Хомоненко А.Д., Цыганков В.М., Мальцев М.Г. - Базы данных. Учебник для высших учебных заведений (6-е изд.) - 2009 (1084484), страница 16
Текст из файла (страница 16)
Как отмечалось, результатом произвольной реляционной операции является отношение, которое, в свою очередь, может участвовать в другой реляционной операции. Это свойство реляционной алгебры называется свойством замкнутости.Свойство замкнутости позволяет записывать вложенные выражения реляционной алгебры, основой которых выступают рассмотренные ранее элементарные операции: объединение, проекция, пересечение, выборка и т. д.При записи произвольного выражения реляционной алгебры надо принимать во внимание следующее.1.
В реляционной алгебре должен быть определен приоритет выполненияопераций (например, операция пересечение более приоритетна чем операция объединение), который нужно учитывать при записи выражений.Для изменения порядка выполнения операций в выражениях можно использовать круглые скобки.3. Реляционнаямодельданных792. Существуют тождественные преобразования, позволяющие по-разномузаписывать одно и то же выражение.
Например, следующие выраженияэквивалентны (здесь А — отношение, С, CI, С2 — выражения):A W H E R E CI AND С2 и (A W H E R E C I ) INTERSECT (A W H E R E С2),A W H E R E С1 OR С2 и (A W H E R E C I ) UNION (A W H E R E С2),A W H E R E N O T С и A MINUS (A W H E R E С).3. Составляя выражение, нужно обеспечивать совместимость участвующихв операциях отношений. При необходимости изменения заголовков следует выполнять переименование атрибутов.3 .
7 . Реляционное исчислениеКак отмечалось ранее, принципиальное различие между реляционной алгеброй и реляционным исчислением состоит в том, что в первом случае процесс получения искомого результата описывается явным образом путем указания набора операций, которые надо выполнить для получения результата,а во втором — указываются свойства искомого отношения без конкретизациипроцедуры его получения.Внешне подходы сильно различаются: один из них предписывающий (реляционная алгебра), а другой описательный (реляционное исчисление). Наболее низком уровне рассмотрения подходы эквивалентны, так как любые выражения реляционной алгебры могут быть преобразованы в семантически эквивалентные выражения реляционного исчисления и наоборот.
Возможностьтакого преобразования доказывалась многими авторами, в частности, для этого можно использовать алгоритм редукции Кодда.Для названного алгоритма преобразования покажем на содержательномуровне возможности формулировки одного и того же запроса с помощью реляционной алгебры и реляционного исчисления на простом примере.Пусть запрос выглядит следующим образом: «Получить номера и городапоставщиков, выпускающих деталь Р2».Словесно алгебраическая версия этого запроса описывается так:• образовать естественное соединение отношений S и SP по атрибуту П#;• выбрать из результата этого соединения кортежи с деталью Р2 (в поле Д #должна быть строка Р2);• с п р о е ц и р о в а т ь результат предыдущей операции на атрибуты П # иГород_П.Этот же запрос в терминах реляционного исчисления можно сформулировать примерно гак: «Получить атрибуты П# и Город_П для таких поставщиков, для которых существует поставка в отношении SP с тем же значениематрибута П# и со значением Р" атрибута Д#».Часть 1.
Основы построения80базданныхРезультатом выполнения запроса будет отношение R вида:п#ГородПS1МоскваS2КиевS3КиевS4МоскваЧитатель может самостоятельно убедиться в этом, проделав описанныевыше операции реляционной алгебры.Преимуществом реляционного исчисления перед реляционной алгебройможно считать то, что пользователю не требуется самому строить алгоритмвыполнения запроса. Программа СУБД (при достаточной ее интеллектуальности) сама строит эффективный алгоритм.Отметим, что поставленную задачу выборки можно решить более оптимально с точки зрения потребности в оперативной памяти.
Более экономичный вариант решения в терминах операциях реляционной алгебры выглядит так:• выбрать из отношения SP кортежи, относящиеся к детали Р2;• выполнить естественное соединение отношения S и отношения, полученного на предыдущем шаге;• спроецировать текущее отношение на атрибуты П# и Город_П.Экономия памяти при реализации этого алгоритма в сравнении с первоначальным вариантом достигается за счет снижения размерности участвующих в операциях временных таблиц, необходимых для хранения промежуточных результатов. Если в предыдущем случае размерность временнойтаблицы была 12*6 (12 строк на 6 колонок), то в последнем случае — 4*6.Математической основой реляционного исчисления является исчисление предикатов — один из разделов математической логики.
Понятие реляционного исчисления как языка работы с базами данных впервые предложено Коддом. Им же был разработан язык ALPHA — прототип программнореализованного языка QUEL, который некоторое время конкурировалс языком SQL.Существует два варианта исчислений: исчисление кортежей и исчисление доменов. В первом случае для описания отношений используются переменные, допустимыми значениями которых являются кортежи отношения,а во втором случае — элементы домена.Реляционное исчисление, основанное на кортежах {исчисление кортежей),предложено и реализовано при разработке упоминавшегося языка ALPHA.В нем, как и в процедурных языках программирования, сначала нужно описать используемые переменные, а затем записывать некоторые выражения.3.
Реляционнаямодельданных81Описательную часть исчисления можно представить в виде:RANGE O F <переменная> IS <список>,где прописными буквами записаны ключевые слова языка, <переменная> — идентификатор переменной кортежа (области значений), а <список> — последовательность одного или более элементов, разделенных запятыми, то естьконструкция вида: х, [, х2 [..., хп]...].Вся конструкция RANGE указывает идентификатор переменной и областьее допустимых значений. Список элементов х, [, х2 [...
, xj...] содержит элементы, каждый из которых является либо отношением, либо выражением надотношением (порядок записи выражений описывается далее). Все элементысписка должны быть совместимы по типу, то есть соответствующие элементам отношения должны иметь идентичные заголовки. Область допустимыхзначений <переменной> образуется путем объединения значений всех элементов списка.
Так, запись вида RANGE O F Т IS XI,Х2 означает, что областьопределения переменной Т включает в себя все значения из отношения, которое является объединением отношений XI и Х2.Пример 1. Варианты описаний.RANGE O F SX IS S;RANGE O F SPX IS SP;RANGE O F SY IS (SX) W H E R E 5Х.Город_П = 'Москва',(SX) W H E R E EXISTS SPX ( S P X . n # = S X . n # AND5РХ.Д# = 'Pi');Переменные SX и SPX в первых двух примерах определены соответственно на отношениях S и SP соответственно (рис. 3.7). Третий пример иллюстрирует запись выражений при определении переменной кортежа. Переменная SY здесь может принимать значения из множества кортежей отношения Sдля поставщиков из Лондона или поставщиков, которые поставляют детальР1 (или для тех и других).Синтаксис выражений исчисления рассматривается ниже.
Запись выражения, формулирующего запрос на языке исчисления кортежей с помощью формы Бэкуса-Наура, упрощенно можно представить следующим образом:<выражение> ::= (у, [, у2 [..., у т ]...]) [ W H E R E wff ]у ::= {<переменная> | <переменная>.<атрибут> } [ AS <атрибут> ]Wff ::= <условие> |NOT wff |<условие> AND wff |<условие> OR wff |IF <условие> THEN wff |EXISTS <переменная> (wff) |FORALL <переменная> (wff) |(wff)Часть 1. Основы82построениябазданныхОбщий смысл записи выражения состоит в перечислении атрибутов результирующего (целевого) отношения, атрибуты которого должны удовлетворять условию истинности формулы wff (well formulated formula — правильнопостроенная формула). Список атрибутов целевого отношения, или целевойсписок, в терминах реляционной алгебры по существу определяет операциюпроекции, а формула wff — селекцию кортежей.В паре <переменная>.<атрибут> первая составляющая служит для указания переменной кортежа (определенной конструкцией RANGE), а вторая —для определения атрибута отношения, на котором изменяется переменнаякортежа.
Необязательная часть «AS <атрибут>» используется для переименования целевого отношения. Если она отсутствует, то имя атрибута целевого отношения наследуется от соответствующего имени атрибута исходногоотношения.Употребление в качестве элемента целевого отношения просто имени переменной Т равносильно перечислению в списке всех соответствующих атрибутов, т. е.
Т.А ( , Т.А2, ... , Т.А п , где AJf А2, ... , Ап — атрибуты отношения,сопоставляемого с переменной Т.Пример 2. Варианты записи пары <переменная>.<атрибут>.sx.n#S X . n # AS Город_ПоставщикаSXSXXI#, 5Х.Город_П AS Город_Г1оставщика, РХ.Д#, РХ.Город_Д# ASГород_ЛеталиВ приведенном определении wff <условие> представляет собой либо формулу wff, заключенную в скобки, либо простое сравнение вида:<операнд1> О <операнд2>,где в качестве любого операнда выступает переменная или скалярная константа, а символ © обозначает операцию сравнения =, Ф, >, >, <, < и т. д.Ключевые слова NOT, AND и OR обозначают логические операции соответственно: И, НЕ и ИЛИ.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
