Расширение реляционной модели для лучшего отражения семантики

2009 г.

Расширение реляционной модели для лучшего отражения семантики

Э. Ф. Кодд
Перевод: М.Р. Когаловский

9. АССОЦИАЦИИ

9.1. Ассоциативные сущности

Ассоциативные сущности представляются в RM/T точно так же, как и стержневые. Следовательно, для каждого ассоциативного типа сущностей имеется E-отношение и ноль или большее число P-отношений. На рис. 4 показан пример ассоциации назначения между служащими и проектами, где каждое назначение интерпретируется как некоторая сущность, и для регистрации суррогатов служащих и проектов, а также дат назначения используются P-отношения.

Рис. 4. Ассоциативная сущность

Если у заданного ассоциативного типа сущностей имеется подчиненный ему характеристический тип сущностей, то в CG-отношении будут иметься соответствующие кортежи, которые определяют дерево этих типов. Кроме того, для поддержки каждого из этих характеристических типов сущностей будут иметься характеристические отношения.

Вставка, обновление и удаление ассоциативных сущностей регулируются следующим правилом.

Правило 6 (целостность ассоциаций): Ассоциативная сущность может существовать в базе данных (т.е. имеется соответствующий суррогат в соответствующем E-отношении), даже если одна или более участвующих в этой ассоциации сущностей являются неизвестными (если только не задано явное ограничение целостности, запрещающее таких ассоциативных сущностей). В таком случае для указания того факта, что участвующие сущности неизвестны, используется суррогат E-null.

Для принудительного автоматического удаления ассоциации при удалении сущности, участвующей в этой ассоциации, можно легко добавить явное ограничение, устанавливающее, что соответствующий атрибут в подходящем P-отношении не может принимать неопределенного значения. Такое ограничение должно являться частью приложения RM/T, а не составной частью самой RM/T.

Ассоциативный тип сущностей служит для поддержки взаимосвязей сущностей других типов (стержневых, ассоциативных либо тех и других). Назовем эти другие типы непосредственными участниками (immediate participant) заданного ассоциативного типа сущностей. Для поддержки спецификаций, указывающих, какие типы сущностей являются участниками и каких именно ассоциативных типов сущностей, мы вводим ассоциативное графовое отношение (association graph relation, для краткости, AG-отношение). Это точно такое же бинарное отношение, как и CG-отношение, за исключением его интерпретации: (SUB:m, SUP:n) принадлежит AG-отношению, если тип сущностей e(m) непосредственно принимает участие в определении ассоциативного типа сущностей e(n). Заметим, что транзитивное замыкание AG-отношения является частично упорядоченным, но не обязательно представляет собой дерево или совокупность деревьев.

Важно отметить, что, если участником одного типа ассоциаций является другой тип ассоциаций, то использование надлежащим образом суррогатов в ассоциации верхнего уровня для ссылок на конкретных участников более низких уровней может устранить потенциальный источник двусмысленности (таким же образом, как надлежащее использование контролируемых пользователем ключей может устранить такую двусмысленность в базисной реляционной модели). Чтобы проиллюстрировать такую двусмысленность, предположим, что имеется два отношения IS и CAN, причем каждое из них имеет атрибуты S (суррогаты поставщика), P (суррогаты деталей) и C (суррогаты городов):

IS ( S:e P:e C:e )

CAN ( S:e P:e C:e )

где (s:e, p:e, c:e) принадлежит IS, если поставщик s поставляет деталь p из города c; и (s:e, p:e, c:e) принадлежит CAN, если поставщик s может поставлять деталь p из города c.

Предположим также, что имеется необходимость представлять ассоциацию более высокого уровня, которая связывает каждую пару (s, p) из IS c проектом (проектами), получающими детали с серийным номером p. Мы могли бы построить RM/T отношение TO(S:e P:e J:e), где атрибут J определяется на суррогатах проектов. Из этого определения неясно, однако, являются ли пары (s, p) в TO парами из IS, или парами из CAN, или просто произвольными парами суррогатов поставщика и детали. Особое ограничение целостности, имеющее форму:

TO[S:e, P:e] ⊆ IS[S:e, P:e]

помогает разрешить эту двусмысленность на уровне типов, но не на уровне экземпляров. Это связано с тем, что в отношении IS может иметься два или более экземпляров пары (s, p), например, (s, p, c1) и (s, p, c2), и в таком случае неясно, ссылается ли экземпляр (s, p) в отношении TO на (s, p, c1) или на (s, p, c2).

Благодаря использованию ассоциативных сущностей в RM/T такая двусмысленность может быть разрешена как на уровне типов, так и на уровне экземпляров. Мы имели бы следующие отношения RM/T:

IS ( IS:e S:e P:e C:e ... )

CAN ( CAN:e S:e P:e C:e ... )

TO ( TO:e IS:e ... )

где атрибут IS:e в отношении TO ссылается на определенные сущности и, следовательно, определенные кортежи в отношении IS.

Можно считать, что совокупность типов сущностей, принимающих участие (непосредственным или иным образом) в заданном ассоциативном типе сущностей образует ассоциативный молекулярный тип (associative molecule type), который связывается воедино с помощью кортежей в AG-отношения.

9.2. Несущностные ассоциации

Для типа несущностных ассоциаций отсутствует E-отношение. Не существует и суррогата, связанного с ассоциацией этого типа. Следовательно, не существует какого-либо надежного способа (т.е. способа, контролируемого системой) для ссылки на такую ассоциацию в PG-отношении либо в AG-отношении. По таким же причинам она не может принимать являться компонентом какой-либо другой ассоциации.

Рис. 5. Несущностная ассоциация

Тип несущностных ассоциаций представляется единственным n-арным отношением. Атрибуты этого отношения включают E-атрибуты, которые идентифицируют типы сущностей, участвующие в данной ассоциации, вместе с ее непосредственными свойствами (если таковые имеются). На рис. 5 показано, каким образом назначение служащих в проект может интерпретироваться как тип несущностных ассоциаций.

Поведение при вставке, обновлении и удалении регулируется правилом 2 базисной реляционной модели. Таким образом, несущностная ассоциация не может существовать в базе данных, если в ней не присутствуют сущности, взаимосвязь которых она обеспечивает.

9.3. Декомпозиция ассоциаций

Размышления, в том числе, и имеющие отношение к описанию базы данных, не появляются сразу четко декомпозированными на минимальные смысловые единицы.

Если задана ассоциация, состоящая из n (n > 2) участвующих в ней типов сущностей, то проектировщик базы данных, имеющий в своем распоряжении для работы только инструментарий бинарных отношений, весьма вероятно, сразу декомпозировал бы такую ассоциацию на n связанных (anchored) бинарных отношений (каждое из них связывает одного участника с доменом сущности самой ассоциации). Предположим теперь, что он спроектировал ассоциацию в n-арной форме, исследовал ее возможные декомпозиции без потерь и обнаружил, что она могла бы быть декомпозирована на две или более независимых ассоциации более низкой степени, каждая из которых могла бы затем быть декомпозирована отдельно (если это желательно) на бинарные отношения. Мы могли бы тогда сказать, что первоначальная непосредственная декомпозиция на бинарные отношения была преждевременной. Назовем эту ситуацию ловушкой преждевременной бинарной декомпозиции (premature binary decomposition trap). Эта ловушка является взаимнодополняющей по отношению к ловушке соединения [5].

Можно предположить, что в своих попытках достижения минимальных смысловых единиц проектировщик был бы хорошо осведомлен о возможностях использования всей теории n-арных отношений, которая была разработана за последнее десятилетие. Теперь имеются такие концепции, как PJ/NF (иначе называемая 5NF – 5-я нормальная форма) [11], минимальные отношения, атомарная декомпозиция [45], правильно определенные отношения [33], независимые отношения [29] и примитивные отношения [26]. Все это может использоваться как руководство по декомпозиции. Хотя все эти концепции имеют дело, главным образом, с проекциями, которые инвертируются с помощью естественных соединений без потерь, в последних двух из них во внимание принимаются также новые ограничения целостности взаимосвязей, которые могли бы потребоваться, если бы декомпозиция зашла слишком далеко или если бы был сделан плохой выбор из двух или более доступных вариантов декомпозиции.

Заметим, что в общем случае несущностная ассоциация не может быть расщеплена (без потерь информации) на связанные бинарные проекции таким же образом, как ассоциативные сущности, поскольку не существует домена сущностей для восстановительного соединения проекций. По этой и другим причинам RM/T может быть применена к проектированию баз данных только при полном исключении концепции несущностной ассоциации.

10. ДЕКАРТОВА АГРЕГАЦИЯ

Для формирования более крупных смысловых единиц важным измерением ³⁾ является декартова агрегация (Cartesian aggregation). Смит (Smith) и Смит (Smith) в [33] называют ее просто агрегацией, но мы хотели бы отличать ее от других форм агрегации таких, как статистическая агрегация и агрегация покрытия (обсуждаемая ниже). Согласно Смит и Смиту, декартова агрегация – это абстракция, в которой связь между объектами рассматривается как объект более высокого уровня.

В RM/T декартова агрегация подразделяется на три вида:

агрегация простых свойств, которая образует некоторый тип сущностей (характеристический, стержневой или ассоциативный);
агрегация характеристических сущностей, которая образует некоторый тип сущностей (характеристический, стержневой или ассоциативный);

Рис. 6. Декартова агрегация

Первый вид декартовой агрегации поддерживается в RM/T с помощью P-отношений и PG-отношений, второй вид – с помощью характеристических отношений и CG-отношений, а третий вид – с помощью стержневых отношений, ассоциативных отношений и AG-отношений. На рис. 6 приведен пример декартовой агрегации.

Хотя RM/T может применяться с ограничением Смит и Смита, требующим, чтобы абстракция путем декартовой агрегации образовывала понятие, которое именуется единственным существительным английского языка, сама модель не ограничивается таким образом, поскольку это ограничение является слишком нечетким.

11. ОБОБЩЕНИЕ

11.1. Безусловное обобщение

Другим важным измерением для формирования более крупных смысловых единиц является измерение обобщения. Оно привлекает большое внимание в контексте семантических сетей [18, 31, 35]. Мы рассмотрим их здесь в контексте n-арных отношений. Смит и Смит (Smith) определили обобщение (generalization) как абстракцию, при которой множество схожих объектов рассматривается как родовой объект. Это понятие имеет два аспекта: инстанциацию (instantiation) и подтипизацию. Оба они являются некоторыми формами специализации (specialization), а их инверсии – формами обобщения. Экстенсиональным двойником инстанциации является принадлежность множеству, а подтипизации – включение множества. Как показывает рис. 7, чтобы получить конкретных инженеров из родового объекта (или типа) инженер, следует применить инстанциацию. Каждый из типов инженер, секретарь и водитель грузовика являются подтипами типа служащий. Тип сущностей e вместе с его непосредственными подтипами, их подтипами и т. д. образуют иерархию обобщения e. Эта иерархия является еще одним молекулярным типом.

Рис. 7. Безусловное обобщение

Почему нам следует разделять членов иерархии обобщения на различные типы сущностей? Мы делаем это только в том случае, если о разных членах иерархии должны регистрироваться разные виды фактов. Если бы эти типы не были представлялись раздельно, мы имели бы единое большое отношение с многими вхождениями специального неопределенного значения, интерпретируемого как "значение неприменимо". С иерархией обобщения ассоциируется правило наследования свойств (property inheritance rule): к любому подтипу e применимы все свойства его родительского(-их) типа(-ов). Например, все свойства служащих вообще применимы к служащим-продавцам в частности.

Введенные выше E-отношения поддерживают обобщение по членству. Для поддержки обобщения по включению мы вводим отношение безусловного обобщения по включению (unconditional gen inclusion relation, или UGI-отношение) – тернарное отношение, представляющее помеченный граф. Два атрибута UGI-отношения определяются на RN-домене (один с ролью SUB, а другой – с ролью SUP), а третий – на домене меток категорий, называемом PER. Триплет (SUB:m, SUP:n, PER:p) принадлежит UGI-отношению, если сущность типа e(m) является непосредственным подтипом типа сущности e(n) по категории p. Иными словами, E-отношение, имя которого представляется символьной строкой m, принудительно включается (вследствие обобщения по категории p) в E-отношение с именем, представленным символьной строкой n. Заметим, что UGI-отношение поддерживает только ограничения непосредственного безусловного включения, которые ассоциируются с семантическим понятием обобщения. Таким образом, если (SUB:m, SUP:n, PER:p) и (SUB:n, SUP:k, PER:p) принадлежат UGI, то (SUB:m, SUP:k, PER:p) ему не принадлежит.

Транзитивное замыкание UGI-отношения представляет собой отношение частичного порядка на типах сущностей, но не обязательно совокупность деревьев, поскольку тип сущностей может быть обобщен по включению в два или более типов сущностей. Например, инженеры-женщины могут быть обобщены в инженеров, с одной стороны, и в служащих-женщин – с другой.

Рассмотрим семейство типов сущностей в некоторой иерархии обобщения. Обычно хорошим был бы проект базы данных, в котором общие свойства и характеристики этих типов сущностей были бы представлены на возможно более высоком уровне такой иерархии, что позволяло бы в полной мере получать преимущества правила наследования свойств. Однако сама RM/T не налагает такого ограничения на иерархии обобщения – этот подход считается всего лишь дисциплиной проектирования, которую пользователь RM/T может по своему усмотрению принимать или отвергать.

Следующее правило регулирует вставки и удаления суррогатов.

Правило 7 (целостность подтипов): Если суррогат (например, s) принадлежит E-отношению для сущности типа e, то s должен также принадлежать E-отношению для каждого типа сущностей, для которого e является подтипом.

11.2. Альтернативное обобщение

Мы можем теперь расширить обычное понятие иерархии обобщения, заметив, что тип сущностей может быть обобщен в два или более альтернативных (alternative) типа. Например, предположим, что в базе данных, относящейся к заказчикам (см. рис. 8), заказчик (customer) может быть какой-либо компанией (company), товариществом (partnership) или индивидуальным лицом (individual), и все они являются юридическими лицами (legal unit). Предположим также, что для каждого из этих пяти типов сущностей должны регистрироваться различные атрибуты. Поэтому помимо регистрации в UGI-отношении безусловного включения заказчиков, компаний, товариществ и индивидуальных лиц в юридические лица мы должны также где-то регистрировать альтернативное или условное включение заказчиков в компании, товарищества или в число индивидуальных лиц. Для поддержки такой возможности мы вводим отношение альтернативного обобщения по включению (alternative gen inclusion relation, AGI-отношение) – тернарное отношение, в точности похожее на UGI-отношение, за исключением его интерпретации. В данном случае (SUB:m, SUP:n, PER:p) принадлежит AGI-отношению, если E-отношение с именем m принуждается условно включаться в E-отношение n вследствие обобщения по категории p.

Рис. 8. Альтернативное обобщение

Допустим, что вставляется информация о новой сущности, и специфицируется только один из ее нескольких типов. Тогда система может (и, в соответствии с правилом 7, должна) автоматически вставить суррогат, сгенерированный для этой сущности, не только в E-отношение, непосредственно представляющее объявленный тип, но также и в E-отношение для каждой сущности, которая, в соответствии с UGI и AGI, является главенствующей по отношению к объявленной сущности. Должны учитываться оба графовых отношения, поскольку A может быть альтернативно подчинено B и C, которые, в свою очередь, являются безусловно подчиненными D. Следовательно, A безусловно подчинено D, но не непосредственно.

Для иллюстраций операционных различий между UGI и AGI рассмотрим внесение нового заказчика в базу данных, которая соответствует рис. 8. Учитывая UGI, система устанавливает, что суррогат для этого заказчика должен быть введен в E-отношение для юридических лиц, а также для заказчиков. Учитывая AGI, она устанавливает, что для определения необходимости ввода суррогата в E-отношение для компаний, товариществ или индивидуальных лиц требуется дополнительная расширенная информация. Пока не появится эта информация, система не может определить, наследует ли заказчик, упоминаемый в запросе, свойства от компании, товарищества или индивидуальных лиц. Соответственно, AGI (в отличие от UGI) приводит систему в состояние, когда ей требуется получить и учесть расширенную информацию, которой она могла бы руководствоваться.

12. АГРЕГАЦИЯ ПОКРЫТИЯ

Конвой судов определенно является некоторым видом агрегации. Однако это не абстракция путем декартовой агрегации, так же как и не абстракция путем обобщения (суда не являются ни экземплярами, ни подтипами конвоев). Хаммер (Hammer) и Маклеод (McLeod) [15] включили этот вид агрегации в свою модель, и мы используем их пример.

Рис. 9. Агрегация покрытия и обобщение

Рассмотрим базу данных, которая отслеживает свойства отдельных судов и конвоев. Когда вставляется информация о новом судне, обычно не известно, в каких конвоях это судно будет участвовать (и будет ли участвовать вообще). Рис. 9 должен прояснить характерные аспекты этого вида агрегации. Тип покрытия (cover type) CONVOY означает, что эта база данных отслеживает конвои вообще. CONVOY ALPHA – это конкретный конвой, один из нескольких существующих в настоящее время. SAUCY SUE – название судна, которому довелось быть в конвое CONVOY ALPHA. Имеется, кроме того, некоторый подконвой конвоя ALPHA, которому SAUCY SUE также принадлежит. Заметим, что включение SUBCONVOY в CONVOY ALPHA не является обобщением, основанным на включении (SUBCONVOY является экстенсионально, а не интенсионально определенным подмножеством ALPHA). Более того, принадлежность SAUCY SUE конвою CONVOY ALPHA не является обобщением, основанным на принадлежности множеству (SAUCY SUE – это не конкретный конвой или вид конвоя).

В примере конвоя оказывается, что судно обычно не может быть элементом двух конвоев одновременно. Если мы считаем одиночные суда единичными конвоями, то понятие CONVOY осуществляет разбиение класса судов. Непересекаемость конвоев не переносится на все другие примеры агрегации покрытия. Так, рассмотрим вместо судов и конвоев людей и клубы: люди могут принадлежать многим разным клубам одновременно. Таким образом, этот тип агрегации, вообще говоря, образует покрытие, а не разбиение – отсюда его название.

Типовый состав покрытия может быть или не быть однородным по типам. Например, отряд особого назначения может состоять из судов, самолетов, танков и персонала.

Каждый тип агрегации покрытия интерпретируется RM/T как тип сущностей, имеющий обычное E-отношение, а также, возможно, P-отношения и подчиненные характеристические отношения. Например, в случае типа покрытия CONVOY в E-отношении регистрировались бы суррогаты для существующих конвоев, а в P-отношении и характеристических отношениях – свойства каждого конвоя, рассматриваемого как единичный родовой объект.

Хотя и можно интерпретировать каждый элемент покрытия как индивидуальный тип сущностей, обычно это не является необходимым или желательным. Принадлежность индивидуальных сущностей (судов) некоторому элементу покрытия (конкретному конвою) представляется графовым отношением, определенным на E-домене очевидным образом.

Чтобы дать системе возможность контролировать ввод элементов элементов покрытия, мы вводим отношение принадлежности покрытию (couer membership relation, KG-отношение) – графовое отношение на RN-домене, которое указывает для каждого типа агрегации покрытия допустимые типы, которые могут стать элементами элементов покрытия (например, только ли суда допускаются в составе конвоев или допускаются также и самолеты?).

Назад Содержание Вперёд