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

2009 г.

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

Э.Ф. Кодд
Перевод: Сергей Кузнецов

Оригинал: IBM Research Report RJ599 (# 12343), August 19, 1969.
Заново опубликовано в ACM SIGMOD Record, March 2009 (Vol. 38, No. 1): E. F. Codd. Derivability, Redundancy and Consistency of Relations Stored in Large Data Banks

От переводчика

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

Аннотация

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

Содержание

Введение

1. Реляционное представление данных

2. Некоторые лигвистические аспекты

3. Операции над отношениями

3.1. Перестановка
3.2. Проекция
3.3. Соединение
3.4. Композиция

4. Выразимые, именованные и хранимые отношения

5. Выводимость, избыточность и согласованность

6. Управление банком данных

Введение

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

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

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

1. Реляционное представление данных

Термин отношение используется здесь в его принятом математическом смысле. Для заданных множеств S_l, S₂, . . . , S_n (не обязательно различных) R является отношением на этих n множествах, если представляет собой некоторое множество n-кортежей, у каждого из которых первый элемент принадлежит S_l, второй – S₂ и т.д. Мы будем называть S_j j-ым доменом R. Определенное выше отношение имеет степень n. Отношения степени 1 часто называют унарными, степени 2 – бинарными, степени 3 – тернарными и степени n – n-арными

Для наглядности мы будем часто использовать представления отношений в виде массивов, однако необходимо помнить, что это частное представление не является существенной частью разъясняемого реляционного представления. У массива, представляющего n-арное отношение R, имеются следующие свойства:

каждая строка представляет некоторый n-кортеж R;
порядок строк не является существенным;
все строки различны;
порядок столбцов является существенным – он соответствует порядку S_l, S₂, . . . , S_n доменов, на которых определено отношение R;
смысл каждого столбца частично передается путем его пометки именем соответствующего домена.

Пример на рис. 1 иллюстрирует отношение степени 4 с именем ship, которое показывает выполняемые поставки деталей в указанных количествах от указанных поставщиков в указанные проекты.

ship supplier part project quantity

1 2 5 17

1 3 5 23

2 3 7 9

2 7 5 4

4 1 1 12

Рис. 1. Отношение степени 4.

Можно было бы задать следующий вопрос: если столбцы помечаются именами соответствующих доменов, то зачем нужна упорядоченность столбцов? Как показывает пример на рис. 2, у двух столбцов могут иметься одинаковые заголовки (что означает одинаковые домены), но они могут они иметь разный смысл для этого отношения. Показанное отношение называется component. Это бинарное отношение, каждый из двух доменов которого называется part. Смысл component (x, y) состоит в том, что деталь x является непосредственным компонентом (или узлом) детали y.

component part part

1 5

2 5

3 5

2 6

3 6

4 7

6 7

Рис. 2. Отношение с двумя одинаковыми доменами.

Далее, мы утверждаем, что банк данных является коллекцией изменяющихся во времени отношений. Эти отношения обладают соответствующими степенями. По мере времени в каждое n-арное отношение могут вставляться новые n-кортежи, из него могут удаляться существующие кортежи, и компоненты любых существующих кортежей могут изменяться. Индивидуальное описание отдельного объекта (например, конкретной детали) называется сущностью [3]. Прототипное описание класса объектов называется типом сущности. Множество сущностей данного типа можно считать отношением, и мы будем называть такое отношение отношением типа сущности. В рассматриваемом ниже примере отношение типа сущности part могло бы определяться на следующих доменах:

part number (номер детали);
part name (название детали);
part color (цвет детали);
part weight (вес детали);
quantity on hand (имеющееся количество);
quantity on order (заказанное количество)

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

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

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

Это помогают понять примеры с рис. 1 и 2. Отношение, показанное на рис. 1, включает три ключа, по одному для каждого из типов сущностей supplier, part, project. Отношение, показанное на рис. 2, включает два ключа, которые относятся к общему типу сущности part. Первый ключ служит для идентификации некоторого компонента, а второй – для идентификации некоторого агрегата, содержащего этот компонент.

До сих пор мы обсуждали примеры отношений, определенных на простых доменах, т.е. доменах, элементами которых являются простые (не разлагаемые на составные части) значения. В рамках реляционного представления можно обсуждать и не атомарные значения. Таким образом, элементами некоторых доменов могут быть отношения. В свою очередь, эти отношения могут быть определена на не простых доменах и т.д. Например, одним из доменов, на котором определяется отношение типа сущности employee (служащий), мог бы быть домен salary history (история зарплаты). Элементом домена salary history является бинарное отношение, определенное на доменах date (дата) и salary (зарплата). Домен salary history представляет собой множество всех таких бинарных отношений.

2. Некоторые лингвистические аспекты

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

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

Класс выражений ограничения, которые можно использовать в спецификации требуемого набора данных, находится в точно заданном взаимнооднозначном соответствии с классом правильно построенных формул исчисления предикатов в предваренной нормальной форме [4]. Средствами H можно определить любую арифметическую функцию, и любую такую функцию можно вызвать средствами R. Специфицированный набор данных может только выбираться из базы данных или удерживаться для возможного выполнения изменений. Вставки новых данных выполняются в виде добавления новых элементов к объявленным отношениям безоотносительно к какому бы то ни было порядку, присутствующему в их машинном представлении. Удаления, которые воздействуют на все сообщество пользователей банка данных (а не на отдельных пользователей или часть их сообщества), выполняются в виде удаления элементов из объявленных отношений. Некоторые удаления могут инициироваться другими удалениями, если средствами R объявляются зависимости по удалению между указываемыми отношениями.

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

Кроме того, если принять реляционное представление, в котором каждое n-арное отношение (n > 2) должно выражаться пользователем как вложенное выражение, включающее только бинарные отношения, то придется использовать 2n-1, а не n+1 имен, которых достаточно при использовании n-арной нотации, описанной в разд. 1. Например, 4-арное отношение ship с рис. 1, содержащее 5 имен в n-арной нотации, представлялось бы во вложенной бинарной нотации в форме

P ( supplier, Q ( part, R ( project, quantity ) ) ),

и в нем использовалось бы 7 имен.

3. Операции над отношениями

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

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

3.1 Перестановка

Для бинарного отношения имеется представление в виде массива с двумя столбцами. Перестановка этих двух столбцов производит обратное отношение. В общем случае, если перестановка применяется к столбцам n-арного отношения, то результирующее отношение называется перестановкой исходного отношения. Например, имеется 4! = 24 перестановки отношения ship с рис. 1, если учитывать тождественную перестановку, не изменяющую порядок столбцов.

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

3.2 Проекция

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

Операция селекции Π используется для получения любой требуемой перестановки, проекции или комбинации этих двух операций. Если L – это список из k индексов

L = i₁, i₂, ..., i_k,

и R – n-арное отношение (n > k), то Π_L(R) – это k-арное отношение, j-ый столбец которого является i_j-ым столбцом R (i = 1, 2, ..., k), не считая того, что в Π_L(R) удалены повторения в результирующих строках. Обратимся к отношению ship с рис. 1. Проекция этого отношения показана на рис. 3.

Π₃₁(ship) project supplier

5 1

5 2

1 4

7 2

Рис. 3. Проекция с перестановкой отношения с рис. 1

Заметим, что в этом частном случае проекция содержит меньше n-кортежей, чем отношение, из которого она порождается.

3.3 Соединение

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

В примере на рис. 4 показаны два отношения R и S, являющиеся соединяемыми без потери информации, а на рис. 5 показано соединение R с S. Бинарное отношение R является соединимым с бинарным отношением S, если существует такое тернарное отношение U, что Π₁₂(U) = R и Π₂₃(U) = S. Любое такое тернарное отношение называется соединением R с S. Если R, S – бинарные отношения, такие что Π₂(R) = Π₁(S), то R является соединимым с S. Одним из соединений, которое всегда в таком случае существует, является естественное соединение, определяемое как

R*S = {(a, b, c):R(a, b) A S(b, c)},

где R(a, b) принимает значение true, если (a, b) входит в R, и аналогично для S(b, c). Из этого определения немедленно следует, что

Π₁₂(R*S) = R

Π₂₃(R*S) = S.

Заметим, что соединение, показанное на рис. 5, является естественным соединением R с S с рис. 4. Однако оно не является единственным соединением R с S. На рис. 6 показано еще одно возможное соединение отношений с рис. 4.

R ( supplier part ) S ( part project )

1 1 1 1

2 1 1 2

2 2 2 1

Рис. 4. Два соединимых отношения

R*S ( supplier part project )

1 1 1

1 1 2

2 1 1

2 1 2

2 2 1

Рис. 5. Естественное соединение R с S (с рис. 4)

R*S ( supplier part project )

1 1 2

2 1 1

2 2 1

Рис. 6. Еще одно соединение R с S (с рис. 4)

При обследовании этих отношений обнаруживается некоторый элемент (элемент 1) домена part (домена, по которому производится соединение), обладающий тем свойством, что он встречается более одного раза и в R, и в S. И именно этот элемент приводит к множественности соединений. Такой элемент домена соединения называется точкой неоднозначности по отношению к соединению R с S.

Если либо Π₂₁(R), либо S является функцией³, то при соединении R с S не может возникнуть никакой точки неоднозначности. В этом случае единственным соединением R с S является естественное соединение. Заметим, что повторяющееся уточнение "R с S" является необходимым, поскольку S могло бы быть соединимым с R (как и R с S), и это соединение потребовало бы совершенно отдельного рассмотрения. На рис. 4 ни одно из отношений R, Π₂₁(R), S, Π₂₁(S) не является функцией.

Неоднозначность при соединении R с S иногда можно разрешить при помощи других отношений. Предположим, что имеется или может быть выведено из других источников, независимых от R и S, отношение T на доменах project и supplier со следующими свойствами:

Π₁(T) = Π₂(S);
Π₂(T) = Π₁(R);
T(j, s) → p(R(s, p) ∧ S(p, j));
R(s, p) → j(S(p, j) ∧ T(j, s));
S(p, j) → s(T(j, s) ∧ R(s, p)).

Тогда мы можем построить трехстороннее соединение отношений R, S, T, т.е. тернарное отношение U, такое что

Π₁₂(U) = R;
Π₂₃(U) = S;
Π₃₁(U) = T.

Такое соединение мы будем называть циклическим 3-соединением, чтобы отличать его от линейного 3-соединения, которое является кватернарным отношением V, таким что

Π₁₂(V) = R;
Π₂₃(V) = S;
Π₃₄(V) = T.

Хотя может существовать более одного циклического 3-соединения (см., например, рис. 7 и 8), условия, при которых это может случиться, включают намного более строгие ограничения, чем те, которые допускают множественность 2-соединений. Более точно, R, S, T должны содержать точки неоднозначности по отношению к соединению R с S (скажем, точку x), S с T (скажем, y) и T с R (скажем, z). Кроме того, точка y должна быть связана с точкой x в S, точка z с точкой y – в T, и точка x с точкой z – в R. Заметим, что на рис. 7 этим свойством обладают точки

x = a; y = d; z = 2.

R ( s p ) S ( p j ) T ( j s )

1 a a d d 1

2 a a e d 2

2 b b d e 2

b e

Рис. 7. Бинарные отношения с несколькими циклическими 3-соединениями

U ( s p j ) U' ( s p j )

1 a d 1 a d

2 a e 2 a d

2 b d 2 a e

2 b e 2 b d

2 b e

Рис. 8. Два циклических 3-соединения отношений с рис. 7

Естественное линейное 3-соединение трех бинарных отношений R, S, T определяется следующим образом:

R*S*T = {(a, b, c, d):R(a, b) ∧ S(b, c) ∧ T(c, d)}.

Скобки в левой части не требуются, поскольку естественное 2-соединение (*) ассоциативно. Для получения циклического варианта естественного 3-соединения мы вводим операцию γ, которая производит отношение степени n-1 из отношения степени n путем связывания его крайних точек. Более точно, если R является n-арным отношением, то

γ(R) = ((a_l, a₂, . . . , a_n-l):R(a_l, a₂, . . . , a_n-l, a_n) ∧ a_l = a_n).

Тогда естественное циклическое 3-соединение отношений R, S, T можно представить выражением

γ(R*S*T).

Очевидным образом понятия линейного и циклического 3-соединений и из естественных вариантов расширяются на случай соединения n бинарных отношений (где n ≥ 3). Однако стоит сказать несколько слов по поводу соединения отношений, которые необязательно являются бинарными. Рассмотрим случай, в котором отношения R (степени r) и S (степени s) соединяются по p своим доменам (p < r, p < s). Для простоты предположим, что эти p доменов являются последними p из r доменов R и первыми p из s доменов S. Если бы это было не так, мы всегда могли бы добиться этого, применив соответствующие перестановки. Теперь образуем декартово произведение первых r-p доменов R и назовем полученное множество новым доменом A. Аналогично, возьмем декартово произведение последних p доменов R и назовем его доменом B. Возьмем декартово произведение последних s-p доменов S и назовем его C.

Теперь мы можем трактовать R как бинарное отношение на доменах A, B. Аналогично, мы можем трактовать S как бинарное отношение на доменах B, C. В такой трактовке к отношениям непосредственно применимы понятия линейного и циклического 3-соединения. Аналогичный подход можно применить для определения линейного и циклического n-соединения n отношений произвольных степеней.

3.4 Композиция

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

Предположим, что имеются два отношения R и S. T является композицией (composition) R с S, если существует соединение U отношения R с отношением S, такое что T = Π₁₃(U). Таким образом, два отношения являются композируемыми тогда и только тогда, когда они являются соединимыми. Однако из существования более чем одного соединения R с S не следует существование более чем одной композиции R с S.

Естественному соединению R с S соответствует естественная композиция R с S, определяемая следующим образом:

R•S = Π₁₃(R*S).

Для отношений R и S c рис. 4 на рис. 9 показана естественная композиция R с S, а на рис. 10 – другая возможная композиция (основанная на соединении, показанном на рис. 6).

R•S ( project supplier )

1 1

1 2

2 1

2 2

Рис. 9. Естественная композиция R с S (с рис. 4)

R*S ( project supplier )

1 2

2 1

Рис. 10. Еще одна композиция R с S (с рис. 4)

Если существует два или большее число соединений, то число различных композиций может варьироваться от единицы до числа различных соединений. На рис. 11 показан пример двух отношений, у которых имеется несколько соединений, но только одна композиция. Заметим, что точка неоднозначности c утрачивается при композиции R с S, поскольку через точки a, b, d, e устанавливаются однозначные связи.

R ( supplier part ) S ( part project )

1 a a g

1 b b f

1 c c f

2 c c g

2 d d g

2 e e f

Рис. 11. Много соединений, только одна композиция

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

4. Выразимые, именованные и хранимые отношения

В состав банка данных входят три коллекции отношений:

набор выразимых (expressible) отношений;
набор именованных (named) отношений;
набор хранимых (stored) отношений.

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

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

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

Те отношения, которые содержатся в наборе именованных отношений, но не содержатся в наборе хранимых отношений, определяются (не зависящими от времени) выражениями, включающими имена хранимых отношений, а также операции перестановки-проекции, естественной композиции, естественного соединения и связывания (Π, •, *, γ). Такие определения выражений должны быть ограничены возможностями языка выборки R.

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

5. Выводимость, избыточность и согласованность

Отношение R является выводимым из набора отношений S, если существует последовательность⁴ перестановок, проекций, естественных соединений и связываний, которая производит R из членов набора S. Эта последовательность операций производит корректное значение R практически в любой момент времени (для хранимых отношений необходимо исключить те интервалы времени, в которые значения R и S изменяются). Заметим, что поскольку в списке операций указано естественное соединение, не возникает вопроса, какое соединение нужно использовать.

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

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

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

В качестве примера слабой избыточности еще раз обратимся к трем бинарным отношениям R, S, T, смысл которых состоит в следующем:

R(s, p) – поставщик s поставляет деталь p, по крайней мере, в один проект.
S(p, j) – деталь p поставляется в проект j, по крайней мере, одним поставщиком.
T(j, s) – в проект j поставщиком s поставляется, по крайней мере, один вид деталей.

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

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

При наличии заданного набора отношений C и связанного с ним набором ограничивающих утверждений мы будем называть C согласованным или несогласованным в зависимости от того, соответствует ли C этим утверждениям. Например, при наличии хранимых отношений R, S, T и ограничивающего утверждения

"Π₁₂(T) является композицией Π₁₂(R) с Π₁₂(S)"

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

Π₁(T) = Π₁(R);
Π₂(T) = Π₂(S);
для каждой пары элементов (a, c) в отношении Π₁₂(T) имеется такой элемент b, что (a, b) содержится в Π₁₂(R) и (b, c) содержится в Π₁₂(S).

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

6. Управление банком данных

Несогласованности в наборе отношений могут являться результатом неадекватного или ошибочного ввода данных. Примером неадекватного ввода является вставка нового элемента, скажем, (2, 5), в отношение S (part, project), когда для детали 2 отсутствует поставщик, поставляющий детали в проект 5 (см. предыдущий раздел). Порождение несогласованности можно было бы регистрировать внутри системы, чтобы, если бы она не устранялась в течение некоторого разумного интервала времени путем соответствующих вставок в отношения R, T, система могла повестить об этом ответственного за безопасность. В качестве другого варианта система могла бы помогать пользователю производить вставки и удаления, информируя его, что для восстановления согласованности набора отношений требуется изменить такое-то и такое-то отношения. В идеальном случае должна была бы иметься возможность выбора разных видов реакции системы на несогласованность разных поднаборов отношений в конкретном банке данных.

Благодарность

Автор хочет поблагодарить доктора Ф.П. Палермо (F.P. Palermo) и доктора Э.Б. Альтмана (E.B. Altman) из Исследовательской лаборатории в Сан-Хосе за полезные обсуждения.

Литература

1. C.W. Bachman, "Software for Random Access Processing", Datamation, April 1965.
2. W.C. McGee, "Generalized File Processing", Annual Review in Automatic Programming 5, 13, pp. 77-149, Pergamon Press, 1969.
3. G.H. Mealy, "Another Look at Data", Proceedings Fall Joint Computer Conference, 1967.
4. A. Church, "An Introduction to Mathematical Logic I", Princeton, 1956.

¹⁾ Здесь требуется исчисление предикатов второго порядка (а не первого), поскольку домены, на которых определяются отношения, могут сами содержать в качестве своих элементов отношения (см. разд. 1).

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

³⁾ Функция – это бинарное отношение "многие-к-одному".

⁴⁾ Мы можем опустить в списке операций естественную композицию, поскольку она является комбинацией соединения и проекции.

⁵⁾ Бинарное отношение является сложным, если ни оно само, ни обратное к нему отношение не является функцией.