ERM-models synonymy and problems of scheme consistencyand completeness ensuring.pdf В подавляющем большинстве моделей данных каждое типичное явление мо-делируемого мира представлено в схеме БД лишь однажды, либо в виде струк-турного элемента, либо в виде ограничения целостности. В таком случае человексам должен заботиться о корректности и полноте описания предметной области(ПрО). Модель «Сущность - Связь - Отображение» или, сокращённо, ERM-модель (от английского «Entity - Relationship - Mapping») [1] позволяет проекти-ровщику схемы работать с одними и теми же фактами ПрО на разных уровнях де-тализации и в разных представлениях. Подобный подход даёт возможность про-ектировщику не следовать жёстким требованиям модели, используя единственновозможные формы данных и самостоятельно контролируя правильность своихдействий. Вместо этого он может фиксировать все представляющие интерес поня-тия, взаимосвязи между ними и закономерности этих взаимосвязей в подходящиймомент в любой удобной для него форме, не задумываясь о возможной противо-речивости и неполноте получающейся схемы.Это приводит к тому, что в модели одному и тому же явлению ПрО могут со-ответствовать различные формы и, часто, некоторые из них могут присутствоватьв ERM-схеме одновременно. Такое положение дел неизбежно влечет за собой не-обходимость решения проблемы, касающейся обеспечения непротиворечивостиразличных форм выражения в схеме одного и того же явления ПрО. Второй про-блемой, сопутствующей синонимии, является редукция ERM-схемы - доведениееё до базовых понятий модели, необходимых для автоматической генерацииСУБД-ориентированной схемы БД. Подобная «нормализация» схемы позволяетминимизировать набор правил её трансляции на язык СУБД.1. Базовые и производные понятия ERM-модели и ТСЗОПоскольку ERM-модель является преемницей модели «Сущность - Связь» (ER-модели) [2], её язык сохраняет все традиционные понятия модели Чена - множествосущностей, множество связей, роль, атрибут, множество значений. Однако в ERM-модели эти структурные понятия не играют роли базовых концепций.Таковыми в ней являются новые понятия «класс» и «отображение», которыесущественно расширяют выразительные возможности модели по сравнению с ER-моделью. Они также обеспечивают должный уровень абстракции, доведённой втеории семантически значимых отображений (ТСЗО) до формальной системы[3−5]. К тому же, базовые концепции ERM-модели фигурируют в правилахтрансформации схем в СУБД-ориентированные модели данных.Привычные же понятия ER-модели являются в ERM-модели производными отбазовых понятий, своеобразными их специализациями. Они обеспечивают болеепонятные человеку формы восприятия данных. Подобный подход позволяет про-ектировщику оперировать в основном знакомыми понятиями, прибегая к исполь-зованию новых форм лишь в случае недостаточной выразительности первых.Возможны ситуации, когда при проектировании ERM-схемы используются толь-ко правила структуризации и задания ограничений целостности, целиком принад-лежащие ER-модели, а новые возможности явно не применяются.Чтобы пояснить образование базовых и производных понятий ERM-модели,для начала сформулируем семантические концепции ERM-моделирования. Дляэтого воспользуемся результатами, полученными логиками в ходе анализа естест-венных языков.Моделируемый мир могут составлять объекты любого вида (как эмпириче-ские, так и теоретические). Основной информационной (мыслительной) единицейпредставления ПрО в голове человека является суждение, которое может бытьвыражено в языковой форме - высказывании. Главную роль играют единичныеатрибутивные суждения и единичные суждения об отношениях, утверждающиеналичие у конкретного объекта определенного свойства, характеристики или от-ношения к другим объектам.Характерным для единичных суждений является использование в качестве ло-гических подлежащих их высказываний единичных имен, предметными значе-ниями которых являются отдельные предметы или объекты. Таким образом, име-ем одну из основных семантических концепций ERM-модели - объект. Совокуп-ность объектов, соответствующих одному определённому понятию, образуеткласс объектов.Логическое сказуемое в единичных атрибутивных высказываниях может бытьзадано с использованием одиночного общего имени, предикатора или предметно-го функтора либо более сложного логического выражения, включающего эти зна-ки и логические термины. Все указанные семантические категории могут бытьвыражены через предметные функции. Последние представляют вторую основ-ную семантическую концепцию ERM-модели, которую мы будем называть болееподходящим термином «отображение». Он, во-первых, не несет математическо-го, количественного смысла образов и прообразов, традиционного для понятия«функция». Во-вторых, с функцией, как правило, ассоциируется требование един-ственности образа, чего нам также хотелось бы избежать. Каждый факт соответ-ствия одному объекту одного другого объекта представляет экземпляр отобра-жения.Введённые базовые понятия ERM-модели - объект и экземпляр отображения(для знаков), класс и отображение (для типов), обеспечивают всю выразительнуюмощь модели. Однако человек не всегда использует этот обобщённый уровеньмышления и общения. Для простоты выделяются частные виды объектов, классови отображений, образующие множество производных понятий модели.Объекты, мыслимые в высказываниях как предметы, представляют собойсущности, а классы таких объектов есть не что иное, как множества сущностей.Идеальные объекты, такие, как числа, даты, строки символов, являются значе-ниями. Они не обладают свойствами, характеристиками и не вступают в отноше-ния с другими объектами, кроме того, что являются значениями характеристикэтих объектов. Значения объединяют во множества значений по синтаксическимособенностям. Объекты, соответствующие конкретным понятиям об n-ках пред-метов, представляют собой связи, а классы объектов, составляющих объемы та-ких понятий, есть не что иное, как множества связей. Каждый объект в n-ке свя-зи играет определённую роль, характеризующую его функцию в этой связи.Отображения, определяемые множествами связей, которые в качестве облас-тей определения и значений имеют одиночные множества сущностей или их де-картовы произведения, называются реляционными. Общее количество реляци-онных отображений, определяемых одним множеством связей степени n, равно2n-2. Отображение, ставящее в соответствие объекту или связи истинностное зна-чение, называется отображением-свойством. Если в качестве области значений вотображении используется произвольное множество значений, такое отображениебудем называть отображением-характеристикой. Отображения-свойства пред-ставляют собой частный случай отображений-характеристик. Отображения-характеристики (в том числе и отображения-свойства) являются не чем иным, какатрибутными отображениями, или просто атрибутами.Таким образом, нам удалось связать фундаментальные понятия логики с ос-новными структурными понятиями ER-модели, сохранив при этом базовые поня-тия - объект, класс и отображение. Все вместе они составляют понятийный базисERM-модели.2. Графическая нотация ERM-моделии примеры синонимии элементов ERM-схемДля демонстрации синонимии в ERM-схеме воспользуемся наиболее нагляд-ной формой её представления - графической ERM-диаграммой.Поскольку ERM-модель является преемницей ER-модели, её графическийязык сохраняет многие традиционные конструкции нотаций Чена и Баркера, атакже вводит новые, специфические именно для модели «Сущность - Связь -Отображение» графические элементы.ERM-схема в графической нотации представляет собой граф. Часть типоввершин и дуг этого графа и их представление в точности соответствует аналогамER-диаграммы Чена. Множества сущностей, множества связей и множества зна-чений, как и ранее, обозначаются прямоугольниками, ромбами и овалами соот-ветственно. Роль множества сущностей во множестве связей обозначается неори-ентированным ребром, соединяющим эти множества. При необходимости онопомечается именем роли, а также числами, характеризующими тип множествасвязей. Ориентированные дуги представляют атрибуты. Они выходят из вершинымножества сущностей или множества связей, входят в вершину множества значе-ний и помечаются именами атрибутов.Основное нововведение модели «Сущность - Связь - Отображение» - понятие«отображение». Для его обозначения добавляется новый вид вершин графа -стрелка. Имя отображения пишется внутри стрелки, под ним в скобках указыва-ются количественные характеристики отображения (минимальное кардинальноечисло, максимальное кардинальное число). Множества, составляющие областьопределения отображения, соединяются ребрами с началом стрелки, а множества,составляющие область значений отображения, - с концом стрелки. Рёбра поме-чаются именами ролей образов и прообразов.Продемонстрируем синонимию в ERM-схемах на примере диаграмм предмет-ной области, связанной с ближайшими родственниками. На рис. 1 показан фраг-мент диаграммы множеств сущностей и множеств связей.МатьРождениеЕМатьMОтецЧеловек| |1ЕРебенок1M ЕОтецM1Рис. 1. Фрагмент диаграммы множеств сущностей и множеств связейДля уточнения схемы можно создать диаграммы других видов. На рис. 2 пока-зана диаграмма, демонстрирующая все реляционные отображения, определяемыетернарным множеством связей РОЖДЕНИЕ.МатьРождениеОтецМатьОтецРебенокЧеловекОтец и ребенок(1, М)Мать ре бенка от отца(0, 1)МатьОтец ребенка от матери(0, 1)ОтецМать и ребенок(1, М)Ребенок родителей(0, М)Родители ребенка(1, 1)РебенокРис. 2. Диаграмма реляционных отображений множества связейНалицо синонимия элементов схемы: роли образов и прообразов реляционныхотображений дублируют роли сущностей во множестве связей (структурная си-нонимия), максимальные кардинальные числа отображений совпадают с соответ-ствующими пометками на рёбрах ролей множества связей, пометки «Е» на этихрёбрах говорят о ненулевом минимальном кардинальном числе реляционных ото-бражений (синонимия ограничений целостности).3. Проблема обеспечения непротиворечивостии задача пополнения ERM-схемОсобенности языка ERM-модели и сформулированные ранее принципы по-строения ERM-диаграмм, ориентированные на удобство для проектировщика,влекут за собой возможность синонимии и создания некорректной схемы за счётзадания противоречивых свойств элементам-синонимам. Поэтому ТСЗО должнаобеспечить соответствующие проверки на непротиворечивость схем.Первая группа проверок порождена метасхемой модели и не требует доказа-тельства, поскольку сама структура схемы гарантирует невозможность противо-речий. Примером может служить требование, чтобы каждую роль независимо оттого, является ли она ролью множества связей или ролью отображения, всегда иг-рал один и только один класс.Вторая группа проверок порождается гипотезами и теоремами формальнойсистемы, которые были сформулированы в процессе непрекращающегося анализазакономерностей во взаимоотношениях между понятиями модели. Именно этагруппа правил проверки позволяет обеспечить корректность модели при всёммногообразии её элементов и их синонимии.Кроме правил обеспечения корректности схемы ТСЗО должна предоставитьправила автоматической редукции схемы, предусматривающие построение соот-ветствующих базовых элементов (отображений) из явно указанных человекомпроизводных элементов (множеств связей, атрибутов).Правила пополнения схемы необходимы по двум причинам. Во-первых, ото-бражения, полученные автоматически из множеств связей, открывают перед про-ектировщиком дополнительные возможности для совершенствования схемы, вчастности, для более полного выражения особенностей и законов ПрО. А, во-вторых, правила генерации СУБД-ориентированных схем строятся с использова-нием именно базовых элементов ERM-схемы. Поэтому необходимо хотя бы к мо-менту генерации получить базовые элементы из всех производных элементов.4. Теоретическая основа проверок ERM-схем на непротиворечивостьОбсудим подробнее проверки, основанные на гипотезах и теоремах формаль-ной системы ERM-модели. Новые гипотезы и теоремы строятся на основе аксиоми ранее доказанных теорем формальной системы ТСЗО. В статьях [3, 4] предло-жены первоначальные варианты формальной системы, а в [5] приведена её по-следняя версия и методика доказательства новых теорем.К настоящему моменту исследователями ERM-модели накоплен значительныйбанк гипотез ТСЗО, ожидающих своего доказательства. Одним из источниковэтих гипотез является непрекращающийся анализ закономерностей во взаимоот-ношениях между понятиями ERM-модели и ТСЗО. Другим важным источникомгипотез является теория реляционных БД, теоремы которой часто отражают такиезакономерности данных, которые можно выразить в терминах ТСЗО.Одним из важнейших понятий реляционной модели является понятие функ-циональной зависимости (ФЗ). Оно играет основную роль в процессе нормализа-ции отношений, определяет важный класс ограничений целостности. Кроме того,выводимость одних и тех же ФЗ из имеющихся в схеме - важное условие эквива-лентности двух схем. Предварительным шагом классической методики декомпо-зиции отношений является построение минимального покрытия ФЗ.Во всех этих случаях используются аксиомы Армстронга, определяющиевзаимоотношения между ФЗ. Для удобства также используются три правила, яв-ляющиеся следствием этих аксиом. В ERM-модели есть понятие, очень близкоепонятию «функциональная зависимость», - «функциональное отображение». Вза-имно-однозначное соответствие этих понятий позволяет получать гипотезы и тео-ремы ТСЗО на основе аксиом Армстронга и правил вывода ФЗ.Аксиома пополнения. Пусть A, B и C являются произвольными подмножест-вами множества атрибутов отношения R. Тогда, если имеется ФЗ A -> B, то спра-ведливы ФЗ A, C -> B, C и A, C -> B.Гипотеза пополнения. Пусть имеем функциональное отображение A -> B, гдеООО (A) и ОЗО (B) составляют произвольные совокупности классов. Тогда, еслинекоторое другое отображение включает в ООО и ОЗО те же совокупности клас-сов (A и B соответственно) и справедливо хотя бы одно из двух высказываний:1) в ООО и ОЗО этого отображения кроме упомянутых A и B одновременновходит только одна и та же совокупность классов C;2) ОЗО этого отображения состоит только из B, а ООО кроме A может вклю-чать в себя дополнительные классы,то это отображение функционально.Аксиома транзитивности. Пусть A, B и C являются произвольными подмно-жествами множества атрибутов отношения R. Тогда, если имеются ФЗ A -> B и B-> C, то справедлива ФЗ A -> C.Гипотеза транзитивности. Композиция двух функциональных отображенийфункциональна.Правило декомпозиции. Пусть A, B и C являются произвольными подмноже-ствами множества атрибутов отношения R. Тогда, если имеется ФЗ A -> B, C, тосправедливы ФЗ A -> B и A -> C.Теорема декомпозиции. Если отображение со сложным образом функцио-нально, функциональны и все его проекции на любые роли образов и их совокуп-ности.Правило объединения. Пусть A, B и C являются произвольными подмножест-вами множества атрибутов отношения R. Тогда, если имеются ФЗ A -> B и A -> С,то справедлива ФЗ A -> B, C.Теорема объединения. Агрегат двух функциональных отображений функцио-нален.Правило псевдотранзитивности. Пусть A, B, C и D являются произвольнымиподмножествами множества атрибутов отношения R. Тогда, если имеются ФЗA -> B и B, C ->D, то справедлива ФЗ A, C -> D.Гипотеза псевдотранзитивности. Пусть имеем функциональное отображениеA -> B, где ООО (A) и ОЗО (B) составляют произвольные совокупности классов.Есть также функциональное отображение, ООО которого полностью включаетОЗО первого (B) и дополнительно некоторую совокупность классов C. Тогда ото-бражение, ООО которого состоит из ООО первого (A) и дополнения ООО второго(C), а ОЗО совпадает с ОЗО второго отображения, функционально.Кроме приведенных выше гипотез и теорем, навеянных теорией реляционныхБД, есть ряд гипотез и теорем собственно ТСЗО, также касающихся функцио-нальных отображений.Гипотеза о функциональности проекций. Если проекции отображения навсе роли образов функциональны, функционально и само отображение.Теорема о функциональности пересечения. Пересечение двух отображенийфункционально, если функционально хотя бы одно из отображений-операндов.Теорема о функциональности разности. Разность отображений функцио-нальна, если функционально уменьшаемое отображение.Теорема о функциональности посылки. Отображение, являющееся посыл-кой функционального отображения, функционально.Гипотезы и теоремы о функциональности отображений являются одним из ча-стных примеров зависимостей кардинальных чисел результатов операций от кар-динальных чисел операндов. Наряду с функциональными отображениями нема-лую роль в проектировании схемы БД играют полностью определённые отобра-жения. Тот факт, что отображение полностью определено, говорит о наличии за-висимости одного класса от другого и напрямую влияет на генерацию, например,реляционной схемы, в которой она трансформируется в обязательность заданиязначения для столбца. Далее перечислены гипотезы о полноте отображений.Гипотеза о полноте объединения. Объединение двух отображений полно-стью определено, если хотя бы одно из отображений-операндов полностью опре-делено.Гипотеза о полноте следствия. Следствие полностью определённого отобра-жения полностью определено.Гипотеза о полноте проекции. Проекция полностью определённого отобра-жения на любые группы ролей образов и прообразов полностью определена.Гипотеза о полноте агрегата. Агрегат двух полностью определённых ото-бражений полностью определён.Гипотеза о полноте композиции. Композиция двух полностью определённыхотображений полностью определена.ЗаключениеБогатые выразительные возможности ERM-модели обеспечивают проекти-ровщика всем необходимым для создания максимально полного и подробногоописания предметной области уже на этапе семантического моделирования. Си-нонимия языка модели оставляет выбор удобного способа представления инфор-мации за проектировщиком, но при этом требует осуществлять проверки схемына непротиворечивость.За счёт увеличения детальности информации о семантике ПрО, представлен-ной в схеме, усложняются правила её преобразования в СУБД-ориентированнуюсхему. Однако, благодаря теории семантически значимых отображений, предла-гаемые правила трансформации не носят характер рекомендаций, строящихся напредположениях, их обоснованность подтверждается соответствующими теоре-мами и аксиомами. Кроме того, вся информация, внесённая проектировщиком, повозможности учитывается при генерации целевой схемы, и каждое незначитель-ное на первый взгляд дополнение может существенно улучшить результат -СУБД-ориентированную схему.

Скачать электронную версию публикации