Мотивация и обоснование
Мотивация и обоснование
Для простоты в этом разделе используется не слишком формальный подход. В частности, вместо введенного в третьей главе формального определения кортежа здесь под кортежем понимается разделяемый запятыми список значений. Поскольку в этой главе активно используются идеи логики предикатов, требуется сделать короткие замечания по поводу терминологии:
Разработка алгебры A мотивируется следующими целями:
Вот более подробное обсуждение четырех принципиальных отличий A от предшествовавших алгебр.
Отсутствие TIMES
Когда в логике два предиката соединяются связкой and, нужно обращать внимание на имена заменителей. Любое имя заменителя, которое появляется в обоих предикатах, должно пониматься как обозначающее одно и то же в новообразованном предикате. Например, рассмотрим два предиката, выраженные на естественном языке: "Служащий E работает в отделе D" и "Служащий E работает над проектом J".
Связка этих двух предикатов с использованием and порождает триадный, а не тетрадный предикат: "Служащий E работает в отделе D и служащий E работает над проектом J". Этот предикат можно представить в сокращенной форме "Служащий E работает в отделе D над проектом J", чтобы подчеркнуть тот факт, что мы не можем подставить некоторого конкретного служащего для E, который работает в отделе D, не подставив того же служащего для E, работающего над проектом J. Это наблюдение позволяет заметить, что заменители тесно связаны с хорошо известной операцией естественного соединения и, конечно, с операцией >AND< алгебры A.
Что касается операции TIMES, она, конечно, является частным случаем соединения (>AND< в алгебре A). Более точно, TIMES соответствует связке через and двух предикатов без общих заменителей, например, "Служащий E работает в отделе D, и у проекта J имеется бюджет B".
Кстати, приведенная выше сокращенная формулировка предиката может привести к ошибочному заключению, что проект J каким-то образом связан с отделом D. Кодд называл этот вид ошибок "ловушкой связи", а позже его иногда называли "ловушкой соединений", что не очень удачно, поскольку ситуация не уникальна для соединений и реляционных операций вообще.
Отсутствие UNION
Предикаты естественного языка могут комбинироваться не только с помощью and, но и с помощью or. Триадному предикату "Служащий E работает в отделе D или служащий E работает над проектом J" соответствует тернарное отношение. Если служащий EX работает в отделе DX, то кортеж (EX, DX, J) входит в тело этого отношения для всех возможных проектов J независимо от того, работает ли реально служащий EX над проектом J (и даже независимо от того, выполняется ли проект J в это время в компании). Аналогично, если служащий EX работает над проектом JX, то кортеж (EX, D, JX) входит в тело отношения для всех возможных отделов D независимо от того, работает ли реально служащий EX в отделе D (и даже независимо от того, существует ли отдел D в это время в компании).
Операция >OR< вводится в алгебру A как двойник операции or. Классическая операция UNION является частным случаем >OR< и соответствует связыванию через or двух предикатов, которые содержат в точности один и тот же набор заменителей, например, "Служащий E работает в отделе D или служащий E прикомандирован к отделу D".
Здесь и далее Д&Д умышленно оставляют в стороне вычислительные проблемы выполнения операции.
Отсутствие MINUS
Пусть WORKS_IN - это отношение с атрибутами E (служащий) и D (отдел), а соответствующий предикат - "Служащий E работает в отделе D". Тело логического дополнения (>NOT<) этого отношения состоит из всех возможных кортежей в форме (E, D), для которых неверно, что служащий E работает в отделе D.
Чтобы показать возможность устранения операции MINUS, рассмотрим следующий пример. Предположим, что в придачу к отношению WORKS_IN имеется отношение WORKS_ON с атрибутами E и J (проект), а соответствующий предикат - "Служащий E работает над проектом J". Рассмотрим теперь унарное отношение, соответствующее монадному предикату "Служащий E работает в некотором отделе, но не работает ни над каким проектом". К алгебре Кодда это отношение можно было бы получить, спроецировав отношения WORKS_IN и WORKS_ON на атрибут E и взяв затем соответствующую разность. В алгебре A мы сначала проецируем WORKS_ON на E, а затем берем >NOT< от этой проекции; соответствующим предикатом будет "Не существует такого проекта, над которым бы работал служащий E". Потом это отношение можно соединить (>AND<) с отношением WORKS_IN, и проекция этого соединения на E даст искомый результат.
Отсутствие restrict (WHERE), EXTEND и SUMMARIZE
При выполнении restrict (WHERE), EXTEND и SUMMARIZE требуются вызовы некоторых операций. В случае restrict эти операции возвращают значения (инстинностные значения), используемые для предотвращения появления некоторых кортежей в результирующем отношении; в случае EXTEND и SUMMARIZE операции возвращают значения, на основе которых определяются некоторые атрибуты результирующего отношения.
Для целей Д&Д имеет смысл и может быть полезно рассматривать такие операции как отношения. Рассмотрим операцию Op, являющуюся скалярной функции (операцию, возвращающую в точности один результат, являющийся скалярным значением). Предположим, что у Op имеется n параметров. Тогда можно трактовать Op как отношение с n+1 атрибутами, по одному на каждый параметр и один на результат. Конечно, атрибуты, соответствующие параметрам, образуют возможный ключ этого отношения; однако это возможный ключ может не быть единственным. Например, если PLUS - это отношение с атрибутами X, Y и Z, тип каждого из которых INTEGER, и это отношение соответствует скалярной функции "+" целой арифметики и предикату "X + Y = Z", то возможными ключами отношения являются комбинации {X, Y}, {X, Z} и {Y, Z}, а в тело отношения входит по одному кортежу (X, Y, Z) для всех возможных комбинаций X, Y, Z, удовлетворяющих предикату.
Замечание: По аналогии с relvar можно относиться к отношениям типа PLUS как к relcon, или как к реляционным константам: они именованы, но их значения не изменяются во времени. И, конечно, упоминавшиеся возможные ключи - это ключи реляционной константы, а не реляционной переменной.
Итак, скалярная функция является частным случаем отношения. Более точно, любой отношение можно рассматривать как операцию, отображающее некоторое подмножество его атрибутов на оставшиеся атрибуты; если это отображение является функциональным (много-к-одному), то отношение можно считать функцией. Поскольку у множества из n элементов имеется 2n подмножеств, отношение степени n можно считать представлением 2n различных операций, некоторые из которых функции, а некоторые - нет (в общем случае). Например, если рассматривать PLUS как операцию, отображающую Z в X и Y, то это отображение не функционально (не поддерживаются функциональные зависимости ZX и ZY), и соответствующая операция не является функцией.
В следующем разделе показывается, что при подобной трактовке операций и наличии операций алгебры A >AND<, >REMOVE< и >RENAME< можно отказаться от непосредственной поддержки операций restrict, EXTEND и SUMMARIZE.
