Database Programming & Design

       

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


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

В число определенных Коддом операций входят перестановка (permutation), проекция (projection), соединение (join), связывание (tie) и композиция (composition) (в статье 1970-го г. добавлена операция ограничения (restriction), которую я описываю здесь для удобства). Интересно заметить, что определения ограничения и соединения отличаются от тех, которые используются сегодня, а операции связывания и композиции теперь редко принимаются во внимание. В том, что следует ниже, символы X, Y, ... (и т.д.) по мере необходимости обозначают либо индивидуальные атрибуты, либо комбинации атрибутов. Кроме того, по причинам, которые скоро будут понятны, определение соединения откладывается до конца раздела.

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

Проекция. Понималась более или менее так же, как и сегодня (хотя синтаксис был другим; далее я буду использовать синтаксис R{X} для обозначения проекции R на X). Замечание: название "проекция" происходит из того факта, что отношение степени n можно рассматривать как представление точек в n-мерном пространстве, и к проекции этого отношения на m его атрибутов (mСвязывание.
Для данного отношения A{X1,X2,...,Xn} связывание A - это ограничение A до тех строк, в которых A.Xn = A.X1 (если использовать термин "ограничение" в его современном смысле, а не в специальном смысле, определяемом ниже.)

Композиция. Для данных отношений A{X,Y} и B{Y,Z} композицией A c B называется проекция на X и Z соединения (a join) A с B (причина, по которой я говорю "a join", а не "the join", объясняется ниже). Замечание: естественная композиция - это проекция на X и Z естественного соединения.

Ограничение. Для данных отношений A{X,Y} и B{Y} ограничение A по B определяется как максимальное подмножество A такое, что A{Y} является подмножеством -- не обязательно точным -- B.

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

Приступим теперь к определению соединения. Для данных отношений A{X,Y} и B{Y,Z} соединение A с B в статье определяется как любое отношение C{X,Y,Z} такое, что C{X,Y} = A и C{Y,Z} = B. Заметим, что следовательно A и B можно соединить (или они "соединяемы"), только если их проекции на Y идентичны -- т.е. только если A{Y} = B{Y}, условие, которое вряд ли удовлетворяется на практике. Также заметим, что если A и B соединяемы, то могут существовать различные соединения (в общем случае). Хорошо известное естественное соединение -- называемое в статье линейным естественным соединением, чтобы отличить его от другого вида, именуемого циклическим соединением -- это важный частный случай, но не единственно возможный.

Однако странно то, что приводимое в статье определение естественного соединения не требует соединяемости A и B в приведенном специальном смысле! На самом деле, это определение почти такое же, как то, которое мы используем сегодня.



Постараюсь объяснить, откуда берется это довольно ограничительное понятие "соединимости". Кодд начинает свое обсуждение соединений с важного вопроса: При каких условиях соединение двух отношений сохраняет всю информацию, содержащуюся в этих двух отношениях? И он показывает, что свойство "соединяемости" является достаточным для обеспечения сохранения всей информации (поскольку в результате соединения не теряется ни одна строка ни одного операнда). Далее он также показывает, что если A и B соединяемы, и либо A.X функционально зависит от A.Y либо B.Z функционально зависит от B.Y, то естественное соединение является единственным возможным соединением (хотя реально он не использует терминологию функциональных зависимостей -- это также оставлено на будущее). Другими словами, Кодд здесь закладывает фундамент важнейшей теории декомпозиции без потерь (которую он, конечно, развил в последующих статьях).

Замечательно, что Кодд также приводит пример, показывающий, что уже в 1969 г. он осознавал тот факт, что некоторые отношения не могут быть декомпозированы без потерь в две проекции, но могут быть декомпозированы без потерь в три проекции! Этот пример был, очевидно, не замечен большинством первоначальных читателей статьи; во всяком случае для исследовательского сообщества оказалось неожиданностью повторное открытие этого факта несколькими годами позже. Именно это повторное открытие привело к изобретению Рональдом Фейджином окончательной нормальной формы 5NF, называемой также нормальной формы проекции-соединения (PJNF).


Содержание раздела