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

Исследовательская лаборатория IBM

В последние три-четыре года рядом исследователей изучались "семантические модели" для форматированных баз данных. Цель заключалась в том, чтобы более или менее формальным образом удерживать больше смысла данных. Благодаря этому проектирование баз данных могло бы стать в большей мере семантическим, и сама система базы данных могла бы вести себя более разумным образом. Двумя главными задачами являлись:

исследование смысловых единиц, являющихся настолько малыми, насколько это возможно - атомарная семантика;

исследование смысловых единиц, больших, чем обычные n-арные отношения - молекулярная семантика.

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

1. ВВЕДЕНИЕ

Реляционная модель для форматированных баз данных [5] была задумана уже десять лет назад, главным образом, как инструмент, призванный освободить пользователя от неудовольствия иметь дело с нагромождением деталей представления данных в среде хранения. Такая независимость от реализации, сочетающаяся с мощью алгебраических операторов n-арных отношений, и открытые вопросы, касающиеся зависимостей (функциональных, многозначных и соединения) внутри отношений и между ними, стимулировали исследования в управлении базами данных (см. [30]). Реляционная модель дала также возможность сосредоточить круг архитектурных интересов на проектировании баз данных и некоторых системах управления базами данных общего назначения, таких как MACAIMS [13], PRTV [38], RDMS(GM) [41], MAGNUM [19], INGRES [37], QBE [46] и System R [2].

В течение нескольких последних лет работы ряда исследователей были нацелены на удержание (формальным в разумной степени образом) больше смысла данных при сохранении независимости от реализации. Эту деятельность называют иногда семантическим моделированием данных. Фактически задача удержания смысла данных - это никогда не завершающаяся задача. Поэтому ярлык "семантическое" не должен интерпретироваться в каком-либо абсолютном смысле. Более того, разработанные ранее модели баз данных (иногда подвергающиеся нападкам как "синтаксические") были не лишены некоторых семантических возможностей (взять, например, домены, ключи и функциональные зависимости). Эта цель является тем не менее чрезвычайно важной, поскольку даже маленький успех может привнести понимание и порядок в область проектирования баз данных. Кроме того, ориентированная на удержание смысла хранимая в компьютере модель данных позволила бы ему отвечать на запросы и другие транзакции более осмысленным образом. Такая модель могла бы послужить также более эффективным посредником между многочисленными внешними представлениями, используемыми прикладными программами и конечными пользователями, с одной стороны, и многочисленными внутренне хранимыми представлениями, с другой стороны.

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

Что касается смысла, то возникает, очевидно, два дополнительных вопроса.

• Что представляет собой атомарный факт (атомарная семантика)?
• Какие более крупные группы информации образуют осмысленные единицы (молекулярная семантика)?

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

2. РЕЛЯЦИОННАЯ МОДЕЛЬ

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

Для того чтобы помочь отличать реляционные системы от нереляционных, мы предлагаем следующие определения. Система базы данных является реляционно-полной, если она поддерживает:

1) структурные аспекты реляционной модели;
2) правила вставки-обновления-удаления;
3) подъязык данных, по крайней мере такой же мощный, как реляционная алгебра, даже если все возможности, которые язык может иметь для итеративных циклов и рекурсии, были удалены из этого языка.

Система базы данных, которая поддерживает (1) и (2), но не (3), является полуреляционной. Заметим, что реляционно-полная система не обязана поддерживать реляционную алгебру в буквальном смысле, но должна поддерживать ее возможности. Следует при этом иметь в виду, что, поскольку реляционная алгебра является мерилом функциональных возможностей, она призвана быть точным интеллектуальным инструментом, позволяющим иметь дело с такими вопросами, как проектирование модели, определение представлений и реструктуризация.

2.1. Структуры

Домен - это множество значений сходного типа: например, все возможные последовательные номера деталей в данной инвентарной ведомости или все возможные даты для класса регистрируемых событий. Домен является простым, если все его значения атомарны (не декомпозируемы системой управления базой данных).

Пусть имеется n (n > 0) не обязательно различных доменов D₁, D₂, ..., D_n. Декартово произведение і {D_i: i = 1, 2, ..., n} - это множество всех кортежей длины n 1, t₂, ..., t_n> таких, что t_i принадлежит D_i для всех i. Отношение определено на таких n доменах, если оно является подмножеством этого декартового произведения. Говорят, что такое отношение имеет степень n.

Вместо множества индексов (1, 2, ..., n) мы можем использовать любое неупорядоченное множество при условии, что мы ассоциируем с каждым компонентом кортежа не только его домен, но также и отличающий его индекс, который мы будем далее называть его атрибутом. В соответствии с этим, n различных атрибутов отношения степени n различают n разных применений доменов, на которых определено данное отношение (напомним, что число различных доменов может быть меньшим, чем n). Тогда кортеж вместо последовательности 1, v₂, ..., v_n> становится множеством пар (A:v), где A - некоторый атрибут, а v - значение, взятое из домена атрибута A.

При этом отношение состоит из множества кортежей, и каждый кортеж имеет одно и то же множество атрибутов. Если все домены являются простыми, то такое отношение имеет табличное представление со следующими свойствами.

• Не существует дубликатов строк (кортежей).
• Порядок строк не имеет значения.
• Порядок столбцов (атрибутов) является несущественным.
• Все элементы таблицы являются атомарными значениями.

Обозначение R(A:a, B:b, C:c, ...) используется для представления изменяющегося во времени отношения R, имеющего атрибут A, который принимает значения из домена a, атрибут B, который принимает значения из домена b, и т. д. Если в некотором контексте рассуждений домены могут игнорироваться, то такое отношение будет представляться как R(A, B, C, ...) или даже просто как R. Нужно заметить, однако, что для корректной интерпретации некоторых выражений (и, главным образом, операторов присваивания) порядок перечисления атрибутов может быть существенным (см. THETA-JOIN ниже).

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

Базовыми называются такие отношения, которые определяются независимо от других отношений в базе данных в том смысле, что никакое базовое отношение полностью не продуцируется (независимо от времени) из каких-либо других базовых отношений.

Выводимыми называются такие отношения, которые могут быть полностью продуцированы из базовых отношений. Это такой вид отношений, которые обычно служат для обеспечения пользователей прикладных программ их собственными представлениями базы данных. Объявленные отношения могут включать выводимые отношения, а также все базовые. Позднее, когда будут введены некоторые дополнительные понятия, мы определим полувыводимые отношения - некоторый класс отношений, относящихся к категории выводимых.

Если U - совокупность атрибутов некоторого отношения, U-компонентом кортежа t этого отношения назовем множество пар (A:v), полученных путем удаления из t таких пар, которые содержат атрибуты, не принадлежащие U.

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

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

(1) Никакие две строки R не содержат одного и того же K-компонента.
(2) Если какой-либо атрибут исключается из K, свойство уникальности (1) утрачивается.

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

Все операции вставки, обновления и удаления, выполняемые над базовыми отношениями, ограничиваются двумя следующими правилами:

Правило 1 (целостность сущностей)

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

Правило 2 (целостность по ссылкам)

Допустим, что некоторый атрибут A составного (т. е. состоящего из нескольких атрибутов) первичного ключа отношения R определяется на первичном домене D. Тогда в любой момент времени для каждого принадлежащего R значения v для A должно существовать базовое отношение (скажем S) с простым первичным ключом (например B) такое, что v появляется как значение B, принадлежащее S.

Реляционная модель состоит из:

• совокупности изменяющихся во времени табличных отношений (с указанными выше свойствами - особо отметим ключи и домены);
• правил вставки-обновления-удаления (Правила 1 и 2, сформулированные выше);
• реляционной алгебры, описываемой далее в разделах 2.2 и 2.3.

Тесно связаны с реляционной моделью различные идеи декомпозиции, являющиеся семантическими по своей природе (как основанные на инвариантных во времени свойствах изменяющихся во времени отношений). Примерами таких идей являются (естественные) соединения без потерь и функциональные зависимости [6], многозначные зависимости [10, 44] и нормальные формы. Более подробное руководство по этим проблемам можно найти в [3]. Кроме того, отсылаем читателя к работе [39]¹⁾.

2.2. Реляционная алгебра (без учета неопределенных значений)

Поскольку отношения являются множествами, здесь применимы обычные теоретико-множественные операторы, такие как UNION (объединение), INTERSECTION (пересечение) и SET DIFFERENCE (разность множеств). Однако их применение ограничивается только парами отношений, совместимых по объединению, т. е. таких отношений, между атрибутами которых имеется взаимно-однозначное соответствие, причем соответствующие атрибуты определены на одном и том же домене. Благодаря этому ограничению гарантируется, что результат является отношением. Оператор CARTESIAN PRODUCT (декартово произведение) применим без такого ограничения.

Определим теперь операторы специально для манипулирования n-арными отношениями. Далее R и S обозначают отношения; A, B1, B2 и C - совокупности атрибутов; c - кортеж соответствующей степени и с соответствующими доменами.

THETA-SELECT (тета-селекция)

Этот оператор иногда называется RESTRICT (ограничением). Пусть Q - одно из бинарных отношений <, <, =, >, <>, которое применимо к атрибуту (атрибутам) A и кортежу c. Тогда R[A Q c] есть множество кортежей из R, A-компоненты каждого из которых находятся в отношении Q с кортежем c. Вместо кортежа c может использоваться другой или другие атрибуты B из R при условии, что A и B определены на общих доменах. Тогда R[A Q B] - это множество кортежей из R, каждый из которых удовлетворяет условию, что его A-компонент находится в отношении Q с его B-компонентом. Если Q представляет собой равенство (очень распространенный случай), оператор THETA-SELECT называется просто SELECT (селекцией).

Примеры THETA-SELECT:

R ( A B C )     R[A <> r] ( A B C )
    p 1 2                   p 1 2
    p 2 1                   p 2 1
    q 1 2                   q 1 2
    r 2 5
    r 2 3       R[A = r] ( A B C )
                           r 2 5
                           r 2 3
                                R[B > C] ( A B C )
                                           p 2 1

PROJECTION (проекция)

Результатом применения оператора проекции к отношению R является отношение R[A₁, A₂, ... A_n], полученное в результате удаления из R всех столбцов, за исключением специфицированных атрибутами A₁, A₂, ... A_n, и последующего удаления избыточных дубликатов строк.

Примеры PROJECTION:

R ( A B C )     R[A, B] (A B)
    p 1 2                p 1
    p 2 1                p 2
    q 1 2                q 1
    r 2 5                r 2
    r 2 3
                R[B, C] ( B C )
R[B] ( B )                1 2
       1                  2 1
       2                  2 5
                          2 3

Теперь мы можем определить третий класс отношений. Полувыводимые отношения - это такие отношения, которые имеют некоторую проекцию (по крайней мере, с одним атрибутом), являющуюся выводимым отношением (см. о слабой избыточности в работе [5]). Если, например, R(A, B) является базовым отношением и S(A, C) - отношение такое, что S[A] = (R[B = b]) [A], и атрибут C определен на некотором домене, не используемом в каком-либо из базовых отношений (и, следовательно, S не является выводимым), то S является полувыводимым отношением. Как мы увидим, существует много применений для полувыводимых отношений. Заметим, что ничем не обусловлено требование обеспечения минимальной избыточности при проектировании реляционных баз данных, хотя это тот вариант, который может быть выбран. Таким образом, декларированные отношения могут включать полувыводимые и даже выводимые отношения, а также базовые отношения.

THETA-JOIN (тета-соединение)

Пусть заданы отношения R(A, B₁) и S(B₂, C) такие, что B₁ и B₂определены на общем домене, и пусть Q - одно из бинарных отношений =, <, <, >, <>, которое применимо к домену атрибутов B₁, B₂. Q-соединение R по B₁ с S по B₂обозначается как R[B₁ Q B₂]S. Это - конкатенация строк отношения R со строками отношения S, формируемая всякий раз, когда B₁ -компонент R-строки находится в отношении Q с B₂-компонентом S-строки. Если отношение Q является равенством, оператор THETA-JOIN называется EQUI-JOIN (эквисоединением). Из всех операторов THETA-JOIN только EQUI-JOIN дает результат, который обязательно содержит два идентичных столбца (один продуцированный из B₁, а другой - из B₂). В общем случае допускается использование в качестве Q произвольного бинарного отношения, которое применимо к домену атрибутов B₁и B₂.

Примеры THETA-JOIN:

R ( A B C )             S ( D E )
    p 1 2                   2  u
    p 2 1                   3  v
    q 1 2                   4  u
    r 2 5
    r 3 3
R[C = D]S ( A B C D E )
            p 1 2 2 u
            q 1 2 2 u
            r 3 3 3 v
R[C > D]S ( A B C D E )
            r 3 3 2 u
            r 2 5 2 u
            r 2 5 3 v
            r 2 5 4 u

Если отношения, к которым применяется оператор THETA-JOIN, имеют какие-либо общие имена атрибутов, то должны быть заданы имена атрибутов результирующего отношения. Например, если каждое из отношений R и S имеет атрибуты A, B, и все эти четыре атрибута определяются на некотором общем домене, мы можем определить несколько возможных Q-соединений R с S. Одно из таких определений:

T(D, E, F, G) = R(A, B)[B > B]S(A, B).

При использовании соглашения о порядке перечисления атрибутов это означает, что источником значений для атрибута D из T является атрибут A из R. Подобным же образом, источниками значений атрибутов E, F и G из T являются, соответственно, атрибуты B из R, A из S и B из S.

NATURAL JOIN (естественное соединение)

Такое соединение ничем не отличается от EQUI-JOIN, за исключением того, что здесь удаляются избыточные столбцы, сгенерированные при выполнении оператора. Естественное соединение - это соединение, используемое при нормализации совокупности отношений.

Пример NATURAL JOIN:

Пусть отношения R и S заданы приведенными выше таблицами. Тогда:

R[C * D]S ( A B C E )
            p 1 2 u
            q 1 2 u
            r 3 3 v

DIVIDE (деление)

Пусть заданы отношения R(A, B1) и S(B2, C) такие, что B1 и B2 определены на одном и том же домене (доменах). Тогда R[B1ЄB2]S - это максимальное подмножество R[A] такое, что его декартово произведение с S[B2] включается в R. Этот оператор является алгебраическим двойником квантора всеобщности.

Пример DIVIDE:

R ( A B )       S ( C )
    p 1             1
    p 2             3
    p 3
    q 1       R[B Є C]S ( A )
    r 1                   p
    r 3                   r

2.3. Расширения алгебры, допускающие неопределенные значения

Смысл двух наиболее важных типов неопределенных значений заключается в том, что "значение неизвестно в настоящее время" или "свойство неприменимо". Подход, при котором допускаются оба типа неопределенных значений, описан в работе [40]. Довольно общий подход к решению проблемы оперирования частичной информацией рассматривается в [22]. Здесь мы будем касаться только первого типа неопределенного значения - "значение неизвестно в настоящее время" - и обозначим его w (см. более подробное обсуждение в [5]). Следующую трактовку следует рассматривать как предварительную и нуждающуюся в дальнейшем исследовании.

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

Первый возникающий вопрос заключается в том, каково значение истинности выражения x = y, если x или y или оба они являются неопределенными значениями? Уместным результатом в каждом из этих случаев является неизвестное значение истинности, а не истина или ложь. В соответствии с этим, мы выбираем трехзначную логику для использования при выборке данных из баз данных, которые могут содержать неопределенные значения. Будем использовать тот же самый символ "w" для обозначения неизвестного значения истинности, поскольку значения истинности могут храниться в базах данных, а мы хотели бы, чтобы интерпретация всех неизвестных или неопределенных значений была однородной. Трехзначная логика базируется на следующих таблицах истинности:

 AND|     F       w       T       OR|      F       w       T
    |                               |
 F  |    F       F        F       F |      F       w       T
 w  |    F       w        w       w |      w       w       T
 T  |    F       w        T       T |      T       T       T
NOT(F) = T;               NOT(w) = w;           NOT(T) = F

Кванторы существования и всеобщности ведут себя подобно многократно применяемым OR и AND, соответственно.

Что касается принадлежности множеству к и включения множеств #, то мы будем присваивать значение истинности w выражениям: w к S и {w} # S всякий раз, когда S - непустое унарное отношение (даже если S содержит какое-либо неопределенное значение). Хотя это и может сначала показаться несколько противоречащим интуитивному представлению, но один из способов добиться, чтобы это казалось более приемлемым, состоит в том, чтобы считать каждое вхождение w держателем места для возможного иного значения. Более точно, выражение, значением которого является некоторое значение истинности, принимает значение w, если и только если (после замещения любых определенных переменных определяющими их выражениями в терминах индивидуальных переменных) имеют место следующие два условия.

1) Каждое вхождение w в выражении может быть замещено некоторым значением, отличным от неопределенного (возможно, разными значениями для разных вхождений) так, чтобы получить значение T для выражения.

2) Каждое вхождение w в выражении может быть замещено некоторым значением, отличным от неопределенного (возможно, разными значениями для разных вхождений) так, чтобы получить значение F для выражения.

Будем называть это принципом подстановки неопределенного значения. Описанная выше трехзначная логика совместима с этим принципом. Следующие примеры иллюстрируют применение этого принципа к принадлежности множеству и к включению множеств. Пусть \ обозначает пустое множество, а R, S, T, U, V - следующие отношения:

R       S       T       U       V
-       -       ---     ---     ---
w       w       w 1     x w     x w 
1       1       y w     w 3     y 3
        2                       z 1

Следующие выражения имеют значение истинности F:

w ≡ \ T # S V # U U # R

Следующие выражения имеют значение истинности w:

R # S S # R T # U U # T

T # V U # V

Заметим, между прочим, что такая схема для неопределенных значений обладает некоторыми свойствами, которые могут, на первый взгляд, показаться парадоксальными. Возьмем, например, отношение EMP (служащие) c атрибутами NAME (фамилия) и AGE (возраст). Выражение

(EMP[AGE < 50] < EMP[AGE > 50])[NAME]

не обязательно продуцирует множество всех имен служащих. Однако, если мы интерпретируем терм EMP[AGE < 50] как множество кортежей в EMP, об AGE-компонентах которых в базе данных известно, что они меньше чем или равны 50, а EMP[AGE > 50] - как множество кортежей, об AGE-компонентах которых известно, что они больше 50, то впечатление парадоксальности исчезает. Такого рода интерпретация не требует, чтобы все тавтологии двузначной логики были сохранены в трехзначной логике (в противоположность [40]).

Применяя принцип подстановки неопределенного значения для проверки неравенств, мы можем исключить произвольный шаг задания w какого-либо места в числовом или лексикографическом упорядочении. В соответствии с этим принципом, мы присваиваем значение истинности w выражениям x Q y, где Q - какое-либо из соотношений <, <, >, >, всякий раз, когда x или y является неопределенным значением.

Для каждого положительного целого n кортеж длины n, состоящий из неопределенных значений (каждое из которых, конечно, сопровождается его атрибутом), является допустимым кортежем. Но небазовое n-арное отношение может содержать самое большее один такой кортеж, в то время как базовое отношение не может содержать таких кортежей вовсе. Как обычно, никакое отношение не может содержать дубликатов кортежей. В случае применения этого правила отсутствия дубликатов (nonduplication rule) неопределенное значение в одном кортеже рассматривается как такое же, как и неопределенное значение в другом. Кажется, что такое отождествление одного неопределенного значения с другим может вступить в противоречие с нашим соглашением о присваивании значения истинности при проверке w = w. Однако отождествление кортежей для удаления дубликатов является операцией на более низком уровне детализации, чем проверка равенства при вычислении условий выборки. Исходя из этого, возможно принять иное правило. Следствия для UNION, INTERSECTION и DIFFERENCE иллюстрируются ниже.

        R       S       R < S   R > S   R - S
--      --      ---     ---     ---
w w     w w     w w     w w     
u w     u w     u w     u w     
u 1     u 1     u 1     u 1     
w 1             w 1             w 1

Рассмотрим теперь влияние неопределенных значений этого типа на остальные операторы реляционной алгебры. Этому влиянию не подвержен оператор CARTESIAN PRODUCT (декартово произведение). Оператор PROJECTION (проекция ) ведет себя, как и ожидалось, при условии, что мы помним, как применяется правило отсутствия дубликатов к кортежам с компонентами, имеющими неопределенное значение. Следующие примеры иллюстрируют оператор проекции:

R R[B, C] R[C]

A B C B C C

---- --- --

u w w w w w

v 1 w 1 w

w w 1 w 1 1

x 1 w

y w 1

Оператор THETA-JOIN (тета-соединение) влечет конкатенацию пар кортежей при условии, что удовлетворяется некоторое заданное условие Q, налагаемое на определенные компоненты этих кортежей. Вычисление этого условие для любой претендующей пары кортежей продуцирует значение истинности F, w или T. Мы оставляем лишь оператор соединения, конкатенирующий только такие пары кортежей, для которых при вычислении условия продуцируется T, и назовем его TRUE THETA JOIN (тета-соединение при "истине"). Кроме того, мы введем оператор MAYBE THETA JOIN (тета-соединение при "может быть"), конкатенирующий только те пары кортежей, для которых при вычислении заданного условия продуцируется w.

Версия MAYBE ("может быть") оператора обозначается помещением символа w после тета-символа (например =w) или символа оператора (допустим Єw). Следующие примеры иллюстрируют операторы TRUE EQUI-JOIN и MAYBE EQUI-JOIN (эквисоединение при "истине" и эквисоединение при "может быть"), а также TRUE LESS-THAN JOIN (соединение меньше, чем при "истине") и MAYBE LESS-THAN JOIN (соединение меньше, чем при "может быть").

R S R [B = C]S R[B =w C]S

A B C A B C A B C

-- -- ---- ----

u w w w 2 2 u w w

w 2 2 u w 2

w 1 w 2 w

w 1 w

R [B < C]S R[B

A B C A B C

---- ----

w 1 2 то же самое,

что и

R[B =w C]S

Если нужно выбрать только те строки из R, которые имеют w в качестве их B-компонента, мы можем применить оператор MAYBE EQUI-JOIN к отношению R с отношением T, чьим единственным элементом является отдельное значение, отличное от неопределенного (годится любое такое значение при условии, что оно выбрано из того же самого домена, на котором определен атрибут B), а затем применяя к результату оператор проекции PROJECT на атрибуты A, B. В приведенном выше случае читатель может проверить, что окончательный результат представляет собой отношение, единственным элементом которого является пара (A:u, B:w). Обработка неопределенных значений оператором THETA-SELECT (тета-селекция) для TRUE и MAYBE версий следует тому же принципу, что и в случае операторов THETA-JOIN.

Подобным же образом обрабатывается оператор деления (DIVISION). Первоначальный оператор, основанный на включении при значении "истина" (проверка включения, которая дает значение T), сохраняется и будет называться TRUE DIVISION (деление при "истина"). Вводится также новый оператор Єw, который основан на включении только при значении "может быть" (проверка включения, вырабатывающая w). Назовем его MAYBE DIVISION (деление при "может быть"). Следующие примеры иллюстрируют эти два вида деления.

R S T R [B Є C]S R[B Єw C]T

A B C C A A

-- - - ---- ----

u 1 2 2 u пусто

u 2 3 w

u 3 R [B Єw C]S R[B Єw C]T

w 2 A A

w w ---- ----

z 3 w u

w

Следующий оператор допускает выполнение над двумя отношениями оператора UNION (объединение), даже если они не являются совместимыми по объединению. Тем не менее результатом всегда является некоторое отношение.

OUTER UNION (внешнее объединение)

Пусть R, S - отношения, которые имеют в качестве общего атрибута (атрибутов) только B и никаких других. Пусть A - оставшийся атрибут (атрибуты) в R, а C - в S. Наконец, пусть

R1(A, B, C) = R і (C:w)

S1(A, B, C) = (A:w) і S,

где і обозначает символ оператора декартова произведения. Тогда внешнее объединение R и S определяется как

R < S = R1 < S1

Заметим, что в частном случае, когда R и S совместимы по объединению,

R < S = R < S

Пример применения оператора OUTER UNION:

R(A B C) S(B D)

p 1 2 2 u

p 2 1 3 v

q 1 2

R < S (A B C D)

p 1 2 w

p 2 1 w

q 1 2 w

w 2 w u

w 3 w v

Подобным образом мы можем также определить OUTER версии для INTERSECTION (пересечение) и DIFFERENCE (разность).

Как при NATURAL JOIN (естественном соединении), так и при EQUI-JOIN (эквисоединении), происходит потеря информации, если соединяемые отношения не имеют равных проекций на атрибуты соединения. Для того чтобы сохранить информацию независимо от равенства этих проекций, нам необходима операция соединения, которая может генерировать неопределенные значения всякий раз, когда это требуется. Такого рода операции были независимо предложены в работах [16, 20, 23, 44].

OUTER THETA-JOIN (внешнее тета-соединение)

Пусть заданы отношения R = R(A, B1) и S = S(B2,C) с B1 и B2, определенными на общем домене, и пусть:

T = R[B1 Q B2]S

R1 = R - T[A, B1]

S1 = S - T[B2, C].

Тогда внешнее тета-соединение определяется как

R[B1 Q B2]S = T < (R1 і (B2:w,C:w)) < ((A:w,B1:w) і S1),

где < обозначает объединение, а і - декартово произведение.

Пример внешнего эквисоединения (OUTER EQUI-JOIN):

S ( S# SCITY ) J ( J# JCITY )

s1 c4 j1 c1

s2 c2 j2 c2

s4 c1 j3 c2

s6 c1 j4 c5

s7 c3

Построим SJ = S[SCITY $ JCITY]J

SJ ( S# SCITY JCITY J# )

s1 c4 w w

s2 c2 c2 j2

s2 c2 c2 j3

s4 c1 c1 j1

s6 c1 c1 j1

s7 c3 w w

w w c5 j4

OUTER NATURAL JOIN (внешнее естественное соединение)

Пусть, как и ранее, заданы отношения R = R(A, B1) и S = S(B2, C), а также отношения T, R1 и S1, определенные так же, как выше, но с заменой "тета" на "=". Тогда внешнее естественное соединение R по B1 с S по B2 определяется как

R[B1 * B2]S = T[A,B1,C] < (R1 і (C:w)) < ((A:w) і S1).

Пример оператора OUTER NATURAL JOIN. Определим T(S#,CITY,J#) = S[SCITY * JCITY]J,

где отношения S и J представлены приведенными выше таблицами. Тогда:

T ( S# CITY J# )

s1 c4 w

s2 c2 j2

s2 c2 j3

s4 c1 j1

s6 c1 j1

s7 c3 w

w c5 j4

В такой трактовке, если оператор генерирует одно или более неопределенных значений, то эти значения всегда имеют тип "значение неизвестно в настоящее время", что согласуется с интерпретацией открытого мира (см. разд. 3). Если бы мы имели дело с отношениями, имеющими интерпретацию замкнутого мира, более уместным был бы тип "свойство неприменимо".

3. СВЯЗЬ С ЛОГИКОЙ ПРЕДИКАТОВ

Опишем два различных способа, с помощью которых реляционная модель может быть связана с логикой предикатов. Предположим, что мы рассматриваем первоначально базу данных как некоторое множество формул в логике предикатов первого порядка. Предположим далее, что каждая такая формула не имеет свободных переменных и находится в максимально возможной атомарной форме (например в A & B замещены составляющие формулы A и B). Допустим теперь, что большинство формул является простыми утверждениями вида Pab ... z (где P - предикат, а a, b, .., z - константы) и что количество различных предикатов в базе данных мало по сравнению с количеством простых утверждений. Такую базу данных называют обычно форматированной, поскольку главная часть ее поддается весьма обычной структуризации. Один из очевидных способов состоит в том, чтобы факторизовать предикат, общий для некоторого множества простых утверждений, и затем интерпретировать это множество как экземпляр n-арного отношения, а предикат - как имя этого отношения. Структурированная таким образом база данных будет далее состоять из двух частей: обычной части, состоящей из совокупности изменяющихся во времени отношений подходящей степени (которая иногда называется экстенсионалом), и необычной части, состоящей из формул логики предикатов, которые являются относительно устойчивыми во времени (ее называют иногда интенсионалом, хотя это, возможно, и не то, что логики Рассел и Уайтхед первоначально подразумевали под этим термином). Можно также рассматривать интенсионал как множество ограничений целостности (т. е. условий, которые определяют все допустимые экстенсионалы) и таким образом исключить изменчивость этих понятий во времени.

Возможны альтернативы при интерпретации отсутствия некоторого кортежа в базовом отношении, которое может рассматриваться как утверждение о том, что значение истинности соответствующей атомарной формулы является (1) неизвестным; (2) ложным. Если принимается альтернатива (1), мы имеем интерпретацию, соответствующую гипотезе открытого мира. Если же принимается альтернатива (2), то мы имеем интерпретацию, соответствующую гипотезе замкнутого мира (см. [28]). Хотя интерпретация, соответствующая гипотезе замкнутого мира, обычно принимается для коммерческих баз данных, существует случай, когда следует допустить, чтобы некоторые отношения (например P-отношения из разд. 7) имели интерпретацию, соответствующую гипотезе открытого мира, в то время как другие отношения (скажем E-отношения для стержневых типов сущностей, обсуждаемых в разд. 5 и 6) имеют интерпретацию, соответствующую гипотезе замкнутого мира.

Независимо от того, принимается ли интепретация открытого или замкнутого мира, реляционная модель весьма близка к логике предикатов. Эта близость является причиной существования большого числа реляционных подъязыков данных, основанных на логике предикатов. Исследование и основательное сравнение таких языков можно найти в работах [20, 27].

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

• Можем ли мы более точно определить, из чего образуется простое утверждение?

• Какие другие уточнения могут быть полезными в форматированной базе данных?

• В какой степени эти дополнительные уточнения могут быть представлены в легко анализируемых структурах данных, а не в процедурах?

Пытаясь дать ответы на эти вопросы, мы будем использовать для мотивации расширений реляционной модели такие популярные неформальные термины, как "сущность", "свойство" и "ассоциация". В конце концов, мы приходим к формальной системе, названной RM/T (здесь T означает "Тасманию", где эти идеи впервые были представлены [9]). Эта система может интерпретироваться многими различными способами. Некоторые интерпретации должны удовлетворять так называемой школе двух концепций в семантическом моделировании, в то время как другие должны удовлетворять школе трех концепций (см. [25, стр. 27]).

4. ОБОЗНАЧЕНИЕ СУЩНОСТЕЙ

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

1) Фактические значения контролируемых пользователем ключей определяются пользователями и, следовательно, должны подвергаться изменениям с их стороны (если, например, сливаются две компании, то две базы данных служащих могут быть объединены таким образом, что некоторые или все последовательные номера служащих могут при этом измениться).

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

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

Эти трудности имеют важное следствие - эквисоединение на общих значениях ключей может не давать того же результата, что и соединение на общих сущностях. Решение этой проблемы, предложенное частично в [4] и в более полном виде в [14], сводится к тому, чтобы ввести домены сущностей, которые содержат назначаемые системой суррогаты. Пользователи базы данных могут заставить систему сгенерировать или удалить некоторый суррогат, но они не имеют контроля ни над значением суррогата, ни над возможностью его показа.

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

В любой базе данных, основанной на RM/T, один из основных доменов служит источником всех суррогатов. Он называется E-доменом. Все атрибуты, определенные на E-домене, называются E-атрибутами. Для того чтобы можно было легко распознавать такие атрибуты, примем соглашение, что им даются имена заканчивающиеся специальным символом "$".

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

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

Возможность выполнения эквисоединения на суррогатах предполагает, что пользователи видят заголовки таких столбцов, но не конкретные значения в этих столбцах.

5. ТИПЫ СУЩНОСТЕЙ

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

В любой базе данных RM/T для каждого типа сущности имеется некоторое унарное отношение (называемое E-отношением). По соглашению, этому отношению дается такое же имя, как и у типа сущности, который оно представляет, в то время как имя его единственного атрибута образуется из имени отношения путем добавления к нему в конце символа "$". Такому атрибуту даются также дополнительные имена (псевдонимы, aliases), если соответствующий тип сущности является подтипом другого типа сущности. В таком случае имеется один псевдоним для каждого типа суперсущности, и этот псевдоним состоит из имени отношения этого супертипа, за которым следует символ "$".

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

Вероятность того, что у сущности может изменяться ее тип или типы, означает, что мы должны различать две цели удаления суррогата сущности из E-отношения:

1) полное удаление сущности из базы данных, что означает удаление всех тех кортежей, в которых ее суррогат появляется в роли уникального идентификатора кортежа, и замещение всех других вхождений специальным суррогатом E-null, который означает "сущность неизвестна" [26];

2) динамическая утрата одного типа для сущности, сопровождающаяся "выживанием" некоторого другого типа для той же самой сущности, что означает: а) удаление ее суррогата из E-отношения для этого типа и из E-отношений некоторых других типов, заключаемых в утрачиваемым типе, но не заключаемых в сохраняемых типах - это станет ясно позже; б) и, кроме того, удаление соответствующих кортежей и замена суррогатов, как это указывалось в (1), за исключением тех, которые ассоциируются с данной сущностью в оставшихся ее типах.

Правило 3 (целостность сущностей в RM/T)

В соответствии с основными правилами для суррогатов, для E-отношений допустимы вставки и удаления, но не обновления. Согласно правилу 1 для базисной реляционной модели, в E-отношениях не допускаются неопределенные значения.

6. КЛАССИФИКАЦИЯ СУЩНОСТЕЙ

И АССОЦИАЦИЙ

Рис. 1. Классификация типов сущностей

Сущности и их типы2) могут классифицироваться следующим образом:

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

• сущности, выполняющие вспомогательную роль в описании сущностей некоторого другого типа; такие сущности и их типы называются характеристическими;

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

• сущности, не выполняющие никакой из указанных выше ролей; такие сущности и их типы называются стержневыми.

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

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

Объекты, которые служат для обеспечения взаимосвязей сущностей, но сами не имеют статуса сущностей, будем называть несущностными ассоциациями. Главное различие между ассоциативными сущностями и несущностными ассоциациями заключается в следующем. Для ассоциативных сущностей, как и для стержневых, допускается наличие характеристических сущностей, а также непосредственных свойств. В то же время для несущностных ассоциаций допускаются только непосредственные свойства. Это и другие различия, обсуждаемые ниже, происходят от трудностей специфицирования перекрестной ссылки на конкретную ассоциацию, когда она не имеет суррогата, уникально ее идентифицирующего. Несущностные ассоциации включены в RM/T, главным образом для того, чтобы продемонстрировать, насколько слабыми являются эти ассоциации по сравнению с ассоциативными сущностями.

На рис. 1 в упрощенном виде представлена классификация типов сущностей (не показано, что характеристические типы сущностей могут сами иметь подтипы). Заметим, что термин внутренний ассоциативный тип сущностей относится к ассоциативному типу сущностей, который не является подтипом какого-либо иного типа сущностей.

Такая классификационная схема в некоторой степени подобна, но несомненно не идентична классификациям, введенным в [32, 42]. Шмид и Свенсон включили в свою схему несущностные ассоциации, но не ассоциативные сущности - в RM/T первые являются необязательными, в то время как вторые - необходимыми.

7. СУЩНОСТИ И

ИХ НЕПОСРЕДСТВЕННЫЕ СВОЙСТВА

Мы уже видели, что E-отношение для заданного типа сущностей декларирует существование таких сущностей, которые имеют этот тип. Непосредственные (имеющие единичные значения) свойства некоторого типа сущностей представляются как различным образом именованные атрибуты одного или более определяющих свойства (property-defining) отношений, называемых P-отношениями. Каждое P-отношение имеет в качестве его первичного ключа некоторый E-атрибут, главная функция которого - связать свойства каждой сущности с декларацией ее существования в E-отношении. Каждый суррогат, появляющийся в этом E-атрибуте, уникально идентифицирует описываемую сущность. Более того, он уникально идентифицирует кортеж, частью которого он является, поскольку свойства имеют единичные значения. Атрибуты P-отношений именуются в соответствии со следующим соглашением: для любого типа сущностей e и любой пары P-отношений для e единственными общими атрибутами этих отношений являются их первичные ключи.

Роль этих E-атрибутов заключается в том, что они служат уникальными идентификаторами для отношений, в которых они появляются. Мы будем называть эту роль K-ролью. Соответственно, каждое P-отношение имеет в точности один E-атрибут, который играет K-роль. Каждое отношение может иметь один или более других E-атрибутов, но их роли являются чисто ссылочными, т. е. это - роль внешнего, а не первичного ключа.

Вставки в P-отношения и удаления из E-отношений управляются следующим правилом.

Правило 4 (целостность свойств)

Кортеж t не может появиться в P-отношении, если соответствующее E-отношение не декларирует факта существования сущности, которую описывает t. Иными словами, компонент первичного ключа - суррогата из кортежа t должен появиться в соответствующем E-отношении.

Было много споров о том, должны ли непосредственные свойства быть представлены вместе в одном определяющем свойства отношении (одна крайность) или они должны быть разбиты на столько бинарных отношений, сколько имеется регистрируемых (в базе данных) свойств (другая крайность). Первое мнение согласуется с дисциплиной PJ/NF [11], в то время как второе соответствует подходу, связанному с несводимыми (минимальными) отношениями [12, 29]. Нормальные формы (отличные от 1NF) не являются обязательными - они просто служат руководящим принципом для проектирования базы данных. Как первоначальная реляционная модель (RM), так и RM/T оставляют это решение на усмотрение пользователя модели. RM/T (и в меньшей степени RM) предоставляет операторы для преобразования из одной формы в другую.

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

Рис. 2. Отношения сущностей и свойств

Следует предостеречь читателя от поспешного вывода о том, что бинарные отношения в чем-то превосходят n-арные отношения, как изобразительные примитивы. Даже в случае непосредственных свойств имеются сомнительные декомпозиции. На рис. 2 показана одна организация непосредственных свойств служащих. В этом и подобных ему примерах у нас может возникнуть желание декомпозировать отношения свойств не более, чем на минимальные смысловые единицы. Должны ли, например, компоненты даты - день (Da), месяц (Mo) и год (Yr) представляться в отдельных P-отношениях? Должны ли разделяться компоненты адреса - номер строения (No), название улицы (Street), город (City) и штат (State)? Помимо использования понятия минимальной смысловой единицы может возникнуть желание принять критерий исключения вхождений неопределенных значений вида "свойство неприменимо". Эта цель часто может достигаться без бинарной атомизации.

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

Заметим, что подходящим соединением для определения представления, которое инкапсулирует некоторые или все непосредственные свойства типа сущностей в едином n-арном отношении, является внешнее естественное соединение (OUTER NATURAL JOIN) всех P-отношений для этого типа по E-атрибутам с K-ролью (см. пример A в разд. 15.4). Такое соединение решает задачу независимо от того, насколько мелкой или крупной будет декомпозиция свойств.

Чтобы пояснить, каким образом P-отношения для заданного типа сущностей связываются с E-отношением для этого типа, мы будем использовать следующие объекты и свойства RM/T. Прежде всего, к ним относится имя_отношения (relname) - представление имени этого отношения в форме символьной строки. Имя_отношения (предполагаемого временным), для которого не было сделано присваивания, имеет неопределенное значение. Каждое базовое отношение имеет имя_отношения, отличное от неопределенного значения. Кроме того, каждое выводимое отношение, которое указывается в левой части какого-либо оператора присваивания, также имеет имя_отношения, отличное от неопределенного значения. Домен имен_отношений (сокращенно - RN-домен) - это домен всех имен_отношений в базе данных.

Теперь мы введем графовое отношение свойств (property graph relation, или PG-отношение), которое указывает, какие P-отношения представляют типы свойств, ассоциированных с каждым E-отношением.

Оба атрибута PG-отношения определяются на RN-домене. Один из этих атрибутов имеет имя SUB, указывающее его подчиненную роль, в то время как другой - имя SUP, указывающее его старшую роль. Если m, n представляют собой, соответственно, имена P-отношения и E-отношения, то пусть выражения p(m), e(n) обозначают тип свойств, представляемый P-отношением, и тип свойств, представляемый E-отношением, соответственно. Пара (SUB:m, SUP:n) принадлежит PG тогда и только тогда, когда p(m) есть тип свойств для типа сущностей e(n).

Совокупность P-отношений для заданного E-отношения можно рассматривать как составляющую некоторый молекулярный тип свойств, который связывается воедино кортежами в PG-отношении.

8. МНОГОЗНАЧНЫЕ И КОСВЕННЫЕ СВОЙСТВА СУЩНОСТЕЙ

Рис. 3. Характеристические отношения

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

Характеристическая сущность сама может иметь одну или более характеристических сущностей, ей подчиненных. Хорошо известный пример - служащие (стержневой тип сущностей), каждый из которых имеет послужной список (характеристический тип сущностей, подчиненный типу служащих), непосредственными свойствами которого являются дата занятия должности (Date) и название должности (Jobname). Эта информация дополняется историей зарплаты (характеристический тип сущностей, подчиненный послужному списку, см. рис. 3), непосредственные свойства которой - дата изменения зарплаты (Date) и новая сумма зарплаты (Amount).

Необходимость в описанном выше характеристическом типе сущностей возникает в связи со строго многозначной зависимостью (т. е. зависимостью, которая не является функциональной). Другая возможность возникновения характеристического типа сущностей связана с транзитивной функциональной зависимостью [6]. В этом случае тип сущностей e имеет непосредственное свойство p, которое, в свою очередь, имеет непосредственное свойство q (например участок скоростной магистрали имеет один из нескольких типов материалов покрытия, которые, в свою очередь, имеют некоторую пористость). Может быть введен тип сущностей, который является характеристическим относительно участков скоростной магистрали для того, чтобы представлять типы материалов покрытия на этих участках. Тогда пористость становится непосредственным свойством этого типа сущностей.

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

Для того чтобы представлять совокупность характеристических деревьев, мы вводим характеристическое графовое отношение (characteristic graph relation, или CG-отношение), бинарное отношение, оба атрибута которого определены на RN-домене. Один из его атрибутов играет роль SUB, а другой - роль SUP (как и в PG-отношении). Это отношение интерпретируется следующим образом. Пара (SUB:m, SUP:n) принадлежит CG, если тип сущностей e(m) непосредственно подчинен типу сущностей e(n) в одной из характеристических иерархий.

Вставка и удаление характеристических сущностей управляются следующим правилом.

Правило 5 (целостность по характеристикам)

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

Совокупность характеристических отношений для заданного E-отношения можно рассматривать как характеристический молекулярный тип, который связывается воедино кортежами в CG-отношении.

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

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

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

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

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

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

Правило 6 (целостность ассоциаций)

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

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

Ассоциативный тип сущностей служит для поддержки взаимосвязей сущностей других типов (стержневых, ассоциативных либо того и другого). Назовем эти другие типы непосредственными участниками заданного ассоциативного типа сущностей. Для поддержки спецификаций, указывающих, какие типы сущностей являются участниками и каких именно ассоциативных типов сущностей, мы вводим ассоциативное графовое отношение (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$,P$] # IS[S$,P$]

помогает разрешить эту двусмысленность на уровне типов, но не на уровне экземпляров. Это связано с тем, что в отношении 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$ в отношении TO ссылается на определенные сущности и, следовательно, определенные кортежи в отношении IS.

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

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

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

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

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

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

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

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

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

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

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

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

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

Важным измерением3) для формирования более крупных смысловых единиц является измерение декартовой агрегации. Смит и Смит в [33] называют ее просто агрегацией, но мы хотели бы отличать ее от других форм агрегации таких, как статистическая агрегация и агрегация покрытия (обсуждаемая ниже). Согласно Смит и Смиту, декартова агрегация - это абстракция, в которой связь между объектами рассматривается как объект более высокого уровня.

3) Имеются в виду измерения многомерного информационного пространства, поддерживаемого RM/T. - Прим. пер.

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

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

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

3) Агрегация любой комбинации стержневых и ассоциативных типов сущностей, которая образует либо ассоциативный тип сущностей, либо тип несущностных ассоциаций.

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

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

11. ОБОБЩЕНИЕ

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

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

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

Почему мы должны разделять членов иерархии обобщения в различных типах сущностей? Мы делаем это только в случае, если различные виды фактов должны регистрироваться о различных членах иерархии. Если бы эти типы не были представлены раздельно, мы имели бы единое большое отношение с многими экземплярами специального неопределенного значения, интерпретируемого как "значение неприменимо". С иерархией обобщения ассоциируется правило наследования свойств: если задан некоторый подтип e, то все свойства его родительского типа (типов) относятся к 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. Альтернативное обобщение

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

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

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

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

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

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

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

Рассмотрим базу данных, которая отслеживает свойства отдельных судов и конвоев. Когда вставляется информация о новом судне, обычно не известно, в каких конвоях это судно будет участвовать (и будет ли участвовать вообще). Рис. 9 должен прояснить различные аспекты этого вида агрегации. Тип покрытия (cover type) КОНВОЙ означает, что эта база данных отслеживает конвои вообще. КОНВОЙ АЛЬФА - это конкретный конвой, один из нескольких существующих в настоящее время. SAUCY SUE означает судно, которому довелось быть в КОНВОЕ АЛЬФА. Имеется, кроме того, некоторый подконвой АЛЬФА, которому SAUCY SUE также принадлежит. Заметим, что включение ПОДКОНВОЯ в КОНВОЙ АЛЬФА не является обобщением, основанным на включении (ПОДКОНВОЙ является экстенсионально, а не интенсионально определенным подмножеством АЛЬФА). Более того, принадлежность SAUCY SUE КОНВОЮ АЛЬФА не является обобщением, основанным на принадлежности множеству (SAUCY SUE - это не конкретный конвой или вид конвоя).

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

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

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

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

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

13. ПРЕДШЕСТВОВАНИЕ СОБЫТИЙ

Сущности типа событий - это такие сущности, частью описания которых является время происхождения либо время начала и/или время окончания. Заметим, что не все сущности с атрибутами времени - события. В частности, ассоциативная сущность, которая указывает, что поставщик x может поставить деталь y со сроком доставки, равным трем месяцам, сама по себе не является событием.

Упорядочение событий во времени играет важную роль в некоторых базах данных. Обеспечение регистрации этого упорядочения на уровне типа представляет собой шаг в направлении поддержки сценариев (scripts) (см. [17]).

Событие e1 следует за событием e2, если время происхождения/начала e1 является строго более поздним, чем время происхождения/окончания e2 (в соответствии с тем, принимаются ли эти события как мгновенные или нет). Некоторые типы событий будут безусловно следующими за одним или более других типов событий. Такое следование - это обычно отношение частичного порядка. Оно представляется в RM/T отношением безусловного следования (US-отношение) - графовым отношением на RN-домене. (SUB:m, SUP:n) принадлежит этому отношению, если событие типа e(m) должно следовать за событием типа e(n), и не существует какого-либо промежуточного типа событий e такого, что e является безусловным преемником e(m), а e(n) - безусловным преемником e.

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

Если событие e2 следует за событием e1, это, очевидно, означает, что e1 является предшественником e2, но это не означает, что e1 обязательно является единственным предшественником e2, даже если e2 - единственный преемник e1. Следовательно, нам необходимы два дополнительных графовых отношения для описания предшествования между типами событий: UP - для безусловного предшествования и AP - для альтернативного предшествования.

Для иллюстрации использования этих графовых отношений предположим, что имеется база данных, которая включает записи заказов, помещенные поставщиками, и записи поставок, которые поступили как входные данные для инвентаризации (соответствующие типы сущностей-событий будут называться заказами и поставками). Предположим также, что мы отвергаем принятие записей поставок в инвентаризационную ведомость, если не существует какого-либо невыполненного заказа, относящегося к товарам в запросе. Тогда отношение UP должно содержать кортеж (SUB:заказы, SUP:поставки), наличие которого интерпретируется как утверждение, что каждому принятию записи поставки должен безусловно предшествовать какой-либо заказ. Кроме того, отношение AS должно включать некоторый кортеж, соответствующий утверждению, что одним из возможных событий-преемников для помещения заказа является принятие записи поставки (поставки могут, конечно, отвергаться). Такая интенсиональная информация может использоваться системой базы данных для того, чтобы подвергать сомнению допустимость принятия конкретных записей поставок, не охваченных соответствующими заказами.

Более общо, отношения US, AS, UP, AP обеспечивают средства задания ограничений на вставку и обновление для событийных отношений, поддерживающих некоторый тип событий. С другой стороны, их поведение при вставке, обновлении и удалении определяется тем, являются ли они стержневыми или ассоциативными.

14. КАТАЛОГ RM/T

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

CATR (R$ RELNAME RELTYPE)

CATRA (RA$ R$ A$)

CATA (A$ ATTNAME USERKEY)

CATAD (AD$ A$ D$ )

CATD (D$ DOMNAME VTYPE ORDERING)

CATC (C$ PERNAME)

CATRC (RC$ R$ C$)

где CATR, CATA и CATD описывают отношения, атрибуты и домены, соответственно; CATRA связывает атрибуты и их домены; CATRC связывает отношения и категории (см. подробнее ниже). Кроме того, атрибуты R$, A$, D$ и C$ определяются на E-домене и содержат суррогаты, соответственно, для сущностей типов отношение, атрибут, домен и метка категории. Наконец, атрибуты RA$, AD$ и RC$ также определяются на E-домене и содержат суррогаты для ассоциативных сущностей типов отношение-атрибут, атрибут-домен и отношение-категория-метка, соответственно. Остальные атрибуты перечислены ниже с кратким пояснением:

RELNAME имя_отношения для отношения (определенное на RN-домене);

ATTNAME имя_атрибута для атрибута;

DOMNAME имя_домена для домена;

PERNAME метка категории (определенная на домене PER);

RELTYPE тип объекта, представляемого отношением;

USERKEY указывает, принимает ли атрибут участие в определяемом пользователем ключе для соответствующего отношения;

VTYPE семантический тип значения;

ORDERING указывает, применим ли оператор > для значений в соответствующем домене.

Для заданной категории c, тип сущностей называется вершиной категории c (top per c), если он имеет, по крайней мере, один подчиненный тип сущностей в c, но сам не является подчиненным какому-либо типу в c. Отношение CATRC содержит, по крайней мере, один кортеж для каждой категории. Для каждой категории в базе данных в нем перечислены отношения, которые представляют типы сущностей - вершины этой категории. Полагаем, что смысл других отношений в каталоге модели RM/T очевиден.

Подходящие типы_отношений специфицируются для отношения путем конкатенации соответствующих букв из следующего списка:

A отношение ассоциативных типов сущностей;

C отношение характеристических типов сущностей;

E E-отношение;

G графовое отношение;

I отношение внутренних стержневых типов сущностей;

K отношение стержневых типов сущностей;

L граф с помеченными ребрами;

N отношение несущностных ассоциаций;

P отношение свойств;

T отношение типов сущностей-событий.

Например, отношение, представляющее стержневой тип сущностей-событий, имело бы тип_отношения TK; отношение, которое представляет ориентированный граф с помеченными ребрами, имело бы тип_отношения LG.

15. ОПЕРАТОРЫ ДЛЯ RM/T

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

15.1. Операторы над именами

NOTE (имя)

Пусть имеется отношение R. Тогда NOTE(R) - это имя_отношения R (т. е. представление имени R в форме литерной строки) в том случае, если такое имя было присвоено отношению R пользователем. В противном случае NOTE(R) имеет неопределенное значение. Для наших целей сейчас нет необходимости распространять этот оператор на объекты, отличные от отношений. Многие отношения, являющиеся промежуточными результатами, не будут иметь имени_отношения. Однако каждому базовому отношению должно быть дано какое-либо имя_отношения.

TAG (тег)

Пусть имеется отношение R. Тогда

TAG(R) = R і {NOTE(R)}

где і обозначает декартово произведение.

DENOTE (отношение)

Пусть r - это имя некоторого отношения. Тогда DENOTE(r) - отношение, обозначаемое r. В случае применения к отношениям, которые имеют имена, операторы NOTE и DENOTE являются обратными друг к другу.

Оператор DENOTE может применяться также к унарному отношению, которое является множеством имен_отношений. Пусть R - такое отношение. Тогда DENOTE(R) представляет собой множество всех таких отношений, имена_отношений которых принадлежат R.

15.2. Операторы над множествами

COMPRESS (сжать)

Пусть f - некоторый ассоциативный и коммутативный оператор, который отображает пару отношений в отношение (например оператор соединения join). Пусть далее Z - множество отношений такое, что f может быть допустимым образом применен к каждой паре отношений в Z. Тогда COMPRESS(f, Z) - это отношение, полученное путем многократного попарного применения f к отношениям в Z. Возможна альтернативная запись COMPRESS(f, Z) как f/Z.

APPLY (применить)

Пусть f - унарный оператор, который отображает отношения в отношения, а Z - множество отношений (не обязательно совместимых по объединению). Тогда APPLY(f, Z) продуцирует множество всех отношений f(z), где z - элемент Z. Примем для удобства соглашение о том, что если некоторое множество отношений используется в алгебраическом выражении в одном или нескольких местах, в которых употребление имени отношения было бы синтаксически допустимо, то это выражение вычисляется для каждого элемента этого множества. Однако

• это выражение должно быть заключено в скобки с предшествующим словом APPLY

• не более одного множества отношений может быть упомянуто в области действия одного оператора APPLY (но может быть упомянуто любое число отдельных отношений).

PARTITION BY ATTRIBUTE: PATT (разбиение по атрибуту)

Пусть R - отношение с атрибутом A (возможно, составным), причем R может иметь и другие атрибуты. Тогда PATT(R, A) - это множество отношений, полученных разбиением R по всем различным значением A. Для всех отношений, имеющих атрибут A:

R = UNION/PATT(R, A).

PARTITION BY TUPLE: PTUPLE (разбиение по кортежам)

Пусть R - некоторое отношение. Тогда PTUPLE(R) - это множество отношений, полученных путем помещения каждого кортежа R в некоторое однокортежное отношение. Заметим, что R = UNION/PTUPLE(R).

PARTITION BY RELATION: PREL (разбиение по отношению)

Пусть R - некоторое отношение. Тогда PREL(R) - это множество отношений, у которых единственным элементом является отношение R. Заметим, что R = UNION/PREL(R).

SETREL (множество отношений)

Этот оператор принимает в качестве аргументов любое число явно указанных отношений и продуцирует в результате множество отношений. Соответствующее выражение:

SETREL(R1, R2, ..., Rn).

15.3. Графовые операторы

В данном разделе рассматриваются операторы, включенные в модель для удобства манипулирования ориентированными графовыми отношениями (PG, CG, AG, UGI, AGI, US, AS, UP, AP, KG). Отношение R называется отношением-диграфом4), если оно имеет степень не менее двух и обладает следующими свойствами: (1) два его атрибута определены на общем домене; (2) один из них исполняет роль SUB, а другой - роль SUP; (3) никакие другие атрибуты отношения не исполняют роли SUB или SUP. Отношение R является отношением-диграфом с помеченными ребрами, если: (1) оно является отношением-диграфом степени не менее трех; (2) в точности один из его атрибутов исполняет роль PER (помечивание); и (3) для каждого набора m, n, p никакие два кортежа R не имеют общих (SUB:m, SUP:n, PER:p). Отношение-диграф, которое не является отношением с помеченными ребрами, называется непомеченным.

4) Здесь диграф - ориентированный граф (от англ. digraph=directed graph). - Прим. пер.

OPEN (открыть)

Случай 1. Пусть R - непомеченное отношение-диграф (т. е. никакой его атрибут не исполняет роли PER). Тогда OPEN(R) порождает копию R, в которой удалены все не непосредственные подчинения. Иначе говоря, это - максимальное подмножество R1 отношения R, обладающее следующим свойством: если (SUB:m, SUP:n) принадлежит R1, то либо не существует какого-либо k, для которого как (SUB:m, SUP:k), так и (SUB:k, SUP:n) принадлежат R1, либо, в противном случае, при существовании такого k имеет место k = m или k = n.

Случай 2. Пусть R - отношение-диграф с помеченными ребрами. В таком случае OPEN(R) порождает максимальное подмножество R1 отношения R, обладающее следующим свойством: если (SUB:m, SUP:n, PER:p) принадлежит R1, то либо не существует какого-либо k, для которого как (SUB:m, SUP:k, PER:p), так и (SUB:k, SUP:n, PER:p) принадлежат R1, либо, в противном случае, при существовании такого k имеем k = m или k = n.

CLOSE (замыкание)

Случай 1. Пусть R - непомеченное отношение-диграф. В таком случае CLOSE(R) - транзитивное замыкание R, т. е. это - минимальное надмножество R такое, что если и (SUB:m, SUP:k), и (SUB:k, SUP:n) принадлежат R, то (SUB:m, SUP:n) также принадлежит CLOSE(R). Кортежи в CLOSE(R), которые не принадлежат также и R, имеют неопределенные значения для тех атрибутов, которые отличны от SUB и SUP.

Случай 2. Пусть R - отношение-диграф с помеченными ребрами. Тогда CLOSE(R) - минимальное надмножество R такое, что если и (SUB:m, SUP:k, PER:p) и (SUB:k, SUP:n, PER:p) принадлежат R, то (SUB:m, SUP:n, PER:p) также принадлежит CLOSE(R). Кортежи в CLOSE(R), которые не принадлежат также и R, имеют неопределенные значения для тех атрибутов, которые отличны от SUB, SUP и PER.

Заметим, что для всех отношений-диграфов R имеют место соотношения:

OPEN(OPEN(R)) = OPEN(R),

OPEN(CLOSE(R)) = OPEN(R),

CLOSE(CLOSE(R)) = CLOSE(R)

В то же время для всех непомеченных отношений-диграфов R степени 2 и для всех отношений-диграфов R степени 3 с помеченными ребрами справедливо также:

CLOSE(OPEN(R)) = CLOSE(R).

Для отношений-диграфов с более высокой степенью OPEN может утрачивать информацию (содержащуюся в атрибутах, отличных от SUB, SUP и PER), которую CLOSE не может восстановить.

STEP (шаг)

Случай 1. Пусть R - непомеченное отношение-диграф, которое не имеет атрибута SEP, обозначающего отделение (separation). Пусть также Z - множество всех атрибутов R, отличных от SUB и SUP. Тогда STEP(R) - это множество всех кортежей вида

(SUB:x, SUP:y, Z:z, SEP:n),

где (SUB:x, SUP:y, Z:z) принадлежит R, а n - наименьшее число ребер графа, которые отделяют узел x от узла y.

Случай 2. Пусть R - отношение-диграф с помеченными ребрами, которое не имеет атрибута SEP. Пусть также Z - множество всех атрибутов R, отличных от SUB, SUP и PER. Тогда STEP(R) - это множество всех кортежей вида

(SUB:x, SUP:y, PER:p, Z:z, SEP:n),

где (SUB:x, SUP:y, PER:p, Z:z) принадлежит R, а n - наименьшее число ребер графа с меткой p, которые отделяют узел x от узла y.

15.4. Примеры

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

Получим сначала имена всех P-отношений для типа сущностей служащие:

R1 Є PG[SUP = emp] [SUB].

Вспомним, что PG - графовое отношение свойств. Тогда мы получаем соответствующее множество отношений:

R2 Є DENOTE(R1).

Наконец, многократно применяем внешнее естественное соединение * по атрибуту EMP$ (общему для всех отношений в этом множестве):

R3 Є (* EMP$)/R2,

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

Предположим, что мы скомбинируем выражения для R1, R2, R3 в единое выражение и заменим emp на r, где r - это имя_отношения для какого-либо типа сущностей. Пусть PROPERTY(r) обозначает результат. Тогда получаем:

PROPERTY(r) = ( * r, "$")/DENOTE(PG[SUP = r] [SUB]).

Здесь PROPERTY, таким образом, отображает имя_отношения типа сущностей в соответствующее исчерпывающее P-отношение.

Пример B. Получить имя служащего и должность для всех служащих с отличным (excellent) рейтингом в предположении, что:

(1) имеются различные типы сущностей для каждого типа должности (например, секретарь, водитель грузовика, инженер и т.д.), и категория типа должности (jobtype) производит разбиение множества служащих;

(2) непосредственным обобщением этих типов может быть тип сущностей служащие (emp);

(3) имя и должность служащего записываются в одно или более P-отношений, ассоциированных с типом сущностей служащие;

(4) рейтинг записывается отдельно в некоторое P-отношение для каждого типа должности.

Имеем:

R1 Є UGI[SUP = emp, PER = jobtype][SUB].

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

На втором шаге получаем:

R2 Є APPLY(PROPERTY, R1).

Здесь R2 - множество P-отношений, каждое из которых является исчерпывающим P-отношением для одного из имен_отношений в R1.

Далее:

R3 Є APPLY(R2[RATING = excelent]).

Имеем R3 - множество отношений, в точности похожее на R2, за исключением того, что каждое отношение в R3 является ограничением его двойника в R2.

Теперь имеем: R4 Є APPLY(R3[EMP$]),

где R4 - множество отношений, полученных проекцией каждого отношения из R3 на атрибут EMP$.

Следующий шаг:

R5 Є (PROPERTY(emp))[EMP$, NAME, JOBTYPE]

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

Наконец, получаем:

R6 Є UNION/APPLY(R4[EMP$ = EMP$]R5).

При этом строится соединение каждого отношения из множества R4 с отношением R5. Результат сжимается многократным объединением для получения R6 - требуемого результата.

Окончательное выражение - пример соединения по сущности, в отличие от соединения по свойству.

Пример C. Пусть некоторая база данных содержит информацию о служащих. Свойства и характеристики, относящиеся ко всем служащим, связываются через посредство PG и CG с типом сущностей служащие. Кроме того, служащие категоризируются по:

• должности - инженер, секретарь, техник и т. д.

• служебному статусу - постоянный и временный.

В базу данных записывается различное множество свойств и характеристик для всех этих разнообразных специализаций. Граф обобщения UGI показывает типы сущностей инженер, секретарь, техник и т. д., как подчиненные типу сущностей служащие по категории должность, а типы сущностей постоянный и временный как подчиненные типу сущностей служащие по категории статус.

Требуется получить тернарное отношение R такое, что (E-домен:x, RN-домен:y, PER-домен:z) принадлежит R тогда и только тогда, когда x является суррогатом некоторого служащего, y - типом сущности x в категории z. Фактически, мы конвертируем информацию категории в новый атрибут отношения на родительском уровне.

Имеем сначала:

R1 Є UGI[SUP = emp] [SUB, PER].

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

Далее:

R2 Є DENOTE(R1[SUB]).

Здесь R2 - это соответствующее множество отношений.

Отсюда получаем:

R3 Є APPLY(TAG, R2).

Для получения множества R3 берется каждое отношение в R2 и к нему добавляется столбец, который содержит столько экземпляров имени_отношения для данного отношения, сколько имеется кортежей в этом отношении.

Наконец, имеем:

R4 Є UNION/APPLY(R3[RN * SUB]R1).

Естественное соединение с отношением R1 применяется к каждому отношению в R3 с использованием атрибутов имени_отношения. Для получения желаемого отношения результирующее множество отношений сжимается путем многократного применения объединения.

Пример D. Скомбинировать всю информацию из графовых отношений RM/T в одном отношении R, имеющем атрибуты SUB, SUP, PER и RN, где (SUB:m, SUP:n, PER:p, RN:q) принадлежит R тогда и только тогда, когда

(1) q - имя_отношения для помеченного графового отношения и (SUB:m, SUP:n, PER:p) принадлежит q; или

(2) q - имя_отношения непомеченного графового отношения, p - неопределенное значение и (SUB:m, SUP:n) принадлежит q.

Предположим, что тип графового отношения есть G. Не будем делать каких-либо предположений о числе графовых отношений в RM/T или об их именах.

Имеем:

R1 Є DENOTE(CATR[RELTYPE = G] [RN]),

R2 Є APPLY(TAG, R2),

R Є < /R2.

В последнем операторе требуется внешнее объединение, поскольку не все графовые отношения в RM/T имеют одну и ту же степень.

16. СВОДКА ВОЗМОЖНОСТЕЙ RM/T

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

Рис. 10. Четыре измерения RM/T

Таблица I

Примечание: В любой базе данных RM/T имеется только один объект для каждого типа, помеченного звездочкой. Отношения, помеченные символом "%", имеют дубликаты E-отношений, не перечисленные здесь явно.

Объект RM/T Цель

Суррогат Контролируемый системой представитель сущности

Имя_отношения Строковое представление имени отношения базы данных

Тип_отношения Строковое представление типа отношения

E-null * Суррогат, обозначающий "сущность неизвестна"

E-домен * Домен активных суррогатов

PER-домен * Домен меток категорий

RN-домен * Домен имен_отношений

E-атр Атрибут, определенный на E-домене

RN-атр Атрибут, определенный на RN-домене

PER-атр Метка в графовом отношении

SEP-атр Отделение одного узла от другого

SUB-атр Подчиненный в графовом отношении

SUP-атр Старший в графовом отношении

CATR-отн %* Список всех имен_отношений и соответствующих типов_отношений

CATRA-отн %* Отношения и их атрибуты

CATA-отн %* Список всех атрибутов

CATAD-отн %* Атрибуты и их домены

CATD-отн %* Список всех доменов

CATC-отн %* Список всех категорий

CATRC-отн %* Категории и их типы сущностей-вершины

E-отн Список суррогатов для всех заданных типов сущностей

P-отн Непосредственные свойства типа сущностей

PG-отн * Граф свойств

CG-отн * Граф характеристик

AG-отн * Граф ассоциаций

UGI-отн * Граф безусловного обобщения по включению

AGI-отн * Граф альтернативного обобщения по включению

US-отн * Граф безусловных преемников

AS-отн * Граф альтернативных преемников

UP-отн * Граф безусловных предшественников

AP-отн * Граф альтернативных предшественников

KG-отн * Принадлежность типам агрегатов покрытия

Приведем теперь краткую сводку специальных объектов и операторов, которые мы ввели в расширенной реляционной модели. В Таблице I перечислены все объекты, а в Таблице II - алгебраические операторы. В Таблицах используются "атр" и "отн" как сокращения для "атрибут" и "отношение", соответственно.

Множества n-арных отношений были введены как дополнительный тип объектов для алгебраических манипуляций. К этим множествам более высокого порядка применимы традиционные теоретико-множественные операторы UNION (объединение), INTERSECTION (пересечение) и SET DIFFERENCE (разность множеств). К ним могут быть применены также различные другие операторы (например OUTER UNION (внешнее объединение)). Для того чтобы создавать эти множества отношений, манипулировать ими и манипулировать графовыми отношениями, были введены дополнительные операторы (термины "объект-область определения" и "объект-область значений" обозначают область определения и область значений оператора), где множество имен отношений означает унарное отношение, которое является множеством имен_отношений (см. Таблицу II).

Таблица II

Оператор Объект-область определения Объект-область

RM/T значений

NOTE Отношение Имя_отношения

TAG Отношение Отношение

DENOTE Имя_отношения Отношение

Множество имен_отношений Множество отношений

COMPRESS Множество отношений Отношение

APPLY Множество отношений Множество отношений

PATT Отношение Множество отношений

PTUPLE Отношение Множество отношений

PREL Отношение Множество отношений

SETREL Отношение (Отношения) Множество отношений

OPEN Графовое отношение Графовое отношение

CLOSE Графовое отношение Графовое отношение

STEP Графовое отношение Графовое отношение

17. ЗАКЛЮЧЕНИЕ

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

Модель данных, которая может использоваться как:

• концептуальные рамки для определения широкого класса форматированных баз данных;

• посредник между хранимыми представлениями и "взглядами" пользователей;

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

Заметим, что в данной работе представлены только табличные и теоретико-множественные аспекты RM/T. Ясно, что имеется несколько видов графов, которые могут быть ассоциированы с RM/T. Кроме того, помимо представления n-арных отношений гиперграфами, каждое графовое отношение имеет непосредственное представление как ориентированный граф (в определенных случаях с помеченными ребрами).

Исследуются также другие расширения реляционной модели. Например, дополнительная поддержка для временного измерения и режим функционирования с памятью (a nonforgetting mode operation). Есть надежда, что RM/T может быть развита в универсальную реструктурирующую алгебру для баз данных. Следует, однако, напомнить, что расширения в RM/T предназначены, главным образом, для не слишком широкого круга, состоящего из проектировщиков баз данных и изощренных пользователей. Большинство же пользователей, вероятно, предпочтет простоту базисной реляционной модели.

БЛАГОДАРНОСТИ

Автор в значительной мере заимствовал идеи, опубликованные Смит и Смитом; Лакруа и Пироттом; Холлом, Оулеттом и Тоддом; Шмидом и Свенсоном; Хаммером и Маклеодом. Написать эту статью побудили многочисленные высказывания о полезности такой работы, содержащиеся в Трудах конференций IFIP TC-2, состоявшихся в 1976 и 1977 годах [24, 25]. Автор благодарен Вильяму Армстронгу, Дональду Камерону, Кристоферу Дейту, Рональду Фейгину, Джону Сова, Стефану Тодду и рецензентам за полезные замечания по первоначальному варианту этой статьи.

---

ЛИТЕРАТУРА

Замечание: Источники [1, 7, 21, 36] не цитируются в тексте статьи.

1. Aho, A.H., Beeri, C., and Ullman, J. The theory of joins in relational databases. Proc. 19th IEEE Symp. on Foundation of Computer Sci., 1977.

2. Astrahan, M.M., et al. System R: Relational approach to database management. ACM Trans. Database Syst. 1, 2 (June 1976), 97-137.

3. Beeri, C., Bernstein, P., and Goodman, N. A sofisticate"s introduction to database normalization theory. Proc.Int. Conf. on Very Large Data Bases, Berlin, Sept. 1978, pp. 113-124.

4. Cadiou, J.M. On semantic issues in the relational model of date. Proc. 5th Symp. on Math. Foundation of Computer Sci., 1976, Gdansk, Poland, Lecture Notes in Computer Science 45, Springer-Verlag, pp. 23-38.

5. Codd, E.F. A relational model of data for large shared data banks. Comm. ACM 13,6 (June 1970), 377-387. Есть русск. пер.: Е.Ф.Кодд. Реляционная модель данных для больших совместно используемых банков данных. СУБД, # 1, 1995. - с. 145-160.

6. Codd, E.F. Further normalization of the database relational model. In Database Systems, Courant Computer Science Symposia 6, R.Rustin, Ed., Prentice-Hall, Englewood Cliffs, N.Y., 1971, pp. 65-98.

7. Codd, E.F. Recent investigations in relational database systems. Information Processing 74, North-Holland Pub.Co., Amsterdam, 1974, pp. 1017-1021.

8. Codd, E.F. Understanding relations (Unstalment # .7). FDT (Bulletin of ACM SIGMOD) 7, 3-4 (Dec. 1975), 23-28.

9. Codd, E.F. Extending the database relational model. Invited talk presented at the Australian Computer Sci. Conf., Hobart, Tasmania, Feb.1-2, 1979.

10. Fagin, R. Multivalued dependencies and a new normal form for relational databases. ACM Trans. Database Syst., 2, 3 (Sept.1977), 262-278.

11. Fagin, R. Normal forms and relational database operators. Proc. ACM SIGMOD Conf., Boston, Mass., May 30 - June 1, 1979.

12. Falkenberg, E., Concepts for modelling information. In Modelling in Data Base Management Systems, G.M.Nijssen, Ed., North-Holland Pub. Co., Amsterdam, 1976.

13. Goldstein, R.C., and Strnad, A.L. The MACAIMS data management system. Proc. 1970 ACM SIGFIDET Workshop on data Description and Access, Houston, Tex., Nov. 15-16, 1970.

14. Hall, P., Owlett, J., and Todd, S. Relations and Entities. In Modelling in Data Base Management Systems, G.M.Nijssen, Ed., North-Holland Pub. Co., Amsterdam, 1976.

15. Hammer, M.M. and McLeod, D.J. The semantic data model: A modelling mechanism for database applications. Proc. ACM SIGMOD Conf., Austin, Tex., May 31 - June 2, 1978.

16. Heath, I.J. Private communication, April 1971.

17. Hemphill, L.G., and Rhyne, J.R. A model for knowledge representation in natural language query systems. IBM Res. Rep. RJ2304, IBM Res. Lab., San Jose, Calif., Sept. 1978.

18. Hendrix, G.G. Encoding knowledge in partitioned networks. Tech. Note 164, SRI International, Menlo Park, Calif., June 1978.

19. Jordan, D.E. Implementing production systems with relational data bases. Proc. ACM Pacific Conf., San Francisco, Calif., April 1975.

20. LaCroix, M., and Pirotte, A. Generalized joins. SIGMOD Record (ACM) 8, 3 (Sept. 1976), 14-15.

21. LaCroix, M., and Pirotte, A. Example queries in relational languages. Tech. Note # 107, Manufacture Belge de Lampes et de Materiel Electronique, Brussels, Belgium, Jan. 1976, revised Sept. 1977.

22. Lipski, Jr., W. On semantic issues connected with incomplete information databases. ACM Trans. Database Syst. 4, 3 (Sept. 1979), 268-296.

23. Merrett, T.H. Relations as programming language elements. Inform. Processing Lett., 6, 1 (Feb. 1977), 29-33.

24. Nijssen, G.M., Ed., Modelling in Database Management Systems. North-Holland Pub. Co., Amsterdam, 1976.

25. Nijssen, G.M., Ed., Architecture and Models in Database Management Systems. North-Holland Pub. Co., Amsterdam, 1977.

26. Pirotte, A. The entity-property-association model: An information-oriented database model. Rep. R343, Manufacture Belge de Lampes et de Materiel Electronique, Brussels, Belgium, March 1977.

27. Pirotte, A. Linguistic aspects of high-level relational languages. Rep. R367, Manufacture Belge de Lampes et de Materiel Electronique, Brussels, Belgium, Jan. 1978.

28. Reiter, R. On closed world data bases. In Logic and Data Bases. H. Gallaire and J. Minker, Eds., Plenum Press, new York, 1978.

29. Rissanen, J. Independent components of relations. ACM Trans. Database Syst. 2, 4 (Dec. 1977), 317-325.

30. Rissanen, J. Theory of relations for databases - a tutorial survey. proc. Symp. on Math. Foundations of Computer Sci., 1978, Zacopane, Poland, Lecture Notes in Computer Science, Springer-Verlag, pp. 536-551.

31. Roussopoulos, N., and Mylopoulos, J. Using semantic networks for database management. Proc. Int. Conf. on Very Large Databases, Sept. 1975.

32. Schmid, H.A., and Swenson, J.R. On the semantics of the relational data model. Proc. ACM SIGMOD Conf. on Management of data, San Jose, Calif., May 1975, pp.211-223.

33. Smith, J.M., and Smith, D.C.P. Database abstractions: Aggregation. Comm. ACM 20, 6 (June 1977), 405-413.

34. Smith, J.M., and Smith, D.C.P. Database abstractions: Aggregation and Generalization. ACM Trans. Database Syst. 2, 2 (June 1977), 105-133. Есть русск. перевод: Д.М.Смит и Д.К.Смит. Абстракции баз данных: Агрегация и обобщение. СУБД, # 2, 1996. - с. 141-160.

35. Sowa, J.F. Conceptual structures for a database interface. IBM J. Res. Develop. 20, 4 (July 1976), 336-357.

36. Sowa, J.F. Definitional mechanisms for conceptual graphs. Proc. Int. Workshop on Graph Grammars, Bad Honnef, west Germany, Nov. 1978.

37. Stonebraker, M., Wong, E., Kreps, P., and Held, G. The design and implementation of INGRES. ACM Trans. Database Syst. 1, 3 (Sept. 1976), 189-222.

38. Todd, S.J.P. The Peterlee relational test vehicle. IBM Syst. J. 15, 4 (1976), 285-308.

39. Ullman, J.D. Theory of Relational Databases. To appear.

40. Vassiliou, Y. Null values in data base management: A denotational semantics approach. Proc. ACM SIGMOD 1979 Int. Conf. on Management of Data, Boston, Mass., May 30-June 1, 1979.

41. Whitney, V.K.M. RDMS: A relational data management system. Proc. Fourth Int. Symp. on Computer and Inform. Sci., Miami Beach, Fla., Dec. 14-16, 1972, Plenum Press, New York.

42. Wiederhold, G., Database Design. McGraw-Hill, New York, 1977.

43. Wong, H.K.T., and Mylopoulos, J. Two views of data semantics: A survey of data models in artificial intelligence and database management. Informatics 15, 3 (Oct. 1977), 344-383.

44. Zaniolo, C. Analysis and design of relation schemata for database systems. Tech. Rep. UCLA-ENG-7669, Ph.D. Th., Universitet of California at Los Angeles, Los Angeles, Calif., July 1976.

45. Zaniolo, C., and Melkanoff, M.A. A formal approach to the definition and design of conceptual schemas for database systems. To appear in ACM Trans. Database Syst.

46. Zloof, M.M. Query-by-example: A data base language. IBM Syst. J. 16, 4 (1977), 324-343. Есть русск. перевод.: М.М. Злуф. Query-by_example: язык баз данных. СУБД # 3, 1996. - с. 149-160.

---

¹⁾ Э.Кодд имел, вероятно, в виду подготавливаемую в то время к печати и вышедшую в 1980 г. монографию Jeffrey D. Ullman: Principles of Database Systems. Stanford University. Computer Science Press. Есть русск. пер.: Дж. Ульман. Основы систем баз данных. - М.: Финансы и статистика, 1983. - Прим. пер.

^*) E.F. Codd. Extending the Database Relational Model to Capture More Meaning. ACM Transactions on Database Systems, Vol. 4, # 4, December 1979, p. 397-434.

(c) Пер. с англ. М.Р. Когаловского.

Переведено и опубликовано с разрешения АСМ.

(c) 1996 АСМ, INC.