Структуры зависимостей в отношениях баз данных

2019 г.

Структуры зависимостей в отношениях баз данных

Вильям Армстронг
Перевод: С.Д. Кузнецов

Dependency Structures of Data Base Relationships

William Ward Armstrong
Départemendt Informatique Universite de Montréal Montréal, Québec, Canada

Proceedings of IFIP Congress 74, Stockholm, Sweden, August 5-10, 1974. North-Holland, 1974, pp. 580-583

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

1. Введение

Понятие отношения^[1] было разработано как мощное средство представления форматированных данных на логическом уровне, пригодное для обмена данными между информационными системами и использования в прикладных программах [1,2,3]. Для пользователей систем управления информацией этот подход является естественным, поскольку они давно привыкли к представлению данных в виде таблиц. Любое отношение, хотя и определяется на абстрактном уровне на основе множеств и функций, может быть конкретно изображено в виде таблицы, состоящей из строк, каждая из которых представляет задание значений атрибутам, указанным в заголовках столбцов (например, ‘NAME’, ‘AGE’, ‘HEIGHT’ и т.д.). Администраторам баз данных и разработчикам систем легко и просто взаимодействовать с такой логически прозрачной структурой информации. Им обеспечивается большая свобода при выборе экономичных данных и структур хранения в зависимости от частоты доступа к разным частям данных и характеристик используемых машин.

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

Мы надеемся, что это исследование позволит специалистам в области реляционных моделей данных использовать точные понятия и терминологию для определения зависимостей и манипулирования ими в тех ситуациях, когда сложные отношения разбиваются на наборы более простых отношений в различных нормальных формах. Нетрудно обнаружить недостаточную развитость этого направления исследований. Э.Ф. Кодд (E.F. Codd) утверждает в [3], что он считает необходимым привести многочисленные примеры, объясняющие и мотивирующие его нормальные формы, а также их многочисленные тонкие последствия. Тот факт, что оказывается необходимым использование примеров отношений для объяснения природы ограничений отношений, подразумевает, что нам нужны средства описания самих этих ограничений. Этого можно достичь путем концептуального отделения отношений, существующих в конкретный момент времени, от возможных классов структур зависимостей, которые налагаются на эти отношения на основе атрибутов заданной базы данных. Вообще говоря, ограничение отношения потребует, чтобы по крайней мере некоторые зависимости были представлены в отношении в любое время, хотя могут существовать и случайные или несущественные зависимости (например, в таблице, состоящей из одной строки, мы можем определить значения всех атрибутов по значениям некоторых атрибутов или ни одного атрибута).

После краткого введения в реляционную модель данных в разд. 2 и определения структуры зависимостей в разд. 3 мы вводим в разд. 4 абсолютно общую аксиоматическую характеристику полных семейств зависимостей, которая включает в себя все структуры зависимостей, поддерживаемые для отношения . Чтобы обосновать аксиомы путем построения отношения, которое на самом деле содержит именно зависимости любого аксиоматически определенного полного семейства, мы должны сначала обсудить «максимальные» зависимости в разд. 5. В разд. 6 показано, что множества , принадлежащие максимальным зависимостям, замкнуты относительно операции пересечения. Множество генераторов этих (на основе пересечения) используется для построения требуемого отношения в разд. 7. В разд. 8 мы характеризуем возможные структуры возможных ключей отношения. В разд. 9 мы применяем результаты настоящей статьи для получения нового и более простого доказательства некоторых теорем Кейзи (Casey) и Делобеля (Delobel) [5]. В разд. 10 содержатся некоторые заключительные замечания.

2. Реляционная модель данных

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

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

Различие между отношением и менее общим понятием r-отношения состоит по-простому в том, что в последнем случае (неявно) . Другими словами, в случае r-отношений независимо от того, имеют атрибуты имена или нет, имеется упорядоченность атрибутов и их доменов: Тогда – это всего лишь конечная последовательность значений. Требование введения порядка на всех множествах атрибутов является избыточным с теоретической точки зрения. Кроме того, в использовании отношений, а не r-отношений имеется большой практический смысл, поскольку к любому атрибуту можно обращаться по его имени (например, ‘HEIGHT’), а не путем указания его позиции в порядке всех атрибутов (например, столбец номер 3 некоторой таблицы). Запоминание номеров столбцов может быть затруднительно для пользователей, которым приходится иметь дело с базой данных из нескольких r-отношений со многими атрибутами. К тому же номера столбцов могли бы меняться при реструктуризации базы данных.

В этой статье нам не требуется обсуждать частично определенные функции .

3. Структуры зависимостей

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

Структура зависимостей в отношении – это семейство

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

4. Полные семейства зависимостей

Чтобы определить некоторые множества зависимостей, введем частичный порядок ≥ на множестве всех зависимостей над следующим образом: для и мы определим, что ≥ в том и только в том случае, когда , . Это можно было бы прочитать как «зависимость не менее информативна, чем зависимость ».

После введения этого частичного порядка становится решеткой [4], в которой для двух элементов и наименьшей верхней границей является , а наибольшей нижней границей – . Отметим это только мимоходом, так как мы не будем использовать операции над решетками.

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

(1) ,
( если и , то ,
( если ≥ , то ,
( если и , то ,

где каждое условие связано квантором всеобщности по всем .

Теорема 1. Структура зависимостей любого отношения является полным семейством зависимостей.

Доказательство. Мы должны проверить соблюдение условий (1)- (4) при замене на . Это очень просто и оставляется читателю.

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

Пример. Для некоторого фиксированного рассмотрим семейство . Смысл состоит в том, что если содержит все атрибуты из , то нет ограничений на ; действительно, атрибуты в определяют все атрибуты в . Но если не содержит все атрибуты из , то зависимость должна быть тривиальной, т.е. . Доказательство того, что является полным семейством зависимостей, оставляется читателям.

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

5. Максимальные элементы полных семейств

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

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

Теорема 2. Семейство ℳ максимальных элементов полного семейства зависимостей удовлетворяет следующим условиям:

для всех существует ≥ такой, что ,
если и и ≥ , то ,
если и и , то .

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

Доказательство.

: Начиная с (по условию ), мы можем подниматься () в конечном множестве , пока не достигнем максимального элемента , который не менее информативен, чем .
: Мы можем ослабить условие до и воспользоваться тем, что является максимальным элементом .
: , следовательно, (по ). Вместе с тем, что , это дает (по ). Поэтому (по . Но является максимальным элементом в , поэтому .

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

Осталось показать, что является полным семейством.

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

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

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

Читателю оставляется проверка соблюдения условий -.

6. Насыщенные множества атрибутов

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

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

Теорема 3. Пусть – полное семейство зависимостей над и – его семейство максимальных элементов. Пусть определено как в начале раздела. Тогда – это полурешетка, содержащая [4], т.е. удовлетворяет следующим условиям:

,
если и , то .

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

Доказательство.

: следует из при .
пусть , . По такое, что . Но , поэтому по . Аналогично показывается, что , и поэтому /.

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

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

Чтобы показать, что является единственным полным семейством, определяемым заданным при посредстве , предположим, что имеется некоторое семейство , и его тоже определяет . Сначала покажем, что Для любого имеется ; и если при , то для при мы имеем . По и . Следовательно, по определению . Наконец, покажем, что . Для любого по найдется некоторая с . По определению . Следовательно, . На том доказательство теоремы заканчивается.

Пример: Для примера из разд. 4 и 5 мы получаем:

Очевидно, что это семейство удовлетворяет условиям и

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

Конечно, здесь по распространенному соглашению ^[2], так что никогда не требуется, чтобы входило в S. Для любого существует (уникальное!) наименьшее S, но полностью описывается путем задания любого S. Именно это описание позволяет нам увидеть, какие полные семейства возможны: мы можем выбрать произвольное семейство S подмножеств и построить из него и . Этот процесс дает все возможные .

Получаем следующую, теперь тривиальную теорему.

Теорема 4. Любое семейство S подмножеств приводит к получению полного семейства

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

Доказательство. Легко показать, что S и – семейство, которое генерирует S путем применения конечного числа операций пересечения, приводят к образованию одного и того же полного семейства (сравните с Теоремой 3).

7. Обоснование аксиом

Теорема 5. Пусть – произвольное полное семейство зависимостей над . Тогда существует отношение над с целочисленными доменами такое, что совпадает со структурой зависимостей отношения .

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

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

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

Построение примера оставляется читателю.

Эта теорема показывает, что наши аксиомы ( ( характеризуют в точности все возможные структуры зависимостей. Теперь мы можем использовать термины «структура зависимостей отношения» и «полное семейство зависимостей» взаимозаменяемым образом.

8. Структура семейства возможных ключей

Определение. Если – полное семейство зависимостей, то элементы из

называются возможными ключами .

Мы знаем, что возможный ключ должен существовать по , и пример разд. 4-6 показывает, что может иметься всего один возможный ключ: . В общем случае возможных ключей может быть много, как показывает следующая теорема.

Теорема 6. Семейство возможных ключей структуры зависимостей удовлетворяет следующим условиям:

если и , то .

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

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

удовлетворяет условиям и и поэтому по Теореме 3 порождает . генерируется посредством S .

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

Доказательство II. Приведем второе доказательство обратного утверждения теоремы на основе отношения .

Пусть .

Пусть . Пусть , где

Тогда легко показать, что является множеством всех возможных ключей .

9. Приложения

Мы не предполагаем, что аксиомы структуры зависимостей - являются оптимальным выбором, однако они предоставляют стандарт для проверки правильности и полноты других систем аксиом. Рассмотрим, например, систему аксиом, предложенную в [5] Делобелем и Кейзи:

(DC 1) Транзитивность (transitivity): если и , то .
(DC 2) Рефлексивность (reflexivity): .
(DC 3) Проективность (projectivity): если , то .
(DC 4) Аддитивность (additivity): если и , то .
(DC 5) Псевдотранзитивность (pseudotransitivity): если и , то .
(DC 6) Пополнение (augmentation): если , то .

Легко проверить, что (DC 1), (DC 3) и (DC 4) совместно эквивалентны нашим аксиомам для полных семейств зависимостей. То же самое верно для (DC 2), (DC 5) и (DC 6).

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

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

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

Если , ), – множество зависимостей над , Делобель и Кейзи определяют булевскую функцию

Теорема 7. Если определяется множеством зависимостей, то наименьшее полное множество , содержащее эти зависимости удовлетворяет следующему условию:

тогда и только тогда, когда )' ≤ f.

Кроме того, тогда и только тогда, когда является насыщенным относительно .

Доказательство: Из того, что тогда и только тогда, когда , следует, что для всех . Множество всех таких удовлетворяет условиям и и поэтому по Теореме 3 определяет некоторое полное множество , причем тогда и только тогда, когда для всех из следует . Очевидно, что для всех , ) . Если является произвольным полным семейством, содержащим , ), оно соответствует , где для всех и из следует . Следовательно, и по Теореме 3 . Условие )' ≤ f эквивалентно тому, что для всех ), т.е. .

Мы немедленно получаем результат Приложения A из [5].

Следствие A. Если определяется множеством зависимостей, то любое представление в виде

производит множество зависимостей , порождающее ту же структуру зависимостей.

Мы также получаем результат Приложения B из [5].

Следствие B. является возможным ключом структуры зависимостей, определяющей , тогда и только тогда, когда является простым импликантом^[3] , не содержащим переменные с отрицаниями.

Доказательство. тогда и только тогда, когда .

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

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

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

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

Автор благодарен Грегору Бохману (Gregor Bochmann), Вацлаву Хваталу (Vaclav Chvatal) и Нейлу Стюарту (Neil Stewart) за многие полезные советы.

Литература

E.F. Codd, A Relational Model of Data for Large Shared Data Banks, Communications of the ACM, vol. 13, no. 6, June 1970,377—387
E.F. Codd, A.L. Dean (eds.),1971 SIGFIDET Workshop on Data Description, Access, and Control, Association for Computing Machinery, New York, 1971.
E.F. Codd, Further Normalization of the Data Base Relational Model, Courant Inst. Comp. Sci. Symp. 6, Data Base Systems, Prentice-Hall, Englewood Cliffs, N.J., 1971, 33-64.
G. Birkhoff, Lattice Theory, 3rd. ed., American Mathematical Society Colloquium Publ. XXV, Providence, R.I., 1967.
C. Delobel, R.G. Casey, Decomposition of a data base and the theory of boolean switching functions, IBM Journal of Research and Development, vol. 17, no. 5, Sept. 1973, 374—386.

В статье используются два логически близких понятия – relationship и relation. Они определяются во втором разделе статьи и к ним обоим (в контексте данной статьи) применим русскоязычный термин «отношение». В переводе термин «отношение» соответствует авторскому «relationship», а r-отношение – «relation» – прим. переводчика. ↑
Принято считать, что результатом пересечения пустого семейства подмножеств некоторого множества является само это множество. Более подробное обоснование этого соглашения см., например, на https://proofwiki.org/wiki/Intersection_of_Empty_Set. – Прим. переводчика. ↑
См., например, https://en.wikipedia.org/wiki/Implicant -- прим. переводчика. ↑