Общая характеристика языков манипулирования данными

Эквивалентность выражений реляционного исчисления с переменными-кортежами и исчисления с переменными на доменах

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

Выражение реляционного исчисления с переменными на доменах строится с использованием тех же средств, что и выражение реляционного исчисления с переменными-кортежами. Отличие состоит в том, что здесь областью определения являются домены.

Здесь также строится правильно определенная формула, основой которой являются атомы.

I. Атомы имеют следующий вид:

a) r(x₁x₂…x_n), где r – отношение, удовлетворяющее схеме R(A₁A₂…A_n) и каждое x_i есть константа или переменная на домене;

b) u q v, где u и v – константы или переменные на домене, q – арифметическая операция сравнения (<, =, >, ³, ¹, £);

II. Формула реляционного исчисления y(t), а также свободные и связанные вхождения переменных определяются так же, как и для исчисления с переменными-кортежами.

Выражение исчисления с переменными на доменах, эквивалентное выражению исчисления с переменными-кортежами {t | y(t)}, конструируется в соответствии со следующими правилами.

Пусть е6сть переменная-кортеж t(R), где R = (A₁A₂…A_n) имеет арность n. Тогда вместо переменной-кортежа t вводятся n новых переменных на доменах t₁, t₂, …, t_n и заданное выражение исчисления с переменными-кортежами заменяется выражением {t₁, t₂, …, t_n | j΄(t₁, t₂, …, t_n)}. Здесь j΄ представляет собой j, в которой:

Любой атом r(t) заменяется атомом r(t₁, t₂, …, t_n);

Каждое свободное вхождение t[A_i] заменено переменной t_i;

Для каждого квантора $u или "u вводится m новых переменных u₁, u₂, …, u_m, где m – арность u. Кванторы $u (или "(u)) заменяются кванторами $u₁ $u₂ … $u_m ("u₁ "u₂ … "u_m, соответственно), и в подчиненных кванторам выражениях u[A_i] заменяются на u_i и r(u) на r(u₁, u₂, …, u_m).

Теорема

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

Пример:

Даны отношения со схемами S(S#, SNAME, CITY) – поставщик,

P(P#, PNAME, PRICE) – деталь,

SP(S#, P#, QTY) – поставка.

Написать выражение реляционного исчисления, позволяющее получить имена поставщиков, поставляющих деталь с номером P2.

a) Выражение исчисления с переменными-кортежами:

{t(SNAME) | $u(S) $v(SP) (S(u) Ù SP(v) Ù u[SNAME] = t[SNAME] Ù u[S#] = v[S#] Ù v[P#] = “P2”)}

b) Выражение исчисления с переменными на доменах:

{t(SNAME) | $u₁(S#) $u₂(SNAME) $u₃(CITY) $v₁(S#) $v₂(P#) $v₃(QTY) (S(u₁,u₂,u₃) Ù SP(v₁,v₂,v₃) Ù u₂ = t Ù u₁ = v₁ Ù v₂ = “P2”)}

Кодд предложил использовать реляционное исчисление с переменными-кортежами как эталон для оценки языков манипулирования данными, основанных на реляционной модели. Дело обстоит так, что едва ли не во все современные языки запросов встраивается одна из трех рассмотренных выше нотаций, а в некоторые языки – их комбинация.

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

Однако в реальных системах языки манипулирования данными обладают в общем случае возможностями, выходящими за рамки реляционного исчисления. Во всех языках манипулирования данными, конечно же, включаются команды вставки, удаления и модификации, которые не являются частью реляционной алгебры или реляционного исчисления. Кроме того, часто предоставляются возможности использовать в записи атомов арифметические операции и использовать агрегатные функции.

Далее приводится краткий обзор языков манипулирования данными, основанных на реляционной модели.

ISBL (Information System Base Language) – «чистый» язык реляционной алгебры. Язык запросов, разработанный в исследовательском центре фирмы IBM в Питерли (Англия) для использования в экспериментальной системе PRTV (Peterlee Relational Test Vehicle); весьма близок к реляционной алгебре. В данном языке нет агрегатных операций, а также средств для вставки, удаления и модификации кортежей.

SEQUEL (Structured English Query Language) – переход от алгебраических языков к языкам исчислений. Использует реляционную алгебру, но имеет синтаксис, напоминающий реляционное исчисление с переменными-кортежами. SEQUEL разработан в 1974 г. (первая публикация) в исследовательской лаборатории IBM в Сан-Хосе. Центральная возможность языка – отображение: специальный вид селекции с последующей проекцией.

В 1976 г. на базе переработанной версии языка SEQUEL/2 корпорация IBM выпустила прототип СУБД, получивший название System R. Назначение этой пробной версии состояло в проверке осуществимости реляционной модели. Помимо прочего, важнейшим из результатов выполнения этого проекта можно считать разработку собственного языка SQL (Structured Query Language).

QUEL – язык реляционного исчисления с переменными-кортежами. Язык запросов реляционной СУБД INGRES, разработанной в Калифорнийском университете в Беркли в конце 70-х г.г. Включает широкий спектр операторов реляционного исчисления с переменными-кортежами. Включает агрегатные функции. Этот язык является более структурированным, чем SQL, но его семантика менее близка к обычному английскому языку (позднее, когда язык SQL был принят как стандартный язык реляционных БД, СУБД INGRES была переведена на использование этого языка).

QBE (Query-By-Example) – язык исчисления с переменными на доменах. Язык разработан в Исследовательском центре IBM в Йорктаун-Хейтсе. Его специфика заключается в том, что он предназначен для работы с терминала. Клавиши терминала позволяют затребовать показ на экране одной или более форм таблиц. Необходимые запросы формулируются с использованием переменных на доменах и констант, как в реляционном исчислении с переменными на доменах. Включены агрегатные функции.

SQL (Structured Query Language) – язык, ориентированный на отображение: описывается отображение известного атрибута или множества атрибутов в искомый атрибут или множество атрибутов. В языке для указания роли имен отношений и атрибутов применяются ключевые слова. Первой из коммерческих реализаций СУБД, построенных на использовании языка SQL, была СУБД ORACLE, выпущенная в конце 70-х г.г. компанией, которая ныне превратилась в корпорацию ORACLE.

В 1982 г. Американский национальный институт стандартов (ANSI) начал работу над стандартом языка реляционных БД. В 1983 г. к этой работе подключился Международный комитет по стандартизации (ISO). Совместными усилиями в 1987 г. был выпущен первый стандарт языка SQL. В 1992 г. была выпущена первая, существенно пересмотренная версия стандарта ISO, которую иногда называют SQL2 или SQL-92.

Язык SQL имеет два основных компонента:

- язык DDL (Data Definition Language), предназначенный для определения структур базы данных;

- язык DML (Data Manipulation Language), предназначенный для выборки и обновления данных.

Язык SQL является примером языка с трансформирующей ориентацией – языка, предназначенного для работы с таблицами с целью преобразования входных данных к требуемому виду. Это не процедурный язык, поэтому в нем необходимо указывать, какая информация должна быть получена, а не как ее можно получить. Иначе говоря, язык SQL не требует указания методов доступа к данным.