Лекция Базисные средства манипулирования реляционными данными: алгебра A Дейта и Дарвена

Введение

1. Базовые операции Алгебры A

2. Операция реляционного дополнения

3. Операция удаления атрибута

4. Операция переименования

5. Операция реляционной конъюнкции

6. Операция реляционной дизъюнкции

7. Полнота Алгебры A

8. Выводимость операции взятия разности

9. Интерпретация операции ограничения

10. Соединения общего вида

11. Реляционное деление

12. Избыточность Алгебры A

13. Реляционные аналоги штриха Шеффера и стрелки Пирса

14. Избыточность операции переименования

Заключение

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

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

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

Базисом предложенной Крисом Дейтом и Хью Дарвеном Алгебры A являются операции реляционного отрицания (дополнения), реляционной конъюнкции (или дизъюнкции) и проекции (удаления атрибута). Реляционные аналоги логических операций определяются в терминах отношений на основе обычных теоретико-множественных операций и позволяют выражать напрямую операции пересечения, декартова произведения, естественного соединения, объединения отношений и т. д.

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

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

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

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

Здесь необходимо пояснить, что отношение ЗАРП_20000 в действительности представляет собой литеральную константу соответствующего типа отношений. Мы не вводим здесь строгого понятия типа отношения; для понимания данного подраздела нужно всего лишь осознать, что по своей природе отношение ЗАРП_20000 и числовой литерал 20000.00 не различаются.

Отношение ЗАРП_БОЛЬШЕ_20000 – это тоже литеральная константа того же типа отношения, что и ЗАРП_20000, однако мощность тела этого литерального отношения в общем случае (если бы мы не ввели ограничения на множество значений домена СЛУ_ЗАРП) могла бы быть очень большой.

Особенность этого случая состоит в том, что число кортежей в теле литеральной константы ЗАРП_НЕ_22000 всего лишь на единицу меньше мощности множества значений домена СЛУ_ЗАРП. Конечно, эта мощность конечна, поскольку мы имеем дело с компьютерными типами данных, но в общем случае может быть очень большой. Поэтому принципиальная возможность выражения операции ограничения через операцию реляционной конъюнкции не означает, что было бы разумно реализовывать ее таким образом на практике.

Конечно, тот же результат даст и выражение СЛУЖАЩИЕ_1 <AND> ((((СЛУЖАЩИЕ_1 <REMOVE> СЛУ_РУК) <REMOVE> СЛУ_ИМЯ) <REMOVE> СЛУ_ЗАРП) <RENAME> (СЛУ_НОМЕР, РУК_НОМ)).

Конечно, в общем случае мощность тела такого константного отношения будет равна мощности соответствующего домена.

Легко убедиться, что в общем случае, если мощность общего домена атрибутов A и B равняется n, то мощность тела константного отношения A_БОЛЬШЕ_B будет составлять (n+1)n/2.

Это «константное» отношение, тело которого не зависит от текущего содержания тела отношения СЛУЖАЩИЕ.

И конечно, в Алгебре A, как и в алгебре Кодда, должна присутствовать операция присваивания переменной отношения.