С.Д. Кузнецов - Основы баз данных (1121716), страница 20
Текст из файла (страница 20)
Известно, что этот набор традиционен, но избыточен, поскольку верны тождества А АМО В г— а НОТ (НОт А Он НО. В) и А Он  — = НОт (МОт А АКО НОт В). (Эти тождества легко проверяются по таблицам истинности операций.) Оказывается (и это тоже легко проверить, опираясь на определения операций), что аналогичные тождества справедливы лля операций <НОт>, <А)чп> и <Он> Алгебры А. Тем самым, в наборе базовых операций Алгебры А можно оставить операции <АНО> и <мст> (или <Он> и <мот>). Реляционные аналоги штриха Шеффера и стрелки Пирса Более того, в алгебре логики существуют две операции, через каждую из которых выражаются все три «базовые» операции: «штрих Шеффер໠— зп (А, В) = НОТ А ОН МОТ В вЂ” и «стрелка Пирс໠— р( (А, В) — МОТ А АХР ЖОТ В. Легко видеть, что ° з1: (А, А) — = НОТ А; ° эМ (МОТ А, НОТ В) — = А ОВ В и ° МОТ э1'.
(А, В) — = А ЖМП В. Алгебра А Дейта и Дараеиа Лекция 4 Аналогично, ° р) (А, А) — = нот А; ° р) (НОТ А, НОТ В) = — А АНП Ви а МОТ р) (А, В) т— в А ОК В. Снова нетрудно проверить, что аналогичные тождества справедливы для реляционныхвариантовштрихашсффера (<е)!> (г2, г2) = <нот> г2 <Ок> <ВОТ> г2) и стрелки Пирса (<р)> (г2, г2) — = <))ОТ> .г2 <АМ()> <НОТ> г2) .
Поэтому можно свести набор операций Алгебры А к трем операциям: <вм> (или <рт>), <кемлме> и <кемОче>. НОМЕРА ввовхтов служащие Раодвст (слу нОмеР, слу имя, слу ЗАРИ) 93 Основы баэ данных Курс (СЛУЖАЩИЕ РНООЕСТ (СЛУ НОМЕР, СЛУ НМЯ, С)ГУ ЗАРЕ)) Т1МЕЕ НОМЕРА ПРОЕЕТОВ СЛУ ЗАРЯ ПРО НОМ СЛУ НОМЕР СЛУ ИМЯ 2934 2934 2935 2935 2936 2936 Федоров 20000.00 2937 гоооо.оо Федоров 2937 2938 2938 Сидоренко 18000.00 2939 18000.00 2939 Сидоренко 2940 2940 22000.00 Иваненко 2941 22000.00 Иваненко 2941 ((СЛУЖАЩИЕ РНОдЕСТ (СЛУ НОМЕР, СЛУ НМЯ, СЛУ ЗАРП)) Т1МЕЕ НОИВРА ПРОЕЕТОВ) М1НПЕ СЛУЖАЩИЕ (СНУЖАЩИВ РНОЗЕСТ (СЛУ НОМЕР, СЛУ ММЯ, СЛУ ЗАРЕ)) Н1МОЗ ( ( ( (снужащив Рнозест ( с~ту номеР, слу нмя, Глу зАРП) ) т1меБ НОМЕРА НРОВЕТОВ) М1МОБ СЛУЛ(АЩИВ) РПОЗЕСТ ( СЛУ НОМЕР, СЛУ ЯМЯ, СЛУ ЗАРП)) Рис. 4.14.
Выражение операции вгугве ву через другие операции Алгебры А 94 Иванов Иванов Петров Петров Сидоров Сидоров Иванова Иванова Федоренко Федоренко 22400.00 22400.00 29600.00 29600.00 18000.00 18000.00 22000.00 22000.00 20000.00 20000.00 Алгебра А Дейта н Дарвина Лекция 4 Избыточноотьоперации переименования Наконец, покажем, что избыточна и операция <пемлме>. Для иллюстрации снова воспользуемся отношением служлщие из рис. 4.!4.
Пусть нам нужен результат операции спужлщИЕ <КЕМАМЕ> (ПРО Ном, НОМЕР ПРОЕКтй) (мы по-прежнему предполагаем, что множество значений домена атрибута пРО ном ограничено значениями, представленными в теле отношения служдщие). Возьмем бинарное отношение про ном нОмеР проектА (рис. 4.15), где каждый из кортежей содержит два одинаковых значения номера проекта и в тело отношения входят все значения домена атрибута ПРО НОМ.' Тогда, как показано на рис.
4.15, вычисление выражения (СПУЕАЩИЕ <Амп> прп НОМ нсмер ПРОектА) <кемоуе> (про ном1 приводит к желаемому результату Тем самым, можно сократить набор операций Алгебры А до двух операции: <я(з> (или <р») и <пемотге>.'* Заключение Базисом Алгебры А, являюшейся алгеброй отношений в строгом математическом смысле, являются операции реляционного отрицания (дополнения), реляционной конъюнкции (или дизъюнкции) и проекции (удаления атрибута). Реляционные аналоги логических операций определяются в терминах отношений на основе обычных теоретико-множественных операций и позволяют выражать напрямую операции пересечения, декартова произведения, естественного соединения и объединения отношений.
Путем комбинирования базовых операций выражаются операции переименования атрибутов, соединения обшего вида, взятия разности отношений. Алгебра А позволяет лучше осознать логические основы реляционной модели, хотя, безусловно, является в меньшей степени ориентированной на практическое применение, чем алгебра Ковда. Как нам кажется, в методическом отношении Алгебра А важна, прежде всего, тем, что в ней реляционная операция естественного соединения является одной из базовых операций, в отличие от алгебры Кодда, где эта операция имела второстепенное значение. Это важно по той причине, что, как мы увидим в лекции 7, операция естественного соединения играет первостепенную роль в классическом подходе к проектированию реляционных баз данных на основе нормализации.
' Это «константное» отношение, тело которого не зависит от текущего содержания тела отношения Сяудлдик. " И конечно, а Алгебре А, как и в алгебре Кодда, должна присутствовать операция присваивания переменной отношения, вб Лекция 5 Реляционное исчисление Лекция Б. Базисные средства манипулирования реляционными данными: реляционное исчисление Эта лекция завершает цикл лекций, посвященных маннпуляцнонному аспекту реляционной модели данных. Материал лекции интересен н сам по себе, поскольку демонстрирует, насколько аппарат математической логики упрощает формулировку запросов к базам данных. Ключевые слова: исчисление предикатов первого порядка, исчисление кортежей, кортежная переменная, оператор КАНОЕ, правильно построенная формула (%е!1-Гоппед Гоппп)а, %'ЕГ), операция импликации, метод вложенных циклов (пез!ед!оорз)о)п), квантор сушествования (ехтзтз), квантор всеобщности (РОНАее), свободная переменная, связанная переменная, числовые функции над множествами, целевой список ()агпе! Пм), выражение исчисления кортежей, исчисление доменов, условие членства, предикат членства, выражение исчисления доменов, язык запросов ( )вегу-Ьу-Ехатр!е.
Введение Предположим, что мы работаем с базой данных, которая состоит из отношений СЛУЖАЩИЕ (СЛУ НОМ, СЛУ ИМЯ, СЛУ ЗАРП, ПРО НОМ) иПРО- екты (НРО ном, НРОект РУК, ЛРО злвп) (вотношениипгоектыатрибут ЛРОект РУк содержит имена служаших, являющихся руководителями проектов, а атрибут ЛРО зАРп — среднее значение зарплаты, получаемой участниками проекта), и хотим узнать имена и номера служащих, которые являются руководителями проектов со средней заработной платой, превышающей ! 8000 руб. Если бы для формулировки такого запроса использовалась реляционная алгебра, то мы получили бы, например, следуюшее алгебраическое выражение: (СЛУЖАЩИЕ ЗО1Н ПРОЕКТЫ ХНЕКЕ (СЛУ ИМЯ = ПРОЕКТ РУК АНР ПРО ЗАРП > 18000.00)) РНОЗЕСТ (СЛУ ИМЯ, СЛУ НОМ) Это выражение можно было бы прочитать, например, следующим образом: ° выполнить зквисоединение отношений служАщие и пРОекты по условию СЛУ НОМ = ПРОЕКТ РУк; ° ограничить полученное отношение по условию ЛРО ЗАРП > 1 8000 .
00; ° спроецировать результат предыдущей операЦии на атрибут СЛУ ИМЯ, СЛУ НОМ. Мы четко сформулировали последовательность шагов выполнения запроса, каждый из которых соответствует одной реляционной операции. 97 Основы баэ данных Курс Если же сформулировать тот же запрос с использованием реляционного исчисления, которому посвяшается эта лекция, то мы получили бы два определения переменных: РззЧОЕ СЛУЖАЩИЩ тЯ ГлУЖАЩИЕ И НАМОК ПРОЕКТ ТЯ ПРОЕКТЫ и выражение СПУЖАДИЖ.ГЛУ ИМЯ, СЛУЖАЩИЕ.ГЛУ НОМ ИНЕНЕ ЕХТЯТЯ (СЛУЖАЩИЛ.СЛУ ИМЯ =- ПРОЕКТ. ПРОЕКТ РУК АНР ПРОЕКТ.ПРО ЗАРП > 6000.00). Это выражение можно было бы прочитать, например, следующим образом: выдать значения С,ТУ ИМЯ и СЛУ НОМ для каждого кортежа служаших такого, что сушествует кортеж проектов со значением ПРОЯКТ Рук, совпадающим со значением СЛУ НОИ этого кортежа служаших, и значением пго ЯАРп, большим ТЯ000,00.
Во второй формулировке мы указали лишь характеристики результируюшего отношения, но ничего не сказали о способе его формирования. В этом случае система сама должна решить, какие операции и в каком порядке нужно выполнить над отношениями служлщиЕ и ПРОЕКТЕ. Обычно говорят, что алгебраическая формулировка является процедурной, т. е. задающей последовательность действий для выполнения запроса, а логическая — описательной (или декларативной), поскольку она всего лишь описывает свойства желаемого результата. Как мы указывали в начале лекции 3, на самом деле эти два механизма эквивалентны, и сушествуют не слишком сложные правила преобразования одного формализма в другой.
Реляционное исчисление является прикладной ветвью формального механизма исчисления предикатов первого порядка.* В основе исчисления лежит понятие переменной с определенной для нее областью допустимых значений и понятие правильно построенной формулы, опираю- шейся на переменные, предикаты и кванторы. В зависимости от того, что является областью определения переменной, различают исчисление кортежей и исчисление доменов. В исчислении кортежей областями определения переменных являются тела отношений базы данных, т.
е. допустимым значением каждой переменной является кортеж тела некоторого отношения. В исчислении доменов областями определения переменных являются домены, на которых определены атрибуты отношений базы данных, т. е. допустимым значением каждой ' Это совсем не означает, что лля понимания этой лекции требуется знание исчисления преликатов. Автор стремился к тому, чтобы материал лекции был в основном самалостаточ ным. Реляционное исчисление Лекция 5 переменной является значение некоторого домена.
Мы рассмотрим более подробно исчисление кортежей, а в конце лекции коротко опишем особенности исчисления доменов. Как и в лекциях, посвященных реляционной алгебре, в этой лекции нам не удастся избежать использования некоторого конкретного синтаксиса, который мы тем не менее формально определять не будем. Те или иные синтаксические конструкции будут вводиться по мере необходимости. В совокупности используемый синтаксис близок, но не полностью совпадает с синтаксисом языка баз данных О()Е(., который долгое время являлся основным языком известной реляционной СУБД 1пжгек Исчисление кортежей Для определения кортежной переменной используется оператор КАНОЕ. Например, для того чтобы определить переменную СЛУжлщий, областью определения которой является отношение служлщие, нужно употребить конструкцию КАНОЕ СЛУЖАЩИЙ 15 СЛУЖАЩИЕ Как уже говорилось, из этого определения следует, что в любой момент времени переменная служлщий представляет некоторый кортеж отношения служАщие.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
