Введение в системы БД (542480), страница 62
Текст из файла (страница 62)
Определить имена поставщиков по крайней мере одной красной детали ЯХ.ЯНАНЕ ИНЕКЕ ЕХ?ЯТЯ ЯРХ ( ЯХ.Я» = ЯРХ.Я» АНО ЕХ?ЯТЯ РХ ( РХ.Р» = ЯРХ.Р» АНО РХ.СОЬОК = СОЬОК ( 'Кег)' ) ) ) Эквивалентная формула (но записанная в предваренной нормальной форме, в которой все кванторы помещаются в начало формулы %Гг) имеет следующий вид. ЯХ.ЯНАМЕ ИНЕКЕ ЕХ1ЯТЯ ЯРХ ( ЕХ1ЯТЯ РХ ( ЯХ.Я» -" ЯРХ.М АНО ЯРХ.Р» = РХ.Р» АНО РХ.СОЬОК = СОЬОК ( 'Кеб' ) ) ) 254 Часть П. Реляг(ионная модель Предваренная нормальная форма не является более (или менее) правильной по отношению к другим формам, но, немного попрактиковавшись, можно убедиться, что в большинстве случаев это наиболее естественный метод формулирования запросов Кроме того, она позволяет уменьшить количество используемых скобок, как показано ниже.
Например, рассмотрим следующую формулу %с Р. г)вапС1 чЫе1 ( паапС2 чЫе2 ( ИТТ ) ) Здесь каждый из кванторов г)аалС1 и паалС2 представляет или квантор ЕХ1ЯТБ, или квантор РОКАЬЬ. При необходимости ее всегда можно однозначно привести к следующему виду. пвапС1 чЫе1 г)папС2 чЫе2 ( н№№ ) Таким образом, зто выражение реляпионного исчисления можно переписать (при необходимости) следующим образом. ЯХ.БНАНЕ ИНЕКЕ ЕХ1ЯТЯ БРХ ЕХ1ЯТЯ РХ ( ЯХ.Я№ = БРХ.Я№ АИО БРХ.Р№ = РХ.Р№ АНО РХ.СОЬОК = СОЬОК ( 'Кеб' ) ) Однако для ясности будем продолжать показывать все скобки во всех остальных примерах. 7.3.5. Найти имена поставщиков по крайней мере одной детали, поставляемой поставщиком с номером 'Я2' БХ.ЯИАНЕ ИНЕКЕ ЕХ1БТБ БРХ ( ЕХ1БТЯ ЯРХ ( БХ.Б№ = ЯРХ.Б№ АИО ЯРХ.Р№ = ЯРХ.Р№ АНО БРХ Б№ — Б№ ( 'Б2' ) ) ) 7.3.6. Выбрать имена поставщиков всех типов деталей БХ.БНАНЕ ИНЕКЕ РОКАЬЬ РХ ( ЕХ1ЯТБ ЯРХ ( ЯРХ.Б№ = ЯХ.Б№ АМР БРХ.Р№ = РХ.Р№ ) ) Равносильное выражение можно записать без использования квантора РОКАЬЬ.
БХ.БИАНЕ ИНЕКЕ НОТ ЕХ1ЯТБ РХ ( НОТ ЕХТБТЯ ЯРХ ( ЯРХ.Б№ = ЯХ.Я№ АНО БРХ.Р№ = РХ.Р№ ) ) 7.3.7. Определить имена поставщиков, которые не поставляют деталь с номером 'Р2' ЯХ.ЯНАНЕ ИНЕКЕ НОТ ЕХТЯТЯ ЯРХ ( ЯРХ.Я№ = БХ,Я№ АНО ЯРХ.Р№ = Р№ ( 'Р2' ) ) Обратите внимание, как просто это решение можно получить из решения примера 7.3.3. 255 Глава 7. Реляционное исчисление 7.3.8. Определить номера поставщиков по крайней мере всех типов деталей, поставляемых поставщиком с номером '$2' БХ.Я4 ИНЕКЕ ГОКАЬЬ ЯРХ ( ЯРХ.Б4 к Я4 ( 'Я2' ) ОК ЕХ1ЯХЯ ЯРХ ( ЯРХ.Б4 = БХ.Я4 АБО БРХ.Р4 = БРХ.Р4 ) ) Переформулируем запрос в соответствии со следующим выражением: "Получить номера поставщиков (скажем, ЯХ), таких, что для всех поставок ЯРХ поставка осуществляется либо не от поставщика с номером 'Я2', либо существует поставка ЯРХ всех типов деталей, входящих в поставку ЯРХ от поставщика ЯХ".
Чтобы упростить формулировку таких сложных запросов, как этот, введем другое синтаксическое соглашение, называемое явной синтаксической формой для оператора логической импликации. Если р и и — формулы %ГЕ, то выражение логической импликации вида 1Р р ХНЕН Ч ЕИР 1Р также будет формулой %Гг с семантикой, идентичной семантике следующей формулы. ( Нот р ) ОК и Таким образом, приведенное выше выражение может быть переписано так. ЯХ.Я4 ЯНЕКЕ ГОКАЬЬ ЯРХ ( 1Г ЯРХ.Я4 = Б4 ( 'Б2' ) ХНЕН ЕХ1БХЯ БРХ ( ЯРХ.Я4 = БХ.Б4 АБО ЯРХ.Р4 = ЯРХ.Р4 ) ЕМО 1Р ) Дадим словесную формулировку этого запроса: "Получить номера поставщиков (скажем, ЯХ), таких, что для всех поставок БРХ в случае поставки от поставщика с номером 'Б2' существует поставка ЯРХ всех типов деталей, входящих в поставку БРХ от по- I ставщика БХ".
7.3.9. Получить номера деталей, которые либо весят более 16 фунтов, либо поставляются поставщиком с номером '42', либо и то, и другое КАНОЕНАК РО КАНОЕЯ ОЧЕК ( РХ.Р4 ИНКИ РХ.ИЕХант > ИЕХОНт ( 14.О) ), ( ЯРХ.Р4 ИНЕКЕ ЯРХ.Я4 = Я4 ( 'Я2' ) ) ) РУ.Р4 В эквивалентном выражении реляционной алгебры здесь могло бы использоваться явное объединение. Ради интереса покажем альтернативную формулировку этого запроса. Однако тот факт, что каждый номер детали в переменной-отношении БР присутствует и в переменной- отношении Р, делает вторую формулировку не соответствующей "стилю объединения".
256 Чисть 11. Реляционная модель 7.4. Сравнительный анализ реляционного исчисления и реляционной алгебры В начале этой главы утверждалось, что реляционная алгебра и реляционное исчисление в своей основе эквивалентны. Обсудим это утверждение более подробно. Вначале Кодд в (б,!1 показал, что алгебра по крайней мере мощнее исчисления.
Он сделал это, придумав алгоритм, называемый алгоритмом редукции Кодда, с помощью которого любое выражение исчисления можно преобразовать в семантически эквивалентное выражение алгебры. Мы не станем приводить здесь этот алгоритм полностью, а ограничимся довольно сложным примером, иллюстрирующим в общих чертах, как он функционирует4. БРч ЯЗГ РЗГ о ЗГ Тз' Рис. 7, !. База данных поставщиков, деталей и проектов (значения для примера) г В действителыгости олгоритчн представленный в !б. ! 1, содержит небольшую оьзибку 77.2!. Более того, определенная в этой статье версия реляционного исчисления не включала аналога оператора объединения, следовательно, исчисление Кодда значительно менее мощное, чеч его алгебра.
Кок бы там ни было, утверждение о том, что алгебра и исчисление, включающее аналог операции объединения. эквивалентны, является истиной, что доказано л~ногичи авторачи (б. (2!. 257 Глава 7. Релиз(ионное исчисление РХ.РР ИНЕНЕ РХ.ИЕИНТ > ИЕ10НТ ( 15.0 ) ОН ЕХХЯТЯ ЯРХ ( ЯРХ.Р(( = РХ.Р(( ((Н0 ЯРХ.Я(( = 34 ( Яг > > 81 Я1 Я2 Я2 Я2 Б2 Я2 Б2 Б2 82 ЯЗ ЯЗ Я1 84 Я5 Я5 Я5 85 85 Бб Б5 Б5 85 85 Р1 Р1 РЗ РЗ РЗ РЗ РЗ РЗ РЗ Р5 РЗ Р4 Р6 Р6 Р2 Р2 Р5 Р5 Р6 Р1 РЗ Р4 Р5 Р6 о1 ч4 ч1 о2 чЗ о4 йб о6 о7 !2 о1 32 ЗЗ 37 ч2 34 чб ч7 !2 ч4 о4 о4 о4 ч4 200 700 400 200 200 500 600 400 800 100 200 500 300 300 200 100 500 100 200 100 200 800 400 500 В качестве основы для нашего примера используется не привычная база данных поставщиков и деталей, а ее расширенная версия, упоминавшаяся в упражнениях главы 4 и в других главах.
Для удобства на рис. 7.1 приводится пример возможных значений для этой базы данных (это копия рис. 4.5 главы 4). Рассмотрим теперь следующий запрос: "Получить имена поставщиков и названия городов, в которых находятся поставщики деталей по крайней мере для одного проекта в Афинах ('АГЬепя'), поставляющих по крайней мере 50 штук каждой детали". Выражение реляпионного исчисления для этого запроса следующее. ( ЯХ.ЯНАНЕ, ЯХ.С!ТУ ) ННЕНЕ ЕХ1БТЯ ЮХ РОЕАЕЬ РХ ЕХ1БТЯ ЯРОХ ( ЮХ.С1ТУ = 'Аслепа' АЕР ЮХ.Л№ = ЯРчХ.ч№ АНР РХ.Р№ = БР!Х.Р№ АНР ЯХ.Я№ = БРЮХ.Я№ АНР БРЮХ.РТУ > ЦТХ ( 50 ) ) Здесь БХ, РХ, ЛХ и ЯРЮХ вЂ” переменные кортежей, получающие свои значения из переменных-отношений Я, Р, Ю и ЯРЮ соответственно.
Теперь покажем, как можно вычислить это выражение, чтобы достичь требуемого результата. Эглал 1. Для каждой переменной кортежа выбираем ее область значений (т.е. набор всех значений лля переменной), если это возможно. Выражение "выбираем, если возможно" подразумевает, что существует условие выборки, встроенное в фразу вНЕНЕ, которую можно использовать, чтобы сразу исключить из рассмотрения некоторые кортежи. В нашем случае выбираются следующие наборы кортежей. Ээлал2.
Строим декартово произведение диапазонов, выбранных на первом этапе. Вот результат. (И т.д.) Все произведение содержит 5чбь2*24 = ! 440 кортежей. Замечание. Для экономии места здесь это отношение полностью не приводится. Мы также не переименовывали атрибуты (хотя это следовало бы сделать во избежание двусмысленности), а просто расположили их в таком порядке, чтобы было видно, какой атрибут Я№ относится, например, к отношению Б, а какой — к отношению ЯРЛ.
Это также сделано для сокращения изложения. 258 Часть 11. Реляционная модель БХ РХ ЮХ ЯРЮХ Все кортежи отношения Я Все кортежи отношения Р Кортежи отношения Ю, в которых С1ТХ = 'Аслепя ' Кортежи отношения ЯРУ, в которых С1ТУ > 50 5 кортежей б кортежей 2 кортежа 24 кортежа Эгпап 3. Осуществляем выборку из построенного на этапе 2 произведения в соответствии с частью "условие соединения" фразы ИНЕЕЕ. В нашем примере эта часть выглядит следующим образом. ЮХ.Ю$ = БРЮХ.ЛМ АНО РХ.РФ = БРЮХ.РМ АБО БХ.БР =ЯРЛХ.ЯФ Поэтому из произведения исключаются кортежи, для которых значение атрибута БР нз отношения поставщиков не равно значению атрибута 34 из отношения поставок, значение атрибута РР из отношения деталей не равно значению атрибута Р$ из отношения поставок, значение атрибута Ю$ из отношения проектов не равно значению атрибута 34 нз отношения поставок, Затем получаем подмножество декартова произведения, состоящее (как оказалось) только из десяти кортежей.
БТА- С!ТУ ТУБ СОЬОК ЧГЕ!СНТ 8№ Р№ 1№ ОТУ С1ТУ 4М С1ТУ !Это отношение, конечно, представляет собой эквивалент результата операции соединения.) Этап 4. Применяем кванторы в порядке справа налево следующим образом. ° Для квантора ЕХ1ЯТБ КХ (где ЙХ вЂ” переменная кортежа, принимающая значение на некотором отношении г) проеиируеи текущий промежуточный результат, чтобы исключить все атрибуты отношения г.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
