Введение в системы БД (542480), страница 63
Текст из файла (страница 63)
° Для квантора РОКХЬЬ НХ делим текущий промежуточный результат на отношение "выбранной области значений", соответствующее КХ, которое было получено выше. Прн выполнении этой операции также будут исключены все атрибуты отношения г. Занечоиие. Под делением здесь подразумевается оригинальная операция деления Кодла (см. аннотацию к 16.3]). В нашем примере имеем следующие кванторы.
ЕХ1ЯТБ ЗХ РОНЬЬЬ РХ ЕХ1ЯТБ ЯРЮХ Значит, выполняются следующие операции. 1. (ЕХ1БТЯ БРАУХ) Проецируем, исключая атрибуты переменной-отношения ЯРЮ (БРЮ. БР, БРЮ.Р4, ЯРО.34 и ЯРО.ОТХ). В результате получаем следующее. Глава 7. Реляз4ионное исчисление 81 82 82 84 85 85 85 Б5 85 85 Ят до Юо С! Ад Ад Ад Ад Ад Ад 20 10 10 20 30 30 30 30 30 ЗО 1оп Раг Раг 1.оп А!Ь А1Ь АФЬ АФЬ АгЬ А1Ь Р1 РЗ РЗ Р6 Р2 Р1 РЗ Р4 Р5 Р6 511 Бс Бс СЕ Вг ыг Бс Бс Ст СЯ Кед В!це В1пе Кед Огееп Кей В! це Кед В1це Кед 12.0 17.0 17.0 19. О 17.0 12.0 17.0 14.0 12.0 19. 0 1.оп Кот Кот 1лп Раг 1.оп Кот 1.оп Раг 1лп 34 33 Л4 33 34 34 34 Ю4 54 Л4 Сп ОК Сп ОК Сп Сп Сп Сп Сп Сп АГЬ А1Ь А$Ь А1Ь АгЬ АгЬ А1Ь А1Ь АСЬ А1Ь Б1 Б2 Б2 84 Я5 Б5 Б5 Я5 Б5 Я5 Р1 РЗ РЗ Р6 Р2 Р1 РЗ Р4 Р5 Р6 34 33 34 53 34 34 34 34 34 14 700 200 200 300 100 100 200 800 400 500 ЯТАТУЯ Р№ Р1Ч ЖЕ1СНТ з№ с1ту СОЬОК С1ту С1ту 2.
(ГОЕАЬЬ РХ) Делим полученный результат на отношение Р. В результате имеем следующее. 31Ч ЯТАТ173 С1Т г" З№ З1ЧАМЕ С1ТУ 35 Аг1ашя ЗО АФЬепя З4 Сопяо1е АГЬепя (Теперь у нас есть место, чтобы показать отношение полностью, без сокращений.) 1. (ЕХ1ЯТЯ ЛХ) Проецируем, исключая атрибуты отношения Ю (5.55, Ю.ЕАМЕ и Ю. 01ТУ).
В результате получаем следующее. ЯТАТ113 С1ту Аг(ашя зо АФЬепя Этягг 5. Проецируем результат этапа 4 в соответствии со спецификациями в прототипе кортежа. В нашем примере прототип кортежа имеет следующий вид. (ЯХ.ЯНЕКЕ, ЯХ.С1ТТ) Значит, конечный результат вычислений будет таков. С1ту Абашя АГЬепа Из сказанного выше следует, что начальное выражение исчисления семантически эквивалентно определенному вложенному алгебраическому выражению, и, если быть более точным, это проекция от проекции результата деления проекции выборки из произведения четырех выборок (!). Этим мы завершаем обсуждение примера.
Конечно, можно намного улучшить используемый алгоритм (глава 17, в частности аннотация к [17.51). И хотя многие подробности в пояснениях были опущены, этот пример вполне адекватно отражает общую идею работы алгоритма редукции. Кстати, теперь можно объяснить одну из причин (и не только одну) определения Коддом ровно восьми алгебраических операторов.
Эти восемь реляционных операторов образуют удобный целевой язык как средство возможной реализации реляционного исчисления. Другими словами, для заданного языка, построенного на основе реляционного исчисления (подобно языку 1 ()ЕЬ), один нз возможных подходов реализации заключа- 260 Часть П. Реляционная модель 31 яг 82 34 35 35 35 35 35 85 Яп1 ао зо С1 Аб Аб Аб Аб Аг( Аг( 2О 1О 1О 20 зо зо зо зо зо зо Ьоп Раг Раг Ьоп АГЬ АгЬ А$Ь АгЬ АГЬ АГЬ Р1 РЗ РЗ Р6 Р2 Р1 РЗ Р4 Р5 Р6 1ЧГ Яс Яс СЕ Вг 1ЧГ Яс Яс Сш се Кеб В!пе В!не Кез Сгееп Кез В1пе Кем В1пе Кез 12.0 17.0 17.0 19.0 17.0 1г.о 17.0 14.0 12.0 19.0 1.оп Кот Кот 1оп Раг 1оп Кот 1 оп Раг 1.оп 24 зз а4 зз 14 З4 )4 З4 З4 а4 Сп ОК Сп ОК Сп Сп Сп Сп сп Сп АГЬ АГЬ АСЬ АгЬ АгЬ АГЬ АГЬ АГЬ АсЬ АгЬ ется в том, что организуется получение запроса в том виде, в каком он предоставляется пользователем. По существу, он будет являться просто выражением реляционного исчисления, к которому затем можно будет применить определенный алгоритм редукции, чтобы получить эквивалентное алгебраическое выражение.
Зто алгебраическое выражение, конечно, будет включать набор алгебраических операций, которые по определению реализуемы по самой своей природе. (Следующий этап состоит в оптимизации полученного алгебраического выражения, о чем речь пойдет в главе ! 7.) Также следует отметить, что восемь алгебраических операторов Кодда являются мерой оценки выразительной силы любого языка баз данных. Зто обстоятельство уже кратко упоминалось в главе 6, в конце раздела 6.6, а сейчас пришло время обсудить его подробнее.
Некоторый язык принято называть реляционно полным, если он по своим возможностям по крайней мере не уступает реляционному исчислению. Иначе говоря, любое отношение, которое можно определить с помошью реляционного исчисления„можно определить и с помошью некоторого выражения рассматриваемого языка (6.!). (В главе 6 отмечалось, что "реляционно полный" значит "не уступаюший по возможностям реляционной алгебре*', а не исчислению, но, как читатель вскоре убедится, это одно и то же. По сути, из самого существования алгоритма редукции Кодда немедленно следует, что реляционная алгебра обладает реляционной полнотой.) Реляционную полноту можно рассматривать как основную меру выразительной силы языков баз данных в самом общем случае.
В частности, так как реляционное исчисление и реляционная алгебра обладают реляционной полнотой, они могут служить основой для проектирования не уступающих им по выразительности языков без необходииости выполнять пересортировку для организации циклов. Зто замечание особенно важно, если язык предназначается для конечных пользователей, хотя оно также существенно, если язык предназначается для использования прикладными программистами. Далее, поскольку алгебра обладает реляционной полнотой, для доказательства того, что некоторый язык !.
также обладает реляционной полнотой, достаточно показать, что в языке !. есть аналоги всех восьми алгебраических операций (на самом деле достаточно показать, что в нем есть аналоги пяти примитивных операций) и что операндами любой операции языка !. могут быть любые выражения этого языка. Язык З()!. — это пример языка, реляционную полноту которого можно доказать указанным способом (упр.
7.9). Язык (!0Е!. — еше один пример подобного языка. В действительности на практике часто проще показать то, что в языке есть эквиваленты операций реляционной алгебры, чем то, что в нем существуют эквиваленты выражений реляционного исчисления. Именно поэтому реляционная полнота обычно определяется в терминах алгебраических выражений, а не в терминах выражений реляционного исчисления. При этом важно понимать, что реляционная полнота необязательно влечет за собой полноту какого-либо другого рода. Например, желательно, чтобы язык также обеспечивал "вычислительную полноту", т.е. позволял вычислять результаты всех вычислимых функций.
Заметим, что согласно нашему определению исчисление не обладает полнотой такого рода, хотя на практике подобная полнота для языка баз данных весьма желательна. Вычислительная полнота — это один из факторов, побудивших ввести в реляционную алгебру операции ЕХТЕЕ!З и ЕШИМ1ЕЕ (обсуждавшиеся в главе 6). В следуюшем разделе описано, как можно расширить реляционное исчисление, чтобы обеспечить в нем наличие аналогов этих операций. Глава 7. Реляционное исчисление 261 Вернемся к вопросу эквивалентности алгебры и исчисления. Мы на примере показали, что любое выражение исчисления можно преобразовать в его некоторый алгебраический эквивалент, а значит, алгебра по крайней мере не уступает по своей мощности исчислению. Можно показать обратное: каждое выражение реляционной алгебры можно преобразовать в эквивалентное выражение реляционного исчисления, а значит, исчисление по крайней мере не уступает по своей мощности реляционной алгебре.
Полное доказательство этих утверждений можно найти, например, в книге Ульмана (()Ишан) (7.)3). Отсюда следует, что реляционная алгебра и реляционное исчисление эквивалентны. 7.5. Вычислительные возможности Несмотря на то что ранее об этом не упоминалось, в определенном нами реляционном исчислении уже есть аналоги алгебраических операторов ЕХТЕИН и ЯНММАК1ХЕ, и вот почему. ° Одной из допустимых форм прототипа кортежа является параметр <олерация выборки кортежа>, компонентами которого могут быть произвольные подпара- метры <выражение>. ° В параметре <логическое выражение> сравниваемыми элементами могут быть произвольные подпараметры <выражение>.
° Первым или единственным аргументом в параметре <вызов обобяаюяей функции> является подпараметр <реляционная операция>. Замечание. Здесь мы ссылаемся на полное определение языка Тп(она! Р, которое приводится в (3.3]. Мы считаем, что не стоит приводить здесь все имеющие место синтаксические и семантические подробности; достаточно лишь рассмотреть несколько типичных примеров (сами примеры также несколько упрощены). 7.5.1. Определить номера и вес в граммах всех типов деталей, вес которых превышает 10 000 г ( РХ,РФ, РХЛЕ16НТ * 454 АЯ 6МИТ ) МНЕКЕ РХЛЕ16НТ * 454 > ИЕ16НТ ( 10000 ) Обратите внимание, что спецификация АЯ 6МИТ в прототипе кортежа дает имя соответствующему атрибуту резульеагна.
Поэтому такое имя недоступно для использования в предложении ИНЕКЕ и выражение РХ.НЕ16НТ " 454 должно быть указано в двух местах. 7.5.2. Выбрать сведения обо всех поставщиках, добавив для каждого из них литеральное значение 'Поставщик' ( ЯХ, 'Поставдик' АЯ ТА6 ) 262 Часть 11.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
