Реляционная модель данных для больших совместно используемых банков данных

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

Источник: журнал Системы Управления Базами Данных # 1/1995, издательский дом «Открытые системы»
Новая редакция: Сергей Кузнецов, 2009 г.

Оригинал: E.F. Codd. A Relational Model of Data for Large Shared Data Banks. Communications of the ACM, Volume 13, Number 6, June, 1970. Текст доступен здесь.

Содержание

1. Реляционная модель и нормальная форма

1.1. Введение

1.2. Зависимости данных в существующих системах

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

1.4. Нормальная форма

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

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

2. Избыточность и согласованность

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

2.2. Избыточность

2.3. Согласованность

2.4. Заключение

Литература

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

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

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

1. Реляционная модель и нормальная форма

1.1. Введение

Эта статья посвящается применению элементарной теории отношений к системам, которые обеспечивают совместный доступ к большим банкам форматированных данных. За исключением статьи Чайлдса (Childs) [1], основной областью применения отношений к системам данных являются дедуктивные системы ответов на вопросы. В статье Ливейна (Levein) и Марона (Maron) [2] приводятся многочисленные ссылки на работы в этой области.

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

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

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

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

1.2. Зависимости данных в существующих системах

Обеспечение таблиц описания данных в разрабатываемых сегодня системах является существенным продвижением на пути к независимости данных [5,6,7]. Наличие таких таблиц облегчает изменения некоторых характеристик представления данных, хранимых в банках данных. Однако набор характеристик представления данных, которые могут быть изменены без нанесения логического ущерба некоторым прикладным программам, продолжает оставаться ограниченным. Далее, модель данных, с которыми работают пользователи, по-прежнему загромождается характеристиками представления; в особенности это касается представлений коллекций данных (а не одиночных элементов данных). Тремя основными видами зависимости данных, которые все еще требуется устранить, являются зависимость порядка, зависимость индексации и зависимость путей доступа. В некоторых системах эти зависимости четко не отделены одна от другой.

1.2.1. Зависимость порядка. Элементы данных в банке данных могут храниться разными способами, некоторые из которых не предполагают наличия какого-либо порядка, некоторые допускают участие каждого элемента только в одном порядке, а некоторые – в нескольких порядках. Обратим внимание на те существующие системы, в которых требуется или хотя бы допускается хранение элементов данных, по крайней мере, в одном полном порядке, тесно связанном с зависимым от аппаратуры порядком адресов. Например, записи в файле, описывающем детали, могут храниться в порядке убывания серийных номеров. В таких системах обычно допускается, чтобы прикладные программы основывались на предположении о том, что порядок представления записей идентичен порядку их хранения (или является его частью). Эти прикладные программы, использующие свойства упорядоченности файла, скорее всего не смогут правильно работать, если по какой-то причине потребуется изменить этот порядок. Аналогичные замечания остаются в силе для случая, когда порядок хранения реализуется посредством указателей.

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

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

В современных системах форматированных данных применяются разнообразные подходы к индексации. В TDMS [7] обеспечивается обязательная индексация по всем атрибутам. В текущей версии IMS [5] пользователю предоставляется выбор для каждого файла: между полным отсутствием индексации (иерархическая последовательная организация) и индексацией только по первичному ключу (иерархическая индексно-последовательная организация). Ни в одном из этих случаев логика пользовательского представления не зависит от обязательно поддерживаемых индексов. Однако в IDS [8] проектировщикам файлов предоставляется возможность выбора индексных атрибутов и добавления индексов в структуру файла с использованием средств дополнительных цепочек. Прикладные программы, в которых для повышения эффективности используются эти индексные цепочки, должны ссылаться на них по именам. Такие программы не смогут работать правильно, если эти цепочки будут впоследствии удалены.

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

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

 
Структура 1. Проекты подчинены Деталям

Файл	Сегмент	Поля
F	ДЕТАЛЬ	номер детали
		наименование детали
		описание детали
		имеющееся количество
		заказанное количество
	ПРОЕКТ	номер проекта
		наименование проекта
		описание проекта
		подтвержденное количество

 
Структура 2. Детали подчинены Проектам

Файл	Сегмент	Поля
F	ПРОЕКТ	номер проекта
		наименование проекта
		описание проекта
	ДЕТАЛЬ	номер детали
		наименование детали
		описание детали
		имеющееся количество
		заказанное количество
		подтвержденное количество

 
Структура 3. Детали и Проекты наравне, Связь назначения деталей проектам подчинена Проектам

Файл	Сегмент	Поля
F	ДЕТАЛЬ	номер детали
		наименование детали
		описание детали
		имеющееся количество
		заказанное количество
G	ПРОЕКТ	номер проекта
		наименование проекта
		описание проекта
	ДЕТАЛЬ	номер детали
		подтвержденное количество

 
Структура 4. Детали и Проекты наравне, Связь назначения деталей проектам подчинена Деталям

Файл	Сегмент	Поля
F	ДЕТАЛЬ	номер детали
		наименование детали
		описание детали
		имеющееся количество
		заказанное количество
	ПРОЕКТ	номер проекта
		подтвержденное количество
G	ПРОЕКТ	номер проекта
		наименование проекта
		описание проекта

 
Структура 5. Детали, Проекты и Связь назначения деталей проектам наравне

Файл	Сегмент	Поля
F	ДЕТАЛЬ	номер детали
		наименование детали
		описание детали
		имеющееся количество
		заказанное количество
G	ПРОЕКТ	номер проекта
		наименование проекта
		описание проекта
H	ПОДТВЕРЖДЕНИЕ	номер детали
		номер проекта
		подтвержденное количество

Теперь рассмотрим задачу выборки номера детали, названия детали и количества деталей этого типа для каждой детали, используемой в проекте с названием "альфа". Следующие наблюдения могут быть сделаны независимо от того, какая конкретная информационная система с древовидной организацией информации выбирается для решения этой задачи. Если для этого разрабатывается программа P, ориентированная на использование одной из приведенных выше структур (т.е. P не определяет, какова реальная структура представления данных), то при любом выборе P не сможет работать, по меньшей мере, с тремя потенциально возможными структурами. Более точно, если P следует структуре 5, то ей не удастся работать со всеми другими структурами; если PP следует структуре 3 или 4, то ей, по меньшей мере, не удастся работать со структурами 1,2 и 5; если P следует структуре 1 или 2, ей, как минимум , не удастся работать со структурами 3, 4 и 5. В каждом случае причина проста. Если отсутствуют проверки для определения реально заданной структуры, то работа P заканчится неудачей по причине попытки перехода по ссылке к несуществующему файлу (в доступных сегодня системах это трактуется как ошибка) или из-за отсутствия перехода по ссылке к файлу, содержащему нужную информацию. Читателю, который в этом сомневается, рекомендуется написать пробные программы для решения этой простой задачи.

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

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

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

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

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

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

1. Каждая строка представляет кортеж степени n.
   
2. Порядок строк не является существенным.
   
3. Все строки различны.
   
4. Порядок столбцов является существенным – он соответствует порядку S₁, S₂,..., S_n доменов, на которых определяется R (однако обратите внимание на приводимые ниже замечания по поводу отношений с упорядоченными и неупорядоченными доменами).
   
5. Значимость каждого столбца частично выражается посредством его пометки именем соответствующего домена.

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

поставка	(поставщик	деталь	проект	количество)
	1	2	5	17
	1	3	5	23
	2	3	7	9
	2	7	5	4
	4	1	1	12

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

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

компонент	(деталь	деталь	количество)
	1	5	9
	2	5	7
	3	5	2
	2	6	12
	3	6	3
	4	7	1
	6	7	1

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

Примечательным фактом является то, что некоторые современные системы (главным образом, те, которые основываются на файлах с древовидной структурой) не в состоянии обеспечить представление данных для отношений, которые имеют два или более одинаковых домена. Примером такой системы является текущая версия IMS/360 [5].

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

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

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

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

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

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

1. номер детали;
   
2. наименование детали;
   
3. цвет детали;
   
4. вес детали;
   
5. количество имеющихся деталей;
   
6. количество заказанных деталей.

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

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

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

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

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

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

1.4. Нормальная форма

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

Рассмотрим, например, набор отношений, приведенный на рис.3(а). История работы и дети – непростые домены отношения служащий. История зарплаты – непростой домен отношения история работы. На дереве на рис.3(а) показаны именно эти взаимосвязи указанных непростых доменов.

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

Рисунок 3(a). Ненормализованное множество

служащий' (номер_служащего, имя, дата_рождения)
история_работы' (номер_служащего, дата_приема_на_работу, название)
история_зарплаты' (номер_служащего, дата_приема_на_работу, дата_назначения_зарплаты, зарплата)
дети' (номер_служащего, имя_ребенка, год_рождения)

Рисунок 3(б). Нормализованное множество

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

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

Чтобы можно было применить описанную нормализации, ненормализованный набор отношений должен удовлетворять следующим условиям:

1. Граф взаимосвязей непростых доменов должен являться набором деревьев.
   
2. Ни один первичный ключ не должен включает в себя непростые домены.

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

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

1. Передаваемая форма не содержала бы указатели (со значениями – адресами или смещениями).
   
2. В ней отсутствовали бы все зависимости от схемы хэш-адресации.
   
3. Она не содержала бы какие-либо индексы или упорядоченные списки.

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

R(g).r.d

где R – имя отношения, g – необязательное имя поколения, r – необязательное имя роли, d – имя домена. Поскольку g необходимо только в случае существования или ожидаемого появления нескольких поколений данного отношения, а r необходимо только, если отношение R имеет два или более доменов с именем d, простая форма R.d часто будет достаточной.

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

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

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

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

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

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

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

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

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

Опять-таки, если принять реляционное представление, в котором каждое n-арное отношение (n>2) должно быть описано пользователем как вложенное выражение, включающее только бинарные отношения (см., например, LEAP System Фельдмана (Feldman) [10]), то вместо всего лишь n+1 имен при использовании прямой n-арной нотации, описанной в разделе 1.2, потребуется образовать 2n-1 имен. Например, 4-арное отношение поставка, приведенное на рис.1 и содержащее 5 имен в n-арной нотации, во вложенной двоичной нотации было бы представлено в виде

P ( поставщик, Q ( деталь, R( проект, количество)))

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

Другим недостатком такого представления является его асимметрия. Несмотря на то, что эта асимметрия не препятствует симметричному использованию, она, определенно, составляет некую основу для запросов, которые трудно формулировать пользователям (попробуйте, например, выразить с использованием Q и R запрос о том, какие детали и в каком количестве используются в данном проекте).

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

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

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

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

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

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

2. Избыточность и согласованность

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

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

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

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

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

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

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

Оператор селекции π используется для получения любой требуемой перестановки, проекции или комбинации этих операций. Так, если L – список из k значений⁷⁾ L = i₁, i₂,...,i_k, и R – n-арное отношение (n≥k), то π_L (R) есть k-арное отношение, j-тый столбец которого есть i_j-тый столбец R (i=1,2,...,k) и в котором удалены дубликаты результирующих строк. Рассмотрим отношение поставка на рис.1. Перестановка проекции этого отношения приведена на рис.4. Заметьте, что в этом частном случае проекция имеет меньше n-кортежей, чем исходное отношение.

π31(поставка)	(проект	поставщик)
	5	1
	5	2
	1	4
	7	2

Рисунок 4. Перестановка проекции отношения c рис.1

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

В примере на рис.5 показаны два отношения R и S, которые могут быть соединены без потери информации, а на рис.6 представлен результат соединения 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) ∧ S(b,c)},

где R(a,b) имеет значение истина, если (a,b) является элементом R, и S(b,c) – аналогично. Очевидно, что

π₁₂(R*S) = R

и

π₂₃(R*S) = S.

Заметим, что соединение, показанное на рис.6, является естественным соединением отношений R и S, представленных на рис.5. Другое соединение показано на рис.7.

R	(поставщик	деталь)	S(деталь	проект)
	1	1	1	1
	2	1	1	2
	2	2	2	1

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

R*S	(поставщик	деталь	проект)
	1	1	1
	1	1	2
	2	1	1
	2	1	2
	2	2	1

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

U	(поставщик	деталь	проект)
	1	1	2
	2	1	1
	2	2	1

Рисунок 7. Другое соединение R и S (рис.5)

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

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

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

1. π₁(T) = π₂(S)
   
2. π₁(T) = π₁(R)
   
3. T(j,s) → ∃p(R(s,p) ∧ S(p,j)
   
4. R(s,p) → ∃j(S(p,j) ∧ T(j,s)
   
5. S(p,j) → ∃s(T(j,s) ∧ R(s,p)

В этом случае мы можем построить соединение трех отношений R, S, T, то есть тернарное отношение такое, что

π₁₂(U)=R, π₂₃(U)=S, π₃₁(U)=T

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

π₁₂(V)=R, π₂₃(V)=S, π₃₄(V)=T.

Поскольку возможно существование более чем одного циклического 3-соединения (см., например, рис.8,9), обстоятельства, при которых это может происходить, накладывают гораздо более сильные ограничения, чем условия множественности 2-соединений. Более точно, отношения R, S, T должны содержать точки неоднозначности соединений R и S (скажем, точка x), S и T (скажем, y) и T и R ( скажем, z) и, более того, y должно соответствовать x в S, z соответствовать y в T и x соответствовать z в R. Заметьте, что на рис.8 точки 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	e 2

Рисунок 8.Бинарные отношения с несколькими циклическими 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

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

Естественное линейное соединение трех бинарных отношений R, S, T определяется так:

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

где скобки в левой части равенства не нужны, т.к. естественное 2-соединение (*) ассоциативно. Для получения циклического аналога мы введем оператор ν, выдающий в качестве результата отношение степени n-1 из отношения степени n, связывая вместе его концы. Если R есть n-арное отношение (n≥2), то связывание R определяется уравнением

ν(R) = { (a₁, a₂, ....,a_n-1) : R(a₁, a₂, ...., a_n-1, a_n) ∧ a₁=a_n}

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

ν(R*S*T).

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

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

2.1.4. Композиция. Читатель, возможно, знаком с понятием композиции применительно к функциям. Мы обсудим обобщение этого понятия и применим его вначале к бинарным отношениям. Наши определения композиции и композиционности основаны непосредственно на определениях соединения и соединимости, приведенных выше.

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

Для естественного соединения R и S существует естественная композиция,⁹⁾ определяемая как

R · S = π₁₃ (R*S) .

Естественная композиция отношений R и S, приведенных на рис. 5, показана на рис.10, другая композиция приведена на рис.11 (получена из соединения, представленного на рис.7).

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

R · S	(проект	поставщик)
	1	1
	1	2
	2	1
	2	2

Рисунок 10. Естественная композиция отношений R и S (показанных на рис.5)

T	(проект	поставщик)
	1	2
	2	1

Рисунок 11. Другая композиция отношений R и S (показанных на рис.5)

R	(поставщик	деталь)	S	(деталь	проект)
	1	a		a	g
	1	b		b	f
	1	c		c	f
	2	c		c	g
	2	d		d	g
	2	e		e	f

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

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

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

2.1.5. Ограничение. Подмножество отношения является отношением. Один из способов воздействия отношения S на отношение R для получения подмножества R заключается в применении операции ограничения отношения R по отношению S. Эта операция является обобщением ограничения функции на подмножество ее области определения и определяется следующим образом.

Пусть L, M – списки индексных значений одинаковой длины такие, что L = i₁, i₂,..., i_k, M = j₁, j₂, ..., j_k, где k≤ степень R и k≤ степень S. Тогда L,M-ограничение R по S, обозначаемое как R_L|_MS, есть максимальное подмножество R' множества R, такое, что

π_L(R') = π_M (S).

Эта операция определена только в том случае, если применима операция равенства между элементами π_ih( R), с одной стороны и p_jh(S), с другой, для всех h=1,2,...k.

Три отношения R, S, R', приведенные на рис.13, удовлетворяют соотношению R'=R_(2,3)|_(1,2)S.

R ( s р j )	S( р j )	R"( s р j )
1 a A	a A	1 a A
2 a A	c B	2 a A
2 a B	b B	2 b B
2 b A
2 b B

Рисунок 13. Пример ограничения

Теперь мы готовы рассмотреть различные применения этих операций над отношениями.

2.2. Избыточность

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

Предположим, что θ – это набор операций над отношениями, и каждая операция обладает тем свойством, что вырабатывает единственное отношение из своих операндов (т.е. естественное соединение допустимо, а соединение нет). Отношение R является θ-выводимым из множества отношений S, если существует последовательность операций из набора θ, которая "в любой момент времени" производит R из элементов S. Фраза "в любой момент времени" присутствует потому, что мы рассматриваем изменяющиеся во времени отношения, и для нас представляет интерес свойство порождаемости, сохраняющееся в течение длительного периода времени. Для набора именованных связей в системах без логического вывода достаточный набор θ₁ содержит следующие операции: проекция, естественное соединение, связывание и ограничение. Перестановка неуместна, а естественную композицию включать не требуется, т.к. ее можно получить путем естественного соединения с последующей проекцией. Для хранимого множества представлений достаточный набор θ₂ должен включать перестановку и дополнительные операции, связанные с получением подмножеств и слиянием отношений, упорядочиванием и связыванием их элементов.

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

служащий (номер, имя, номер_менеджера, имя_менеджера)

где номер является первичным ключом, и номер_менеджера является внешним ключом. Обозначим активный домен через Δ_t и предположим, что

Δ_t (номер_менеджера) ⊂ Δ_t (номер)

и

Δ_t (имя_менеджера) ⊂ Δ_t (имя)

в любой момент времени t. В этом случае избыточность очевидна: домен имя_менеджера не является необходимым. Чтобы убедиться в том, что эта избыточность является сильной избыточностью в соответствии с приведенным выше определением, заметим, что

π₃₄ (служащий) = π₁₂ (служащий)₁|₁π₃(служащий).

Во втором примере набор отношений включает описывающее поставщиков отношение S с первичным ключом s#, описывающее отделы отношение D с первичным ключом d# и описывающее проекты отношение J с первичным ключом j#, а также следующие отношения:

P(s#, d#,...), Q(s#, j#,...), R(d#, j#,...),

где в каждом случае многоточие означает домены, отличающиеся от s#, d#, j#. Предположим, что удовлетворяется следующее не зависящее от времени условие C: поставщик s обслуживает отдел d (отношение P) тогда и только тогда, когда поставщик s обслуживает некоторый проект j# (отношение Q), который выполняется отделом d# (отношение R). Тогда мы можем записать соотношение

π₁₂(P) = π₁₂ (Q) · π₂₁ (R)

и таким образом показать наличие сильной избыточности.

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

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

Мы можем проиллюстрировать слабую избыточность, рассмотрев второй пример сильной избыточности (из приведенных выше) и предположив, что условие C в некоторые моменты времени не выполняется. Отношения π₁₂(P), π₁₂(Q), π₁₂(R) являются сложными ¹⁰⁾ отношениями с возможным существованием точек неоднозначности, появляющихся иногда в потенциальных соединениях каких-либо двух отношений. При этих условиях ни одно из них не порождается из двух других. Однако между ними существует зависимость, поскольку каждое из них является проекцией некоторого циклического соединения трех отношений. Один из видов слабой избыточности может быть охарактеризован следующим утверждением: в любой момент времени π₁₂(P) является некоторой композицией π₁₂(Q) и π₂₁(R). Эта композиция может быть естественной при одних обстоятельствах и может не являться таковой при других.

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

2.3. Согласованность

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

Для данного набора C изменяемых во времени отношений, ассоциированного с ним множества Z ограничительных утверждений и значения V набора C в какой-либо момент времени мы будем называть состояние (C, Z, V) согласованным или несогласованным в зависимости от того, удовлетворяет ли V набору условий Z или нет. Например, для набора хранимых отношений R,S,T вместе с ограничительным утверждением "π₁₂(T) является композицией π₁₂ (R) и π₁₂ (S)" мы можем периодически проверять, что значения, хранящиеся в R,S,T, удовлетворяют этому условию. Алгоритм осуществления такой проверки должен просматривать первые два столбца каждого из отношений R,S,T (вне зависимости от способа их представления в системе) и определять, выполняются ли следующие условия

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

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

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

Предположим, что множество именованных отношений C содержит отношения S, J, D, P, Q, R из примера раздела 2.2, и что P, Q, R обладают сильной или слабой избыточностью в определенном выше смысле (в рассматриваемом нами случае не важно, какая именно избыточность имеет место). Далее, предположим, что в некоторый момент времени t банк данных находится в согласованном состоянии и не содержит никакого проекта j такого, что поставщик 2 обслуживает проект j, и проект j ведется отделом 5. Соответственно, в π₁₂(P) не существует элемента (2,5). Пусть теперь пользователь вводит элемент (2,5) в π₁₂(P), вставляя соответствующий элемент в P. В этот момент состояние банка данных является несогласованным. Эта несогласованность могла возникнуть вследствие оплошности, если появление (2,5) является правильным, и действительно существует проект j такой, что поставщик 2 обслуживает проект j и проект j ведется отделом 5. В этом случае очень вероятно, что пользователь собирается в ближайшем будущем добавить элементы в Q и R, результатом чего явится появление (2,j) в π₁₂(Q) и (5,j) в π₁₂(R). С другой стороны, ввод (2,5) мог быть ошибочным. Так могло бы получиться, если бы пользователь намеревался вставить в P некоторый другой элемент, появление которого перевело бы согласованное состояние в согласованное состояние. Суть в том, что как правило, в системе будут отсутствовать средства разрешения этого вопроса без опроса окружения системы (например, пользователя, породившего несогласованность).

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

2.4. Заключение

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

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

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

Благодарности. C.T. Davis из IBM Poughkeepsie убедил автора в необходимости независимости данных в будущих информационных системах. Автор выражает благодарность ему и, также, F.P.Palermo, C.P.Wang, E.B.Altman и M.E.Senko из IBM San Jose Research Laboratory за полезные обсуждения.

Получена в сентябре 1969 г., пересмотрена в феврале 1970 г.

Литература

1. Childs, D.L. Feasibility of a set-theoretical data structure – a general structure based on a reconstituted definition of relation. proc. IFIP Cong., 1968, North Holland Pub. Co., Amsterdam, р. 162-172.
2. Levein, R.E., and Maron, M.E. A computer system for inference execution and data retrieval. Comm. ACM 10,11 (Nov. 1967), 715-721.
3. Bachman, C.W. Software for random access processing. Datamation (Apr. 1965), 36-41.
4. McGee, W.C. Generalized file processing. In Annual Review in Automatic Programming 5, 13, Pergamon Press, New York, 1969, рр. 77-149.
5. Information Management System/360, Application Description Manual H20-0524-1. IBM Corp., White plains, N.Y., July 1968.
6. GIS (Generalized Information System), Application Description Manual H20-0574. IBM Corp., White Plains, N.Y., 1965.
7. Bleier, R.E. Treating hierarchial data structures in the SDC time-shared data management system (TDMS). Proc. ACM 22nd Nat. Conf., 1967, MDI Publications, Wayne, pa., рр. 41-49.
8. IDS Reference Manual GE 625/635, GE Inform. Sys. Div., Pheonix, Ariz., CPB 1093B, Feb. 1968.
9. Church, A. An Introduction to Mathematical Logic I. Princeton U. Press, Princeton, N.J., 1956.
10. Feldman, J.A., and Rovner, P.D. An Algol-based associative language. Stanford Artificial Intelligence Rep. AI-66, Aug. 1, 1968.

---

¹⁾ Более точно, R является подмножеством Декартова произведения S₁ × S₂ × ... × S_n.

²⁾ Говоря математическим языком, связь - это класс эквивалентности отношений, эквивалентных относительно перестановки доменов (См. п.2.1.1).

³⁾ Естественно, пользователь производит ввод данных в компьютерную систему и их выборку гораздо более эффективно, если он понимает смысл данных.

⁴⁾ М.Е. Сенко из IBM, Сан-Хосе, независимо указывает на желательность устранения непростых доменов.

⁵⁾ Работа с отношением включает запросы, обновление и удаление.

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

⁷⁾ При работе со связями мы используем имена доменов (в случае необходимости уточненные именами ролей) вместо позиций доменов.

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

⁹⁾ Другие авторы склоняются к игнорированию композиций, отличных от естественной, и, соответственно, называют композицией именно этот частный случай – см., например, "Общую топологию" Келли.

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