Реляционное исчисление с переменными на доменах.

Различие состоит в следующем:

1. В исчислении с переменными на доменах не существует переменных-кортежей; вместо них существуют переменные на доменах, которые представляют компоненты кортежей.

2. Атом имеет вид:

а) в – n-арное отношение, где или переменной на домене. Эта запись указывает, что значения тех , которые являются переменными на доменах, должны быть выбраны так, чтобы было кортежем отношения .

б) ; или переменные на доменах; оператор сравнения; должны быть выбраны так, что – истинно.

3. Формулы в РИ с переменными на доменах используют связки и кванторы .

Свободные и связанные переменные определяются так же, как и в РИ с переменными кортежами.

Выражение РИ с переменными на доменах имеет вид: , (*)

где формула такая, что ее свободные переменные на доменах являются различными переменными .

Пример:

- отношение R₁ состоит из компонент x₁ и x₂ таких, что ни одна из них не является 1-й компонентой отношения R.

Выражение (*) называется безопасным, если:

1. Из истинности выражения .

2. Если подформула , то из истинности .

3. Если подформула , то из истинности .

Пример:

• имеет место для бинарных отношений и означает, что состоит из кортежей таких, что ни один из их компонентов не является первым компонентом какого-либо кортежа отношения .

Выражения исчисления с переменными на доменах эквивалентны выражениям исчисления с переменными-кортежами. Формализуем алгоритм перевода выражений исчисления с переменными-кортежами в выражения исчисления с переменными на доменах:

1. Если является кортежем арности n, то введем n новых переменных на доменах .

2. Атомы заменяются атомами .

3. Каждое свободное вхождение заменяется на x_i.

4. Для каждого квантора или вводится m новых переменных на доменах , где m –арность . Делаются замены:

на ,

на ,

на ,

на .

5. Выполняется построение выражения , где представляет собой , в котором проведены замещения 1-4.

Пример: перепишется .

В РИ с переменными на доменах существуют 2 теоремы:

Теорема: Для каждого безопасного выражения РИ с переменными-кортежами существует эквивалентное безопасное выражение РИ с переменными на доменах.

Теорема: Для каждого безопасного выражения с переменными на доменах существует эквивалентное ему выражение РА.

РИ есть метод определения того отношения, которое нам желательно получить (как ответ на запрос) в терминах уже имеющегося отношения.

РИ представляет собой набор правил для записи выражений, определяющих некоторое новое отношение в терминах заданной совокупности отношений.

Реляционные ямд.

Рассмотренные РА и РИ-я могут служить основой ЯМД.

Использовать РИ с переменными-кортежами как эталон для оценки ЯМД, основанный на РМ, впервые предложил Кодд. Кодд предложил язык Alpha, основанный на РИ. Этот язык является скорее абстрактным, т.к. нет систем, которые полностью бы его реализовали. DAMAS, INGRES реализовали этот язык частично. Этот язык обладает очень мощными средствами выборки:

• с упорядочиванием;

• с использованием ;

• с использованием ;

• с использованием (получить имена тех поставщиков, которые поставляют все детали; подсчет числа кортежей в отношении).

Существуют агрегатные функции count, total, max, min, average. Count – промежуточным результатом является отношение; total – список, в котором повторяющиеся значения не удаляются.

Язык Alpha является более чем полным.

Язык, в котором можно (по крайней мере) моделировать исчисление с переменными-кортежами, либо, что равносильно операциям РА, или исчисление с переменными на доменах, называется полным. Т.к. реальные языки можно реализовывать функциями не имеющими аналогов ни в РА, ни в РИ; то их называют более чем полными (реальные языки, включающие навигационные операторы и процедуры БД). Такие языки включают, естественно, команды, которые не являются частью РА или РИ. Кроме того, в них возможно:

1. Арифметические вычисления. Атомы в выражениях РИ и формулах селекции в алгебраическом выражении часто могут включать арифметические вычисления, а также сравнения ( + многие другие арифметические операции не использующиеся в РА и РИ).

2. Команды присваивания и печати.

3. Агрегатные функции. К столбцам отношения часто применяют такие операции, как среднее, сумма, min, max.

Часто говорят, что языки, основанные на РИ, представляют собой языки более высокого уровня по сравнению с алгебраическим, поскольку алгебра специфицирует порядок операций, в то время как исчисление оставляет определение наиболее эффективного порядка вычисления компилятору или интерпретатору.

Например, если имеются отношения и мы можем записать:

(1)

• напечатать значения , ассоциированные со значением , равным , в отношении со столбцами , полученным в результате соединения.

Эквивалентное выражение в исчислении с переменными на доменах:

(2)

Выражение в исчислении фактически только указывает, что мы хотим, но не описывает, как это получить.

(2) только специфицирует свойства желаемого значения.

1. специфицирует конкретный порядок операций.

Вычисление (1) требует выполнения операции соединения, что в свою очередь может вызвать необходимость сортировки обоих отношений по их значениям и просмотра отсортированных отношений. Это требует значительного времени. В зависимости от организации файлов, используемых для представления и , вычисление по формуле (3), эквивалентной (1), займет меньше времени:

(3)

Здесь сначала нужно найти в кортежи с значениями и ассоциировать с ними значения. В результате будет вычислено . Затем находим кортежи с такими значениями и печатаем ассоциированные с ними значения.

Выражение (3) может быть вычислено как по (1), так и по (2). Компилятор языка при оптимизационном просмотре может непосредственно преобразовать (1) в (3).

Языки, основанные на РИ, в настоящее время более распространены, чем на РА.

При рассмотрении языков важным является то, насколько легко в этих языках можно реализовать операции включения, выбора, проекции и естественного соединения. Такие выражения называются выражениями вида «селекция – проекция – соединение».

1. ISBL (Information System Base Language).

Используется в PRTV (Peterlee Relational Test Vehicle). Он весьма близок к РА. Соответствие операторов языка и РА:

Этот язык не содержит никаких агрегатных функций, не реализует операции включения, удаления и модификации кортежей. Но можно написать любые программы на ПЛ/1.

2. QUEL (QUEry Language) – это язык манипулирования данными системы INGRES (Interactive Graphics and Retrieval System). INGRES – полная система управления РБД, которая создана в университете шт. Калифорния и до сих пор развивается и совершенствуется.

Это язык РИ с переменными-кортежами. В языке существуют возможности удаления, добавления и модификации данных, а также агрегатные функции: сумма, среднее, счетчик, min, max.

3. QBE (Query-By-Example) – язык РИ с переменными на доменах. Разработан фирмой IBM. В этом языке так же существуют операции обновления данных (удаления, добавления, модификации), агрегатные функции (обычные).

Кроме этого в QBE предусмотрены возможности, которых нет в РА и в РИ. Его специфика заключается в том, что запрос формулируется путем заполнения табличной формы, содержащей имена отношений и его атрибутов. Табличная форма появляется на экране при нажатии специальных клавиш терминала (т.е. язык QBE предназначен для работы с терминалом). Для заполнения и модификации таблиц существует специальный экранный редактор.

4. SQL (Structured Query Language) – язык манипулирования данными, используемый в реляционных системах БД; в настоящее время принят за стандарт для БД.

Синтаксически SQL близок к исчислению кортежей. Предшественником этого языка был язык SQUARE(создан для СУБД System-R), этот язык с одной стороны отношения напоминает РА, с другой – РИ с переменными-кортежами (можно именовать кортежи в отношениях, или сравнивать множества с помощью условия ).

Операторы;

– как в РА;

;

;

не как в РА, а в стиле исчисления с переменными-кортежами , где есть , в котором замещает атрибут , или номер компонента этого атрибута в .

Оператор присваивания – <выражение>

(<выражение> – n-компонентное отношение), вычисляется выражение и присваивается результат отношению .

Основной операцией в SQL является операция отображения, представляющая собой композицию выбора и проекции. Общий вид отображения:

имя отношения;

атрибуты ;

оператор сравнения ;

.

Если опущен, то подразумеваем “=”.

Можно конструировать композиции отображений используя оператор (также строится соединение). Отображение воплощает в себе суть РА – “выбор-проекция-соединение”:

.