Тема 3.2. Реляционная алгебра. Языки запросов

3.2.1. Теоретические языки запросов.

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

В реляционных СУБД для выполнения операций над отношениями используются две группы языков, имеющие в качестве своей математической основы теоретические языки запросов:

·         реляционная алгебра;

·         реляционное исчисление.

В реляционной алгебре  операнды и результаты всех действий являются отношениями. Языки реляционной алгебры являются процедурными, так как отношение, являющееся результатом запроса к реляционной БД, вычисляются при выполнении последовательности реляционных операторов, применяемых к отношениям.

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

Для примера языков реляционной алгебры и исчислений воспользуемся БД, состоящей из трех таблиц:

·         S (поставщики);

·         P (детали);

·         SP (поставки).

S

P

SP

Первичными ключами этих таблиц являются соответственно: П# (код поставщика), Д# (код детали) и составной ключ (П#, Д#). Каждое из полей П#, Д# таблицы SP в отдельности является внешним ключом по отношению к таблице S и Р соответственно.

Имена доменов (множество допустимых значений) совпадают с именами атрибутов. исключение составляют атрибуты Город_П и Город_Д, которые имеют общий домен: множество названий городов. Имя этого домена может быть, например, просто Город. характеристики как типов данных следующие: Д# - строка символов длиной 5, Имя – строка символов длиной 20, Статус – цифровое длиной 5, Город – строка символов длиной 15, Д# - строка символов длиной 6, Тип – строка символов длиной 6, Вес – цифровое длиной 5, Количество – цифровое длиной 5.  

3.2.2. Реляционная алгебра.

Реляционная алгебра как теоретический язык запросов по сравнению с реляционным исчислением более наглядно описывает выполняемые над отношениями действий.

Примером языка запросов, основанного на реляционной алгебре, является ISBL (Information System Base Language – базовый язык информационных систем).

Реляционная алгебра, включает в себя следующие основные операции: объединение, разность, пересечение, декартово (прямое) произведение, выборка, проекция, деление, соединение.

Рис. 3.1. Основные операции реляционной алгебры

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

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

Совместимость структур отношений означает совместимость имен атрибутов и типов соответствующих доменов.

Основные правила записи выражений. Результатом реляционной операции является отношение, которое может участвовать в другой реляционной операции. Это свойство реляционной алгебры называется свойством замкнутости.

Свойство замкнутости позволяет записывать вложенные выражения реляционной алгебры, основой которых выступают элементные операции: объединение, проекция, пересечение, выборка и т.д.

При записи произвольного выражения реляционной алгебры надо принимать во внимание следующее.

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

2.      Существуют тождественные преобразования, позволяющие по-разному записывать одно и тоже выражение.

3.      Составляя выражение, нужно обеспечивать совместимость участвующих в операциях отношений. При необходимости изменения заголовков следует выполнять переименование атрибутов.

Операндами логического выражения являются условные выражения вида a > b, Город = «Москва». Значением условного выражения может быть либо 1, либо 0.

3.2.3. Реляционное исчисление

Как отмечалось ранее, принципиальное различие между реляционной ал­геброй и реляционным исчислением состоит в том, что в первом случае про­цесс получения искомого результата описывается явным образом путем ука­зания набора операций, которые надо выполнить для получения результата, а во втором — указываются свойства искомого отношения без конкретизации процедуры его получения.

Внешне подходы сильно различаются: один из них предписывающий (ре­ляционная алгебра), а другой описательный (реляционное исчисление). На более низком уровне рассмотрения подходы эквивалентны, так как любые вы­ражения реляционной алгебры могут быть преобразованы в семантически эк­вивалентные выражения реляционного исчисления и наоборот. Для такого преобразования можно использовать алгоритм редукции Кодда.

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

Пусть запрос выглядит следующим образом: «Получить номера и города поставщиков, выпускающих деталь Р2».

Словесно алгебраическая версия этого запроса описывается так:

·         образовать естественное соединение отношений S и SP по атрибуту П#;

·         выбрать из результата этого соединения кортежи с деталью Р2 (в поле Д# должна быть строка Р2);

·         спроецировать результат предыдущей операции на атрибуты П# и Город_П.

Этот же запрос в терминах реляционного исчисления можно сформулиро­вать примерно так: «Получить атрибуты П# и Город_П для таких поставщи­ков, для которых существует поставка в отношении SP с тем же значением атрибута П# и со значением Р" атрибута Д#».

Результатом выполнения запроса будет отношение R вида:

Преимуществом реляционного исчисления перед реляционной алгеброй можно считать то, что пользователю не требуется самому строить алгоритм выполнения запроса. Программа СУБД (при достаточной ее интеллектуаль­ности) сама строит эффективный алгоритм.

Отметим, что поставленную задачу выборки можно решить более опти­мально с точки зрения потребности в оперативной памяти. Более эконо­мичный вариант решения в терминах операциях реляционной алгебры вы­глядит так:

·         выбрать из отношения SP кортежи, относящиеся к детали Р2;

·         выполнить естественное соединение отношения S и отношения, полу­ченного на предыдущем шаге;

·         спроецировать текущее отношение на атрибуты П# и Город_П.

Экономия памяти при реализации этого алгоритма в сравнении с перво­начальным вариантом достигается за счет снижения размерности участвую­щих в операциях временных таблиц, необходимых для хранения промежу­точных результатов. Если в предыдущем случае размерность временной таблицы была 12*6 (12 строк на 6 колонок), то в последнем случае — 4*6.

Математической основой реляционного исчисления является исчисле­ние предикатов — один из разделов математической логики.

Существует два варианта исчислений: исчисление кортежей и исчисле­ние доменов. В первом случае для описания отношений используются пере­менные, допустимыми значениями которых являются кортежи отношения, а во втором случае — элементы домена.

Реляционное исчисление, основанное на кортежах (исчисление кортежей).

3.2.4. Язык запросов по образцу QBE.

Хранимые в базе данные можно обрабатывать в ручную, последовательно просматривая и редактируя данные в таблицах с помощью имеющихся в СУБД собственных средств. Для повышения эффективности применяют запросы, позволяющие производить множественную обработку данных, то есть одновременно вводить, редактировать и удалять множество записей, а также выбирать данные из таблиц.

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

Для подготовки запросов с помощью различных СУБД чаще всего используются два основных языка описания запросов:

·         язык QBE (Query By Example) – язык запросов по образцу;

·         SQL (Structured Query Language) – язык запросов по образцу.

По возможностям манипулирования данными при описании запросов указанные языки практически эквивалентны. Главное отличие между ними заключается в способе формирования запросов: язык QBE предполагает ручное или визуальное формирование запросов, в то время как использование SQL означает программирование запросов.

Характеристика языка QBE

Основой языка QBE является реляционное исчисление с переменными доменами. Язык QBE позволяет задавать сложные запросы к БД путем заполнения предлагаемой СУБД запросной формы. Такой способ задания запросов обеспечивает высокую наглядность и не требует указания алгоритма выполнения операции – достаточно описать образец ожидаемого результата. В каждой из современных реляционных СУБД имеется свой вариант языка QBE.

На языке QBE можно задавать запросы однотабличные и многотабличные.

С помощью запросов на языке QBE можно выполнять следующие основные операции:

·         выборку данных;

·         вычисление над данными;

·         вставку новых записей;

·         удаление записей;

·         модификацию данных.

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

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

Запросная форма имеет вид таблицы, имя и назначения полей которой совпадают с именем и названиями полей соответствующей исходной таблицы. Чтобы узнать имена доступных таблиц БД, в языке QBE предусмотрен запрос на выборку имен таблиц. Названия полей исходной таблицы могут вводиться в шаблон в ручную или автоматически. Во втором случае используется запрос на выборку заголовков столбцов.

В современных СУБД многие действия по подготовке запросов с помощью языка QBE выполняются визуально с помощью мыши, то есть «протаскиванием» мышью поля одной таблицы к полю другой.

Для иллюстрации средств и возможностей языка QBE используем таблицы БД, которая относится к торговой сфере. БД включает четыре таблицы:

Пример 1.  Запрос на выборку.

    Запрос на выборку всех зеленых товаров можно записать в следующем виде:

    Словесно запрос можно сформулировать так: «Вывести все товары ХХ, цвет которых зеленый». В приведенном шаблоне элемент примера ХХ не обязателен, его можно опустить. Пустые колонки из шаблона можно удалять.

Выборка данных

Простая выборка. Примером простой выборки является запрос: «Вывести все возможные цвета товаров из таблицы ТИПЫ ТОВАРОВ».

Простая выборка с упорядочиванием. Для упорядочивания выводимых значений по возрастанию или по убыванию используются конструкции «АО.» и «DO.» соответственно. Если требуется упорядочить по нескольким столбцам, применяют конструкцию  «АО(1)» и «АO(2)».

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

1.      Точное совпадение задается вводом констант в соответствующих полях шаблона.

2.      Частичное совпадение задается с помощью элементов примера.

3.      Условие сравнения записывается с помощью операций сравнения: = (равно); > (больше); < (меньше); <> (не равно); >= (больше или равно); <= (меньше или равно).

Пример 2.  Условия сравнения.

Запрос имени сотрудников, работающих в отделе игрушек и получающих зарплату больше 1800, выглядит так:

Результатом является таблица вида:

Пример 3.  Сравнения с элементами примера.

Запрос вида: «Найти сотрудников, получающих зарплату больше чем Х».

Операнды логического выражения соединяются знаками логических операций:

·         AND – конъюнкция (И);

·         OR – дизъюнкция (ИЛИ);

·         NOT – отрицание (НЕ);

·         XOR – дизъюнкция II (исключающее ИЛИ);

·         EQV – эквивалентность;

·         IMP – импликация.

Приоритет выполнения операций:

·         отрицание;

·         конъюнкция;

·         дизъюнкция.

В СУБД можно также осуществлять запросы с объединением условий, в таблицах, в которых существуют связи, проводить группировки запросов. Также можно осуществлять операции вставки, удаления, модификации записей.

Вернутся в содержание.

Скачано с www.znanio.ru