Основы реляционных баз данных

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

Основы реляционных баз данных

1.1. Множества

1.2. Отношения

1.2.1. Общие сведения

1.2.2. Способы представления отношений

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

Селекция

Проекция

Естественное соединение

1.3. Декомпозиция отношений

1.3.1. Корректная декомпозиция

1.3.2. Пример некорректной декомпозиции

1.3.3. Зависимости между атрибутами

Функциональные зависимости

Многозначные зависимости

1.3.4. Правила вывода зависимостей

1.3.5. Ключи

1.4. Ограничения целостности отношений

1.4.1. Семантическая целостность

1.4.2. Доменная целостность

1.4.3. Ссылочная целостность

1.5. Нормализация таблиц

1.5.1. Первая нормальная форма

1.5.2. Вторая нормальная форма

1.5.3. Третья нормальная форма

1.5.4. Доменно-ключевая нормальная форма

1.5.5. Денормализация

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

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

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

1.1. Множества

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

Примечание

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

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

Множества могут быть конечными и бесконечными. Конечные множества содержат элементы, которые можно сосчитать или перечислить. Это означает, во-первых, что имеется принципиальная возможность сопоставить каждому элементу множества некоторое натуральное число (1, 2, 3, ... ), и, во-вторых, этот пересчет когда-нибудь закончится. Так, например, бесконечное множество всех целых чисел можно начать перечислять, но этот процесс никогда не закончится: для любого целого числа можно создать следующее, прибавив к нему 1. А вот множество всех действительных чисел, также являющееся бесконечным, даже начать перечислять невозможно. Интересно, что этот факт был установлен Кантором только лишь в конце XIX века и произвел на математиков ошеломляющее впечатление.

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

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

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

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

Какой-либо элемент x может принадлежать или не принадлежать некоторому множеству А. Чтобы указать, что элемент x принадлежит множеству А, пишут , а если x не принадлежит A, то пишут . Множество может и не содержать элементов, тогда его называют пустым и обозначают как Æ.

Простейший способ для определения конкретного множества состоит в том, чтобы явно указать все элементы, принадлежащие этому множеству. Это так называемый экстенсиональный способ определения множества. Если количество элементов, входящих в множество A, не велико, то он вполне применим на практике: достаточно написать выражение вида . Однако при достаточно больших множествах этот способ не подходит. Тогда используют так называемый интенсиональный (неявный) способ определения множеств. Он основан на использовании некоторой функции (алгоритма), которая для каждого элемента определяет, принадлежит ли он данному множеству или нет. Пусть для некоторого множества A определена такая функция . Если вместо переменной x подставить в ее выражение конкретный элемент a, то результатом вычисления  будет либо ИСТИНА (true), либо ЛОЖЬ (false), в зависимости от того, принадлежит или нет элемент a множеству A. Таким образом, функция  принимает в качестве аргументов элементы из некоторой области (универсума) и возвращает одно из двух значений, которые мы здесь обозначаем как ИСТИНА и ЛОЖЬ (т. е. функция  является двухзначной). С другой стороны, мы можем определить некоторым образом какую-нибудь двухзначную функцию , принимающую в качестве аргумента значения из некоторого универсума. Тогда эта функция определяет некоторое множество, а именно, множество всех тех элементов универсума, для которых эта функция возвращает значение ИСТИНА. Указанные двухзначные функции в математической логике называются предикатами.

В качестве примера рассмотрим выражение . Это типичное выражение сравнения. Здесь через x обозначена переменная, значения которой берутся из множества всех действительных чисел. Тогда это выражение может принимать значения ИСТИНА или ЛОЖЬ в зависимости от того, какое значение будет подставлено вместо x. Вопреки сложившейся математической практике мы могли бы записать данное выражение и в таком виде: . Здесь  — обозначение предиката "быть меньше 5". Данный предикат определяет множество всех действительных чисел, которые меньше числа 5. Обратите внимание, что мы некоторым конечным образом определили бесконечное множество.

Аналогично мы можем определить с помощью предиката  множество всех красных элементов. Разумеется, мы должны иметь алгоритм вычисления данного предиката, т. е. алгоритм определения, является ли предъявленный элемент x красным, или нет.

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

Примечание

Предикаты в математической логике являются двухзначными функциями. Однако как в математике, так и на практике нередко встречаются ситуации, к которым больше подходит многозначная и, в частности, трехзначная логика. Так, для некоторого элемента x результатом вычисления значений некоторого предиката P(x) может быть не только ИСТИНА или ЛОЖЬ, но и некоторое третье значение, например, NULL. Последнее интерпретируется как "не определено" или "не известно". Такая логика в том или ином виде принята при поддержке современных баз данных. Например, столбец таблицы базы данных может содержать помимо наборов каких-то символов особое значение NULL, которое понимается как "еще не введенное", "пока неизвестное" и т. п. Однако замечу, что понимание трехзначной логики лучше усваивается при условии понимания классической двухзначной логики.

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

Не следует смешивать отношение принадлежности  между элементами и множествами и отношение включения  между множествами. Так, например, если  и , то это еще не означает, что . Другой пример: если  и , то , но не верно, что . Верно лишь, что , т. е. множество, состоящее из элемента B, является подмножеством множества A. Иначе говоря, элементы некоторого множества A сами могут быть множествами, но элементы последних не обязательно являются элементами множества A. Так, в рассматриваемом примере , , , но . Заметим также, что элемент и множество, содержащее единственный этот элемент (т. е. x и ), — разные вещи.

Над множествами можно выполнять различные операции: объединение (), пересечение (), вычитание (-) и декартово произведение (´).

Объединение множеств A и B есть множество, обозначаемое как , которое содержит все элементы множества A и все элементы множества B. Например, пусть , . Тогда . Напомню, что в любом множестве все элементы должны быть различны. Другими словами, множество  содержит только такие элементы, которые принадлежат множеству A или множеству B (возможно, и обоим одновременно). В частности, .

Пересечение множеств A и B есть множество, обозначаемое как , которое содержит все элементы, принадлежащие как множеству A, так и множеству B. Если таких элементов нет, то пересечение множеств пусто (). Например, пусть , . Тогда . В частности, .

Вычитание из множества A множества B дает в результате множество, называемое разностью этих множеств и обозначаемое как . Это множество содержит все элементы множества A, которые не принадлежат множеству B. Например, пусть , . Тогда . В частности, . Если множества A и B не пересекаются (т. е. ), то . Множество  называют также дополнением множества B до множества A.

Декартово произведение множеств будет рассмотрено далее в разд. 1.2.

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

Примечание

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

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

q       — закон двойного дополнения (отрицания);

q       — закон исключения третьего;

q       — закон противоречия;

q      ;

q      ;

q      законы Моргана:

;

;

      законы коммутативности (перестановки):

;

;

      законы ассоциативности (группировки):

;

;

      законы дистрибутивности (сочетания операций):

;

.

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

В качестве упражнения докажем одно из приведенных ранее равенств, а именно один из законов дистрибутивности:

.

Для этого достаточно доказать два включения, а именно:

и

.

1.     Доказательство включения

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

2.     Доказательство включения

Пусть . Тогда  и . Следовательно,  или же  и , т. е. .

На этом доказательство равенства двух множеств заканчивается.

Итак, мы рассмотрели понятие множества и основные операции над множествами. Теперь кратко рассмотрим понятия высказывания и предиката. Высказывание, с точки зрения математической логики, не зависимо от его информационного содержания и смысла, либо истинно, либо ложно. Например, высказывание "дважды два равно четырем" считается истинным, а высказывание "все птицы могут летать" — ложным (поскольку есть, например, страус, который не летает). Однако мы можем составить выражение, в котором будут фигурировать некие изначально неопределенные объекты, вроде переменных в математических выражениях. Например, выражение  может быть как истинным, так и ложным в зависимости от того, что имеется в виду под переменной x (т. е. каково ее значение). Выражение "нечто является красным" также не может принять конкретного значения истинности, пока мы не определим, что понимается под словом "нечто". Так, если в выражение  подставить число 3, то оно примет вид  и будет истинным. Если же в это выражение подставить число 12345, то получится ложное высказывание. Выражения с переменными, возвращающие одно из двух возможных значений (ИСТИНА или ЛОЖЬ) после подстановки вместо переменных конкретных значений, называются предикатами. Пусть имеется некоторое выражение с переменными . Обозначим его как , подчеркивая тем самым, что это просто некоторая функция от n аргументов. Особенностью этой функции является только то, что она двухзначная — принимает одно из двух возможных значений (ИСТИНА или ЛОЖЬ).

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

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

К предикатам, как и к высказываниям, применимы операторы отрицания (), конъюнкции () и дизъюнкции (). В результате применения этих операторов получается другой предикат. Оператор отрицания изменяет значение предиката на противоположное. Так, если предикат  истинен, то  ложен, и наоборот. Оператор конъюнкции выполняет роль логического союза И, а дизъюнкции — логического союза ИЛИ. Так, для двух предикатов  и  предикат  истинен только тогда, когда истинны одновременно оба предиката; предикат  истинен только тогда, когда истинен хотя бы один из предикатов.

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

До сих пор мы рассматривали предикаты только от одной переменной. Однако предикаты могут содержать и несколько переменных. Например, предикат  представляет собой равенство двух числовых выражений с двумя переменными — x и y. Следующее выражение является истинным высказыванием:

Изменение типа квантора в выражении может изменить его значение истинности. Так, например, следующее высказывание ложно:

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

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

Пусть  — некоторый предикат. Тогда справедливы следующие равенства:

Пусть, например, P обозначает свойство "быть красным". Тогда первое из двух указанных равенств означает, что высказывание "не верно, что все x красные" эквивалентно высказыванию "некоторые x не красные". Второе равенство утверждает эквивалентность высказываний "не верно, что есть красный объект" и "все объекты не красные".

1.2. Отношения

1.2.1. Общие сведения

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

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

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

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

Рассмотрим в качестве примера отношение ОТЦЫ_И_ДЕТИ. Это отношение между множеством МУЖЧИНЫ и множеством ЛЮДИ: ОТЦЫ_И_ДЕТИ (МУЖЧИНЫ, ЛЮДИ). Мы не будем сейчас определять предикат, задающий это отношение. Алгоритм определения отцовства может быть различным. Например, можно ограничиться только опросом всех мужчин на предмет, каких детей они имеют, провести генетическую экспертизу и т. п. Как бы то ни было, в результате мы получим множество всех кортежей вида , в которых через x1 и x2 обозначены люди, такие, что x1 является отцом для x2. В качестве имен людей следует выбрать их уникальные идентификаторы. Фамилия, имя и отчество для этой цели вряд ли подойдут. Возможно, окажется достаточным использовать дополнительные паспортные данные, отпечатки пальцев или снимок радужной оболочки глаза. Очевидно, что множества отцов и женщин включаются в множество людей, но ни одна женщина не принадлежит множеству отцов. Поэтому в рассматриваемом отношении ОТЦЫ_И_ДЕТИ не будет ни одного кортежа, в котором на первом месте стояло бы имя женщины. Кроме того, ни один человек не может быть отцом для самого себя. Поэтому в отношении не будет ни одного кортежа, в котором первый и второй элемент совпадают. Эти и, возможно, другие особенности, характеризующие отношение, называют ограничениями его целостности.

Задавая отношение ОТЦЫ_И_ДЕТИ, мы можем, по крайней мере теоретически, поступить следующим образом. Сначала возьмем множество всевозможных кортежей , в которых МУЖЧИНЫ и ЛЮДИ. А затем выберем из этого множества только те кортежи, в которых x1 является отцом для x2. Полученное множество и будет представлять собой интересующее нас отношение ОТЦЫ_И_ДЕТИ.

Множество всех возможных кортежей , в которых  и , называется декартовым произведением множеств A1 и A2 и обозначается как . Количество элементов в декартовом произведении равно произведению количеств элементов в множествах A1 и A2. Например, если  и , то:

.

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

Декартово произведение для n множеств  обозначается как  и состоит из всевозможных кортежей вида , в которых , , ... , . Например, пусть товары на складе имеют характеристики, выбираемые из множеств НАИМЕНОВАНИЕ, КОЛИЧЕСТВО, ЦЕНА и ПОСТАВЩИК. Тогда таблица, содержащая сведения о всех товарах на складе, представляет отношение между указанными характеристиками, а все ее строки — кортежи, принадлежащие некоторому подмножеству декартового произведения:

НАИМЕНОВАНИЕ ´ КОЛИЧЕСТВО ´ ЦЕНА ´ ПОСТАВЩИК.

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

1.2.2. Способы представления отношений

К представлениям отношений мы приходим, когда требуется наглядность или определенное удобство для хранения данных и манипулирования ими. Рассмотрим несколько вариантов.

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

Бинарные (двухместные) отношения можно представить в виде графов, а также двухстолбцовых таблиц. В графовом представлении каждой вершине соответствует некоторый элемент одного из двух множеств. От одной вершины к другой проводится стрелка, если первый элемент находится в рассматриваемом отношении со вторым. Например, отношение достижимости населенных пунктов из данного пункта с помощью авиарейсов является бинарным отношением между множеством АВИАРЕЙСЫ и множеством ПУНКТЫ_НАЗНАЧЕНИЯ. Мы проводим из вершины графа достижимости, соответствующей, например, рейсу Р123, стрелку в вершину "Москва", если данным рейсом можно добраться до данного пункта. Очевидно, информацию о достижимости пунктов авиарейсами можно представить и в виде двухстолбцовой таблицы. В первом столбце указываются авиарейсы, а во втором — пункты назначения. В каждой строке указывается, каким авиарейсом и куда можно долететь. Каждая строка таблицы представляет собой кортеж отношения.

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

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

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

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

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

Табличное представление отношений — это чрезвычайно плодотворный технологический прием, обеспечивший создание и широкое практическое применение баз данных. То обстоятельство, что отношения — просто множества, позволило изучать проблемы реляционных баз данных на теоретическом уровне, в мире математики (алгебра множеств и исчисление предикатов), а не только в мире технологии. В результате разработка СУБД, конкретных баз данных, языков манипулирования данными, в том числе и SQL, водрузилась на твердый теоретический фундамент.

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

      Отношение имеет имя R. Например, сведения о товарах, хранящихся на складе, образуют некоторое отношение, которому можно дать имя СКЛАД.

      Множества , для которых определено отношение R, имеют различные имена, называемые атрибутами отношения. Мы будем считать, что  — атрибуты отношения. Совокупность всевозможных значений любого множества с именем  () называется доменом атрибута . Заметим еще раз, что в отношении не может быть двух и более одинаковых атрибутов, хотя их домены могут быть и одинаковы (в смысле равенства множеств). Например, отношение СКЛАД может быть определено для атрибутов НАИМЕНОВАНИЕ, КОЛИЧЕСТВО, ЦЕНА и ПОСТАВЩИК. Структуру этого отношения можно записать так: СКЛАД (НАИМЕНОВАНИЕ, КОЛИЧЕСТВО, ЦЕНА, ПОСТАВЩИК). Каждый атрибут имеет свой домен — множество возможных значений. Например, доменом атрибута КОЛИЧЕСТВО может быть множество неотрицательных чисел. При табличном представлении отношения каждому атрибуту соответствует заголовок столбца, а домену — множество значений в этом столбце.

      Порядок перечисления атрибутов в структуре отношения не имеет значения. Иначе говоря, перестановка атрибутов местами оставляет само отношение прежним, хотя вид таблицы, представляющей это отношение, изменяется. Например, отношения СКЛАД (НАИМЕНОВАНИЕ, КОЛИЧЕСТВО, ЦЕНА, ПОСТАВЩИК) и СКЛАД (ПОСТАВЩИК, НАИМЕНОВАНИЕ, КОЛИЧЕСТВО, ЦЕНА) считаются эквивалентными.

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

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

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

      Селекция

      Проекция

      Естественное соединение

Эти операции выражаются некоторым образом через обычные операции над множествами, такие как объединение, пересечение, вычитание и декартово произведение. Рассмотрим их более подробно.

Селекция

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

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

На рис. 1.1 в качестве примера показано некоторое отношение , домены D1, D2 и D3 атрибутов A1, A2 и A3, некоторые подмножества d1, d2 и d3 этих доменов, декартово произведение  и результат сужения исходного отношения на множество кортежей .

Рис. 1.1. Пример сужения отношения

Рассмотрим в качестве примера отношение ЗАРПЛАТА (СОТРУДНИК, ВЫПЛАТА), которое можно представить в виде двухстолбцовой таблицы. В этой таблице в столбце СОТРУДНИК указаны имена сотрудников некоторой фирмы или какого-то ее подразделения, а в столбце ВЫПЛАТА — денежная сумма, причитающаяся соответствующему сотруднику. Допустим, нас интересуют выплаты только Иванову и Петрову — элементам домена атрибута СОТРУДНИКИ. Обозначим через D_{СОТРУДНИК} множество всех значений столбца СОТРУДНИК. Это и есть домен атрибута СОТРУДНИК. Аналогично, обозначим через D_{ВЫПЛАТА} домен атрибута ВЫПЛАТА. Тогда интересующее нас отношение можно определить следующим образом:

ЗАРПЛАТА (СОТРУДНИК, ВЫПЛАТА)  {Иванов, Петров} ´ D_{ВЫПЛАТА}

Здесь через {Иванов, Петров} обозначено требуемое подмножество домена атрибута СОТРУДНИК.

На естественном языке запрос на получение указанного множества кортежей выглядит более чем просто: "выбрать кортежи, в которых значение атрибута СОТРУДНИК равно "Иванов" или "Петров". Эквивалентный запрос можно еще сформулировать и так: "выбрать кортежи, в которых значение атрибута СОТРУДНИК равно "Иванов", и те кортежи, в которых значение атрибута СОТРУДНИК равно "Петров". Обратите внимание на использование союзов "или" и "и" в этих формулировках запросов. Если в первой формулировке "или" заменить на "и", то искомое множество кортежей будет заведомо пустым, поскольку атрибут СОТРУДНИК в одном и том же кортеже не может иметь два и более различных значения. Вторая формулировка допускает замену "и" на "или", поскольку в ней речь идет о различных значениях атрибута в различных кортежах. Применяя в обычной речи союзы "и" и "или", всегда следует отдавать себе отчет в том, что имеется в виду — объединение или пересечение соответствующих множеств.

Примечание

На языке SQL данный запрос формулируется следующим образом:

SELECT * FROM ЗАРПЛАТА WHERE СОТРУДНИК='Иванов' OR СОТРУДНИК='Петров'

По-русски это выглядит так: "выбрать кортежи (записи) из таблицы ЗАРПЛАТА, в которых атрибут (столбец) СОТРУДНИК имеет значение 'Иванов' или 'Петров'.

Проекция

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

На рис. 1.2 в качестве примера показано некоторое отношение  и его проекция  на множество атрибутов .

Рис. 1.2. Пример проекции отношения

Примечание

На языке SQL проекция отношения (таблицы) на заданное множество атрибутов (столбцов) производится с помощью оператора:

SELECT список_столбцов FROM имя_таблицы

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

SELECT список_столбцов FROM имя_таблицы WHERE условие_выборки

Естественное соединение

Предположим, имеются два отношения, содержащие кроме прочих и одинаковые атрибуты. Рассмотрим, например, две таблицы R1 (ПРЕПОДАВАТЕЛЬ, ДИСЦИПЛИНА) и R2 (ПРЕПОДАВАТЕЛЬ, КАФЕДРА).

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

      Отношение R2 содержит сведения о приписке преподавателей к кафедрам. Предполагается, что каждый преподаватель может быть приписан только к одной кафедре.

Естественно, может возникнуть задача сведения этих двух отношений в одно (соединить две таблицы в одну) — R3 (ПРЕПОДАВАТЕЛЬ, ДИСЦИПЛИНА, КАФЕДРА). На рис. 1.3 показаны примеры отношений R1 и R2, а также результат их соединения R3. Важным обстоятельством, позволившим выполнить соединение двух отношений, является наличие у них общего атрибута ПРЕПОДАВАТЕЛЬ. Обратите внимание, что проекция отношения R3 на атрибуты {ПРЕПОДАВАТЕЛЬ, ДИСЦИПЛИНА} в точности равна отношению R1, а проекция на атрибуты {ПРЕПОДАВАТЕЛЬ, КАФЕДРА} — отношению R2. Это означает, что при соединении отношений R1 и R2 в отношение R3 не было привнесено ничего нового и ничего не было потеряно. Другими словами, отношение R3 в точности представляет информацию, содержащуюся в отношениях R1 и R2.

Рис. 1.3. Пример соединения отношений

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

Пусть даны два отношения  и , где A1, A2 — множества атрибутов (а не одиночные атрибуты). Естественным соединением этих отношений  называется отношение , содержащее те и только те кортежи z, для которых выполняются одновременно следующие два условия:

      ;

      .

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

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

      Множества атрибутов отношений  и  не равны, но пересекаются (т. е. , ). В данном случае:

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

      Множества атрибутов отношений равны (т. е. ). Тогда естественное соединение равно пересечению исходных отношений:

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

Рис. 1.4. Естественное соединение отношений

Примечание

Язык SQL предоставляет специальные средства для различных типов соединения таблиц. Естественное соединение отношений R1 (ПРЕПОДАВАТЕЛЬ, ДИСЦИПЛИНА) и R2 (ПРЕПОДАВАТЕЛЬ, КАФЕДРА), показанных на рис. 1.3, можно выполнить с помощью следующего SQL-выражения:

SELECT R1.*, R2.КАФЕДРА FROM R1, R2 WHERE R1.ПРЕПОДАВАТЕЛЬ=R2.ПРЕПОДАВАТЕЛЬ

По-русски это выглядит так: "выбрать все столбцы таблицы R1 и столбец КАФЕДРА таблицы R2 из декартового произведения R1 и R2 при условии, что преподаватели из этих таблиц одинаковы".

Здесь подразумевается именно декартово произведение, т. к. после ключевого слова FROM указаны две таблицы. В SQL также можно использовать оператор NATURAL JOIN для явного указания операции естественного соединения.

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

1.3. Декомпозиция отношений

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

Так, в рассмотренном в предыдущем разделе отношении R3 (ПРЕПОДАВАТЕЛЬ, ДИСЦИПЛИНА, КАФЕДРА) (см. рис. 1.3) все атрибуты имеют повторяющиеся значения, а атрибут ПРЕПОДАВАТЕЛЬ однозначно определяет атрибут КАФЕДРА, поскольку каждый преподаватель приписан только к одной кафедре. Наличие такой зависимости между атрибутами ПРЕПОДАВАТЕЛЬ и ДИСЦИПЛИНА наталкивает на мысль, что декомпозиция возможна.

Отношения R1 (ПРЕПОДАВАТЕЛЬ, ДИСЦИПЛИНА) и R2 (ПРЕПОДАВАТЕЛЬ, КАФЕДРА) можно рассматривать как результат декомпозиции отношения R3, т. е. как операцию, обратную естественному соединению. Обратите внимание, что общий объем данных в отношениях R1 и R2 меньше объема данных в отношении R3. Кроме того, в отношении R2 атрибут ПРЕПОДАВАТЕЛЬ не имеет повторяющихся значений.

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

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

1.3.1. Корректная декомпозиция

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

Например, декомпозиция отношения R3 (ПРЕПОДАВАТЕЛЬ, ДИСЦИПЛИНА, КАФЕДРА) (см. рис. 1.3) на свои проекции:

R3 [ПРЕПОДАВАТЕЛЬ, ДИСЦИПЛИНА] = R1 (ПРЕПОДАВАТЕЛЬ, ДИСЦИПЛИНА)

и

R3 [ПРЕПОДАВАТЕЛЬ, КАФЕДРА] = R2 (ПРЕПОДАВАТЕЛЬ, КАФЕДРА)

является корректной.

Это утверждение просто следует из того, что отношение R3 было получено из отношений R1 и R2 путем их естественного соединения (см. разд. 1.2.3).

1.3.2. Пример некорректной декомпозиции

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

Рис. 1.5. Пример некорректной декомпозиции отношения

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

1.3.3. Зависимости между атрибутами

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

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

Функциональные зависимости

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

Рассмотрим несколько примеров отношений, показанных на рис. 1.3.

      В отношении R2 (ПРЕПОДАВАТЕЛЬ, КАФЕДРА) между атрибутами ПРЕПОДАВАТЕЛЬ и КАФЕДРА имеется функциональная зависимость, поскольку каждый преподаватель может быть приписан лишь к одной кафедре (предполагается, что совместительство не допускается). Другими словами, по значению атрибута ПРЕПОДАВАТЕЛЬ можно однозначно определить, на какой кафедре он работает. Однако между атрибутами КАФЕДРА и ПРЕПОДАВАТЕЛЬ в отношении R2 нет функциональной зависимости: на одной и той же кафедре могут работать несколько преподавателей.

      В отношении R1 (ПРЕПОДАВАТЕЛЬ, ДИСЦИПЛИНА) нет ни одной функциональной зависимости: один и тот же преподаватель может заниматься несколькими дисциплинами, а одну и ту же дисциплину могут вести несколько преподавателей.

      В отношении R3 (ПРЕПОДАВАТЕЛЬ, ДИСЦИПЛИНА, КАФЕДРА) существуют две функциональных зависимости:

·                между атрибутами ПРЕПОДАВАТЕЛЬ и КАФЕДРА;

·                между атрибутами ДИСЦИПЛИНА и КАФЕДРА.

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

Пусть дано некоторое отношение  с атрибутами из множества A, т. е. A — это множество атрибутов, а не отдельный атрибут. Обозначим через X и Y некоторые подмножества атрибутов (, ). В отношении  выполняется функциональная зависимость между атрибутами X и Y, обозначаемая как , если для любых кортежей z1 и z2 этого отношения из равенства их проекций на множество атрибутов X следует равенство их проекций на множество атрибутов Y. Иначе говоря, функциональная зависимость  выполняется, если справедливо следующее высказывание: для любых z1 и z2 из равенства  следует равенство .

Если выполняется функциональная зависимость , то говорят, что атрибуты X функционально (однозначно) определяют атрибуты Y.

Например, в отношении R3 (ПРЕПОДАВАТЕЛЬ, ДИСЦИПЛИНА, КАФЕДРА), показанном на рис. 1.3, имеются следующие функциональные зависимости:

      {ПРЕПОДАВАТЕЛЬ}{КАФЕДРА} — преподаватель функционально определяет кафедру;

      {ДИСЦИПЛИНА}{КАФЕДРА} — дисциплина функционально определяет кафедру;

      {ПРЕПОДАВАТЕЛЬ, ДИСЦИПЛИНА}{КАФЕДРА} — преподаватель и дисциплина функционально определяют кафедру.

Рассмотрим еще один пример. Предположим, отношение ПРОДАЖИ (ТОВАР, КОЛИЧЕСТВО, ЦЕНА, СТОИМОСТЬ) содержит сведения о проданных товарах. Стоимость товара однозначно определяется его количеством и ценой, поскольку существует простая формула: стоимость = количество ´ цена. Поэтому в данном отношении имеется функциональная зависимость {КОЛИЧЕСТВО, ЦЕНА}{СТОИМОСТЬ}.

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

Здесь через (*) обозначена операция естественного соединения. Таким образом, исходное отношение  можно восстановить с помощью операции естественного соединения двух своих проекций —  и .

Например, в отношении R3 (ПРЕПОДАВАТЕЛЬ, ДИСЦИПЛИНА, КАФЕДРА), показанном на рис. 1.3, имеется функциональная зависимость {ПРЕПОДАВАТЕЛЬ}{КАФЕДРА}. Следовательно, это отношение можно декомпозировать на две проекции:

      R3 [ПРЕПОДАВАТЕЛЬ, КАФЕДРА];

      R3 [ПРЕПОДАВАТЕЛЬ, ДИСЦИПЛИНА].

В данном примере можно принять такие обозначения:

      A = {ПРЕПОДАВАТЕЛЬ, ДИСЦИПЛИНА, КАФЕДРА};

      X = {ПРЕПОДАВАТЕЛЬ};

      Y = {КАФЕДРА};

      = {ПРЕПОДАВАТЕЛЬ, КАФЕДРА};

      = {ПРЕПОДАВАТЕЛЬ, ДИСЦИПЛИНА};

       = {ПРЕПОДАВАТЕЛЬ}{ПРЕПОДАВАТЕЛЬ, ДИСЦИПЛИНА} = {ПРЕПОДАВАТЕЛЬ, ДИСЦИПЛИНА}.

Отношение ПРОДАЖИ (ТОВАР, КОЛИЧЕСТВО, ЦЕНА, СТОИМОСТЬ), имеющее функциональную зависимость {КОЛИЧЕСТВО, ЦЕНА}{СТОИМОСТЬ}, можно декомпозировать на такие проекции:

      ПРОДАЖИ [КОЛИЧЕСТВО, ЦЕНА, СТОИМОСТЬ]

      ПРОДАЖИ [ТОВАР, КОЛИЧЕСТВО, ЦЕНА]

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

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

Приведем несколько свойств функциональных зависимостей.

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

      В отношении  функциональная зависимость  выполняется тогда и только тогда, когда она выполняется в проекции , где .

Многозначные зависимости

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

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

      Атрибут A1 не определяет однозначно атрибут A2, т. е. нет функциональной зависимости .

      Атрибуты A2 и A3 не зависят друг от друга, т. е. в отношении  любое значение A2 может сочетаться в кортежах с любым значением A3.

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

Это частное определение многозначной зависимости, возможно, и не очень понятное. Поэтому поясним его на примере.

Пусть дано отношение R (ПРЕПОДАВАТЕЛЬ, ДИСЦИПЛИНА, УВЛЕЧЕНИЕ), которое содержит сведения о преподавателях, дисциплинах, занятия по которым они проводят, и личных увлечениях (хобби). Предполагается, что один преподаватель может проводить занятия по нескольким дисциплинам, т. е. атрибут ПРЕПОДАВАТЕЛЬ не определяет однозначно атрибут ДИСЦИПЛИНА. Далее, мы считаем, что нет никакой связи между дисциплинами и увлечениями преподавателей. Иначе говоря, если известно, что преподаватель читает студентам, например, математический анализ, то из этого нельзя однозначно определить, чем конкретно он увлекается. И наоборот, если мы знаем, о конкретном увлечении преподавателя классической музыкой, то еще не можем однозначно сказать, какой именно дисциплиной он занимается. Все это означает, что в рассматриваемом отношении значения атрибутов ДИСЦИПЛИНА и УВЛЕЧЕНИЕ могут сочетаться произвольным образом. Итак, атрибуты ДИСЦИПЛИНА и УВЛЕЧЕНИЕ не зависят друг от друга, а атрибут ПРЕПОДАВАТЕЛЬ не однозначно определяет атрибут ДИСЦИПЛИНА. Пример рассмотренного отношения показан на рис. 1.6.

Рис. 1.6. Отношение с многозначной зависимостью ПРЕПОДАВАТЕЛЬДИСЦИПЛИНА

Поскольку в отношении R постулируется независимость атрибутов ДИСЦИПЛИНА и УВЛЕЧЕНИЕ, то в этом отношении каждое сочетание значений атрибутов ПРЕПОДАВАТЕЛЬ и ДИСЦИПЛИНА должно сочетаться с каждым значением атрибута УВЛЕЧЕНИЕ. В примере отношения, показанном, на рис. 1.6, преподаватель Иванов проводит занятия по двум дисциплинам и имеет два хобби. Поэтому ему в таблице посвящено четыре записи (кортежа). Михайлов занят двумя дисциплинами и имеет одно увлечение, поэтому информация о нем представлена в отношении двумя записями. В данном отношении имеется многозначная зависимость ПРЕПОДАВАТЕЛЬДИСЦИПЛИНА или, другими словами, атрибут ПРЕПОДАВАТЕЛЬ многозначно определяет атрибут ДИСЦИПЛИНА. Заметим, что мы бы не говорили о многозначной зависимости ПРЕПОДАВАТЕЛЬДИСЦИПЛИНА, если бы между атрибутами ДИСЦИПЛИНА и УВЛЕЧЕНИЕ существовала какая-нибудь зависимость.

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

Рис. 1.7. Декомпозиция отношения, содержащего многозначную зависимость ПРЕПОДАВАТЕЛЬДИСЦИПЛИНА

Поскольку выполняется многозначная зависимость ПРЕПОДАВАТЕЛЬДИСЦИПЛИНА, атрибуты ДИСЦИПЛИНА и УВЛЕЧЕНИЕ не зависят друг от друга. Поэтому имеется возможность представить связи ПРЕПОДАВАТЕЛЬ—ДИСЦИПЛИНА и ПРЕПОДАВАТЕЛЬ—УВЛЕЧЕНИЕ в виде отдельных отношений, причем так, чтобы исходное отношение R (ПРЕПОДАВАТЕЛЬ, ДИСЦИПЛИНА, УВЛЕЧЕНИЕ) полностью восстанавливалось с помощью операции естественного соединения.

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

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

Рис. 1.8. Отношение с многозначной зависимостью A1A2

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

Рис. 1.9. Декомпозиция отношения R(A1, A2, A3) с многозначной зависимостью A1A2

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

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

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

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

На рис. 1.10 представлено некоторое отношение  и две его проекции —  и . Нетрудно проверить, что выполняется равенство . Следовательно, отношение декомпозируется на эти проекции. Но тогда в отношении  выполняются две многозначные зависимости:

       — поскольку  и ;

       — поскольку .

С учетом первой зависимости исходное отношение можно декомпозировать на проекции  и , показанные на рис. 1.10. С учетом второй зависимости это отношение можно декомпозировать на такие же проекции.

Рис. 1.10. Из данной декомпозиции отношения следует наличие в нем зависимостей A2A1 и A2A3

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

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

1.3.4. Правила вывода зависимостей

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

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

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

В систему правил вывода многозначных зависимостей входят четыре основных правила. Прежде, чем их перечислить, договоримся об обозначениях. Через A будем обозначать множество всех атрибутов отношения, а через X, Y и Z — подмножества атрибутов (, , ). Разумеется, каждое из них может содержать и только единственный элемент — какой-нибудь один атрибут отношения. Для обозначения многозначной зависимости используется, как и раньше, символ (). Однако все приведенные далее утверждения справедливы не только для многозначных зависимостей, но и для функциональных зависимостей.

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

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

2.     Правило рефлексивности. Если , то .

3.     Правило пополнения. Если выполняется зависимость  и для некоторых подмножеств атрибутов V и W справедливо включение , то выполняется зависимость .

4.     Правило транзитивности. Если выполняются две зависимости —  и , то выполняется и зависимость .

Из этих четырех основных правил можно логически вывести еще три дополнительных правила:

1.     Правило объединения. Если выполняются две зависимости —  и , то выполняется и зависимость .

2.     Правило разности. Если выполняются две зависимости —  и , то выполняется и зависимость .

3.     Правило пересечения. Если выполняются две зависимости —  и , то выполняется и зависимость .

Дополнительные правила удобно использовать для сокращения длины вывода зависимостей.

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

Пусть даны две зависимости  и , тогда вывод правила разности состоит из следующих четырех шагов:

1.     По правилу пополнения из  следует , т. е. .

2.     По правилу пополнения из  следует .

3.     По правилу транзитивности из  и  следует . Однако , поэтому выполняется зависимость .

4.     Так как , то по правилу пополнения из  следует . Но , а , поэтому справедлива зависимость .

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

1.3.5. Ключи

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

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

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

Рассмотрим в качестве примера таблицу, представляющую отношение Студенты (Фамилия, Имя, Отчество, Учебная_группа). Какие атрибуты в этом отношении могут составить ключ? Предполагается, что каждый студент может находиться только в одной учебной группе. Казалось бы, что множество атрибутов {Фамилия, Имя, Отчество} должно однозначно идентифицировать студента, а, следовательно, и группу. Это было бы верно, если бы мы исключили возможность существования в одной группе полных тезок (однофамильцев с одинаковыми именами и отчествами). Хотя это и маловероятно, но все же возможно. Таким образом, множество атрибутов {Фамилия, Имя, Отчество} не подходит на роль нетривиального ключа. В подобных ситуациях создают специальный атрибут (столбец), предназначенный играть роль ключа. В нашем примере это может быть ID_cтудента (идентификатор студента). Значения этого атрибута могут быть какими угодно, но обязательно уникальными. В результате получается таблица Студенты (ID_студента, Фамилия, Имя, Отчество, Учебная_группа). А если ID_студента является ключом, то в данном отношении имеется функциональная зависимость {ID_студента}{ID_студента, Фамилия, Имя, Отчество, Учебная_группа}, а также зависимость {ID_студента}{Фамилия, Имя, Отчество, Учебная_группа}. Последнюю зависимость, очевидно, можно использовать для декомпозиции исходного отношения на следующие два: Студенты_список (ID_студента, Фамилия, Имя, Отчество) и Группы (ID_студента, Учебная_группа). На рис. 1.11 показано исходное отношение Студенты и две его проекции.

Рис. 1.11. Декомпозиция отношения Студенты с ключом ID_студента на две проекции

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

1.4. Ограничения целостности отношений

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

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

Далее мы рассмотрим несколько видов целостности и способы их задания.

1.4.1. Семантическая целостность

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

В таблице, обладающей семантической целостностью должен быть первичный ключ. Первичный ключ (см. разд. 1.3.5) — это один столбец или группа столбцов, значения которых должны быть уникальными и определенными (не равными NULL). В языке SQL это ограничение целостности, выражающееся в виде ограничения на значения столбца или группы столбцов, задается ключевыми словами PRIMARY KEY (см. разд. 7.2.1, 7.2.2).

1.4.2. Доменная целостность

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

Ограничения на допустимые значения для столбца таблицы предназначены для поддержания доменной целостности. В языке SQL риск нарушить доменную целостность возникает при добавлении и обновлении записей с помощью операторов INSERT и UPDATE соответственно. Ограничения доменной целостности можно задать при создании таблицы с помощью оператора CREATE TABLE, а также предварительно, путем создания домена, применив оператор CREATE DOMAIN.

1.4.3. Ссылочная целостность

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

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

      Клиенты (Имя_клиента, Адрес, Телефон);

      Продажи (ID, Товар, Количество, Цена, Стоимость, Имя_клиента).

В таблице Клиенты столбец Имя_клиента является ключом (PRIMARY KEY), т. е. имеет уникальные и определенные значения. В таблице Продажи одноименный столбец не является ключом, его значения могут повторяться, т. к. один и тот же клиент мог приобрести несколько товаров. Эта таблица связана с таблицей Клиенты по столбцу Имя_клиента, т. е. столбец Имя_клиента первой таблицы (Продажи) ссылается на одноименный столбец второй таблицы (Клиенты). Другими словами, данные таблицы находятся в родительско-дочернем отношении: таблица Клиенты родительская, Продажи — дочерняя. Данная связь между таблицами организуется путем объявления столбца Имя_клиента таблицы Продажи внешним ключом (FOREIGN KEY), ссылающимся на первичный ключ в таблице Клиенты (см. разд. 7.2.3).

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

1.5. Нормализация таблиц

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

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

Рассмотрим в качестве примера таблицу Продажи (Клиент, Товар, Количество, Цена), показанную на рис. 1.12.

Рис. 1.12. В этой таблице могут возникнуть аномалии модификации

В  таблице, показанной на рис. 1.12, могут возникнуть аномалии модификации данных. Предположим, было решено удалить из нее запись о клиенте "ОАО "Рога и копыта", поскольку теперь он ничего не приобретает в вашей фирме. Но тогда вы потеряете информацию и цене на "Хвосты". Если же вам потребуется добавить запись о каком-нибудь новом товаре, то необходимо добавить и сведения о покупателе и количестве этого товара. А если пока такого покупателя нет?

Аномалия модификации, возникшая в рассмотренном примере, обусловлена тем, что данная таблица содержит информацию, относящуюся к различным темам. В ней есть сведения и о том, что приобрели покупатели, и о цене товаров. Лучше разбить ее на две таблицы, посвященные двум различным темам: Продажи_клиенты и Прайс_лист, показанные на рис. 1.13.

Рис. 1.13. Результат декомпозиции таблицы Продажи

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

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

1.     Первая нормальная форма (1НФ)

2.     Вторая нормальная форма (2НФ)

3.     Третья нормальная форма (3НФ)

4.     Нормальная форма Бойса-Кодда (НФБК)

5.     Четвертая нормальная форма (4НФ)

6.     Пятая нормальная форма (5НФ)

Все нормальные формы вложены друг друга в следующем смысле: таблица в 2НФ является также и таблицей в 1НФ; таблица в 3НФ является таблицей и в 2НФ, и в 1НФ, и т. д.

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

Далее мы кратко рассмотрим первые три наиболее важные для практики нормальные формы, а также доменно-ключевую нормальную форму.

1.5.1. Первая нормальная форма

Любая таблица, удовлетворяющая определению отношения, находится в 1НФ. Вот основные характеристики таблицы в 1НФ:

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

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

      в каждой ячейке таблицы должно находиться только единственное значение;

      у каждого столбца должно быть уникальное имя;

      все строки (записи) в таблице должны быть различными;

      порядок расположения столбцов и строк таблице не имеет значения.

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

1.5.2. Вторая нормальная форма

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

Рассмотрим пример отношения Секции (Имя, Секция, Плата), показанный на рис. 1.14.

Рис. 1.14.  Отношение Секции (Имя, Секция, Плата)

Ключом в данном отношении является {Имя, Секция}, но оно содержит функциональную зависимость СекцияПлата. Аргумент (левая часть) этой зависимости является лишь частью составного ключа. Отношение Секции имеет аномалии удаления и добавления. Так, если мы захотим удалить записи с именем "Иванов", то потеряем стоимость шахматной секции. Мы не сможем добавить запись о новой секции, пока в нее кто-нибудь не запишется. Данных аномалий можно было бы избежать, если бы атрибут Плата зависел от всего ключа (однозначно определялся всем ключом).

Отношение Секции (Имя, Секция, Плата) в 1НФ можно разбить на два отношения во 2НФ:

      Секция_члены (Имя, Секция);

      Секция_плата (Секция, Плата).

1.5.3. Третья нормальная форма

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

Рассмотрим в качестве примера отношение Гости (ID_гостя, Тип_номера, Плата), представляющее сведения о проживающих в гостинице. Ключом в этом отношении является ID_гостя, Плата однозначно определяется атрибутом Тип_номера (например, люкс, полулюкс и т. д.), т. е. имеется функциональная зависимость Тип_номераПлата. Поскольку каждый гость проживает только в одном номере определенного типа, в отношении есть и функциональная зависимость ID_гостяТип_номера. Таким образом, возникает транзитивная (опосредованная) зависимость ID_гостяПлата. Так как ключ состоит из единственного атрибута ID_гостя, то отношение находится в 2НФ.

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

Чтобы устранить указанную аномалию, следует декомпозировать исходное отношение Гости (ID_гостя, Тип_номера, Плата) на два:

      Проживание (ID_гостя, Тип_номера);

      Тип_плата (Тип_номера, Плата).

Эти отношения будут находиться в 2НФ и не содержать транзитивных зависимостей.

Таким образом, отношение находится в 3НФ, если оно находится в 2НФ и не содержит транзитивных зависимостей.

1.5.4. Доменно-ключевая нормальная форма

Если таблица находится в 3НФ, то остается довольно мало шансов для возникновения аномалий модификации данных, но они есть. Чтобы исключить все виды возможных аномалий, таблица должна находиться в доменно-ключевой нормальной форме (ДКНФ).

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

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

1.5.5. Денормализация

Чтобы исключить как можно больше аномалий модификации данных, старайтесь как можно больше нормализовать таблицы базы данных. Лучше, если вы доведете их до ДКНФ, хотя на практике это редко происходит. Чаще ограничиваются второй или третьей нормальными формами. Занимаясь нормализацией, вы увеличиваете количество таблиц в базе данных и при определенном их числе эффективность работы может оказаться слишком низкой. Кроме того, формулировать SQL-запросы к базе данных тем легче, чем меньше в ней таблиц. Так что, на любом этапе своего развития база данных может быть в какой-то степени денормализованной.

Основы реляционных баз данных

1.1. Множества

1.2. Отношения

1.2.1. Общие сведения

1.2.2. Способы представления отношений

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

Селекция

Проекция

Естественное соединение

1.3. Декомпозиция отношений

1.3.1. Корректная декомпозиция

1.3.2. Пример некорректной декомпозиции

1.3.3. Зависимости между атрибутами

Функциональные зависимости

Многозначные зависимости

1.3.4. Правила вывода зависимостей

1.3.5. Ключи

1.4. Ограничения целостности отношений

1.4.1. Семантическая целостность

1.4.2. Доменная целостность

1.4.3. Ссылочная целостность

1.5. Нормализация таблиц

1.5.1. Первая нормальная форма

1.5.2. Вторая нормальная форма

1.5.3. Третья нормальная форма

1.5.4. Доменно-ключевая нормальная форма

1.5.5. Денормализация