- Реляционные языки
- Пример языка реляционного исчисления
- Пример языка реляционного исчисления
- Алгоритм редукции Кодда
- Исчисление кортежей
- Исчисление доменов
- Языки реляционных баз данных
- 7.6 Реляционное исчисление на доменах
- 7.7 Запросы, основанные на реляционной алгебре и на исчислениях
- Языки реляционных баз данных
- 7.2 Понятие исчисления. Свойства исчислений
- Видео
Реляционные языки
На предыдущей лекции говорилось о том, что одна из частей, модели данных является управляющей, т.е. она определяет типы допустимых операций с данными, включая операции обновления и извлечения данных, а также операции изменения структуры базы данных. Для управления отношениями в реляционных СУБД используются самые разнообразные языки. Некоторые из них являются процедурными, т.е. с их помощью пользователь точно указывает системе, как следует манипулировать данными. Другие языки являются непроцедурными, т.е. пользователь указывает, какие данные ему нужны, а не как их следует извлекать.
На этой лекции основное внимание уделим реляционной алгебре, а на следующей – реляционному исчислению, которые предложены Коддом (1971) в качестве основы для создания реляционных языков. Попросту говоря, реляционную алгебру можно описать как (высокоуровневый) процедурный язык, т.е. тот, который может быть использован для того, чтобы сообщить СУБД о том, как следует построить требуемое отношение на базе одного или нескольких существующих в базе данных отношений. Реляционное исчисление, с неформальной точки зрения, представляет собой непроцедурный язык, который можно использовать для определения того, каким будет некоторое отношение, созданное на основе одного или нескольких других отношений базы данных. Однако, строго говоря, реляционная алгебра и реляционное исчисление эквивалентны друг другу, т.е. для каждого выражения алгебры существует эквивалентное выражение в реляционном исчислении (и наоборот).
Реляционное исчисление используется для оценки избирательной мощности реляционных языков. Язык называется реляционно полным, если он позволяет получить любое отношение, которое можно вывести с помощью реляционного исчисления. Большинство реляционных языков запросов является реляционно полными. Однако по сравнению с реляционной алгеброй и реляционным исчислением они обладают и другими, более широкими функциональными возможностями, поскольку в них предусмотрены дополнительные операции, способные выполнять вычислительные, обобщающие и упорядочивающие функции.
Реляционная алгебра и реляционное исчисление представляют собой формальные, а не дружественные пользователю языки. В реляционных базах данных они использовались в качестве основы для разработки других языков управления данными, более высокого уровня. Для нас они представляют интерес потому, что иллюстрируют основные операции языков манипулирования данными, а также служат определенным критерием сравнения других реляционных языков.
Несмотря на то что реляционное исчисление является достаточно сложным с точки зрения освоения и использования, тем не менее его непроцедурная природа считается весьма перспективной и это стимулирует поиск других, более простых в употреблении непроцедурных методов. Подобные исследования вызвали появление двух других категорий реляционных языков: языков на основе преобразований и графических языков.
Языки на основе преобразований являются классом непроцедурных языков, которые используют отношения для преобразования исходных данных к требуемому виду. Эти языки предоставляют простые в употреблении структуры для формулирования требуемого результата имеющимися средствами. Примерами языков на основе преобразований являются язык SQUARE, язык SEQUEL и его ответвление — язык SQL. Ранее мы с вами знакомились с некоторыми операторами языка SQL. В дальнейшем мы будем использовать именно этот язык и изучим его дополнительные возможности.
Графические языки предоставляют пользователю рисунок или другое графическое отображение структуры отношения. Пользователь создает некий образец желаемого результата, и система возвращает затребованные данные в указанном формате. Примером подобного языка является язык QBE (Query-By-Example). Он используется, например в MS Access или MS Visual Foxpro.
Еще одной категорией языков являются языки четвертого поколения (fourth-generation languages — 4GL), которые позволяют создавать полностью готовое и соответствующее требованиям заказчика прикладное приложение с помощью ограниченного набора команд и в то же время предоставляют дружественную по отношению к пользователю среду разработки, чаще всего построенную на использовании команд меню В некоторых системах используются даже некоторые разновидности естественного языка, т.е. ограниченной версии обычного английского языка, который иногда называется языком пятого поколения (fifth-generation language — 5GL). Однако разработки проектов подобных языков по большей части все еще находятся в зачаточном состоянии.
Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет
Пример языка реляционного исчисления
Предположим, что мы работаем с базой данных, обладающей схемой СОТРУДНИКИ (СОТР_НОМ, СОТР_ИМЯ, СОТР_ЗАРП, ОТД_НОМ) и ОТДЕЛЫ (ОТД_НОМ, ОТД_КОЛ, ОТД_НАЧ), и хотим узнать имена и номера сотрудников, являющихся начальниками отделов с количеством сотрудников больше 50.
Мы четко сформулировали последовательность шагов выполнения запроса, каждый из которых соответствует одной реляционной операции. Если же сформулировать тот же запрос с использованием реляционного исчисления, которому посвящается этот раздел, то мы получили бы формулу, которую можно было бы прочитать, например, следующим образом: Выдать СОТР_ИМЯ и СОТР_НОМ для сотрудников таких, что существует отдел с таким же значением ОТД_НАЧ и значением ОТД_КОЛ большим 50.
5.2.1. Кортежные переменные и правильно построенные формулы
Реляционное исчисление является прикладной ветвью формального механизма исчисления предикатов первого порядка. Базисными понятиями исчисления являются понятие переменной с определенной для нее областью допустимых значений и понятие правильно построенной формулы, опирающейся на переменные, предикаты и кванторы.
В зависимости от того, что является областью определения переменной, различаются исчисление кортежей и исчисление доменов. В исчислении кортежей областями определения переменных являются отношения базы данных, т.е. допустимым значением каждой переменной является кортеж некоторого отношения. В исчислении доменов областями определения переменных являются домены, на которых определены атрибуты отношений базы данных, т.е. допустимым значением каждой переменной является значение некоторого домена. Мы рассмотрим более подробно исчисление кортежей, а в конце лекции коротко опишем особенности исчисления доменов.
В отличие от раздела, посвященного реляционной алгебре, в этом разделе нам не удастся избежать использования некоторого конкретного синтаксиса, который мы, тем не менее, формально определять не будем. Необходимые синтаксические конструкции будут вводиться по мере необходимости. В совокупности, используемый синтаксис близок, но не полностью совпадает с синтаксисом языка баз данных QUEL, который долгое время являлся основным языком СУБД Ingres.
Для определения кортежной переменной используется оператор RANGE. Например, для того, чтобы определить переменную СОТРУДНИК, областью определения которой является отношение СОТРУДНИКИ, нужно употребить конструкцию
Как мы уже говорили, из этого определения следует, что в любой момент времени переменная СОТРУДНИК представляет некоторый кортеж отношения СОТРУДНИКИ. При использовании кортежных переменных в формулах можно ссылаться на значение атрибута переменной (это аналогично тому, как, например, при программировании на языке Си можно сослаться на значение поля структурной переменной). Например, для того, чтобы сослаться на значение атрибута СОТР_ИМЯ переменной СОТРУДНИК, нужно употребить конструкцию СОТРУДНИК.СОТР_ИМЯ.
На самом деле, правильнее говорить не о свободных и связанных переменных, а о свободных и связанных вхождениях переменных. Легко видеть, что если переменная var является связанной в WFF form, то во всех WFF, включающих данную, может использоваться имя переменной var, которая может быть свободной или связанной, но в любом случае не имеет никакого отношения к вхождению переменной var в WFF form. Вот пример:
Здесь мы имеем два связанных вхождения переменной СОТР2 с совершенно разным смыслом.
5.2.2. Целевые списки и выражения реляционного исчисления
Итак, WFF обеспечивают средства формулировки условия выборки из отношений БД. Чтобы можно было использовать исчисление для реальной работы с БД, требуется еще один компонент, который определяет набор и имена столбцов результирующего отношения. Этот компонент называется целевым списком (target_list).
Последний вариант требуется в тех случаях, когда в WFF используются несколько свободных переменных с одинаковой областью определения.
5.2.3. Реляционное исчисление доменов
Во всех остальных отношениях формулы и выражения исчисления доменов выглядят похожими на формулы и выражения исчисления кортежей. В частности, конечно, различаются свободные и связанные вхождения доменных переменных.
Для примера сформулируем с использованием исчисления доменов запрос «Выдать номера и имена сотрудников, не получающих минимальную заработную плату» (будем считать для простоты, что мы определили доменные переменные, имена которых совпадают с именами атрибутов отношения СОТРУДНИКИ, а в случае, когда требуется несколько доменных переменных, определенных на одном домене, мы будем добавлять в конце имени цифры):
Реляционное исчисление доменов является основой большинства языков запросов, основанных на использовании форм. В частности, на этом исчислении базировался известный язык Query-by-Example, который был первым (и наиболее интересным) языком в семействе языков, основанных на табличных формах.
Пример языка реляционного исчисления
Вы будете перенаправлены на Автор24
Принципиальным различием между реляционной алгеброй и реляционным исчислением является то, что в реляционной алгебре получение искомого результата описывается явным образом с помощью указания набора операций, которые необходимо выполнить для получения результата, а в реляционном исчислении указывают свойства искомого отношения без указания процедуры его получения.
Алгоритм редукции Кодда
Рассмотрим возможность формулировки одного и того же запроса языком реляционной алгебры и реляционного исчисления.
Рассмотрим запрос: «Получить города и номера поставщиков, которые выпускают деталь D2».
Словесно языком реляционной алгебры запрос может быть описан следующим образом:
С помощью реляционного исчисления данный запрос может быть сформулирован следующим образом:
«Получить атрибуты Поставщик# и Город_Поставщик для тех поставщиков, которые имеют поставку в отношении PD с таким же значением атрибута Поставщик# и со значением D» атрибута Деталь#».
Отношение R будет результатом выполнения данного запроса:
Преимущество реляционного исчисления перед реляционной алгеброй состоит в том, что пользователь не должен сам строить алгоритм выполнения запроса. Эффективный алгоритм строится программой СУБД.
Исчисление предикатов, раздел математической логики, является математической основой реляционного исчисления.
Впервые понятие реляционного исчисления для работы с базами данных предложил Кодд. Он разработал язык ALPHA, который стал прототипом программно реализованного языка QUEL, который одно время конкурировал с языком SQL.
Исчисления существуют в двух вариантах:
Исчисление кортежей
Реляционное исчисление кортежей было реализовано при разработке языка ALPHA. Как и в процедурных языках программирования, в нем сначала необходимо выполнить описание используемых переменных, а после записать выражения.
Описывается исчисление следующим образом:
где RANGE, OF, IS – ключевые слова языка,
Например, запись RANGE OF A IS A1, A2 значит, что область определения переменной А содержит все значения из отношения, являющегося объединением отношений А1 и А2.
Исчисление доменов
Реляционное исчисление, основанное на доменах, было предложено Лакроиксом и Пиротте, которыми также был разработан на его основе язык ILL.
Среди языков, основанных на исчислении доменов, можно выделить QBE с некоторыми оговорками, DEDUCE и FQL.
Дейт утверждал, что язык QBE содержит элементы исчисления кортежей и доменов, но является более близким к исчислению доменов. Языком не поддерживается операция отрицания квантора существования (NOT EXISTS), поэтому его нельзя назвать реляционно полным. Тем не менее, язык QBE достаточно широко распространен в современных СУБД.
Исчисление доменов сходно с исчислением кортежей. Основой любого выражения запроса в исчислении доменов являются переменные доменов.
Переменной домена является скалярная переменная, которая в качестве значений содержит элементы какого-нибудь домена.
Основное различие исчисления кортежей и исчисления доменов состоит в том, что исчислением доменов поддерживается дополнительная форма условия, которая называется условием принадлежности.
Общий вид условия принадлежности:
$R(A1:vartheta_1, A2: vartheta_2, cdots)$,
Например, выражение PD (Поставщик# : ‘P1’, Деталь# : ‘D1’) будет истинным в случае, когда в отношении PD существует хотя бы один кортеж, который содержит значение ‘P1’ атрибута Поставщик# и значением ‘D1’ атрибута Деталь#.
Языки реляционных баз данных
7.6 Реляционное исчисление на доменах
В реляционном исчислении на доменах (Domain Relational Calculus — DRC) область определения переменных не кортежи отношения, а набор доменов.
Отношение состоит из кортежей, в которые входят значения, принадлежащие доменам. Поэтому необходимо как-то показывать, что некоторые значения на доменах входят в один кортеж. С этой целью в исчисление на доменах, в отличие от исчисления на кортежах, вводится дополнительный набор предикатов, выражающих условия принадлежности (доменов кортежу).
Пусть 
—это 
-арное отношение с атрибутами 
. Тогда условие принадлежности можно записать так: 
, где 
— это либо константа, либо имя доменной переменной.
Условие принадлежности истинно тогда и только тогда, когда в отношении г существует кортеж, содержащий заданные значения указанных 
-тых атрибутов кортежа , то есть 
.
Если — константа, то условие на атрибут
. зависит от текущих значений доменных переменных; если же — имя доменной переменной, то условие принадлежности может принимать разные значения истинности при разных значениях этой переменной.
Во всех остальных отношениях правильно построенные формулы и выражения исчисления доменов и исчисления кортежей аналогичны. В частности, формулы могут включать кванторы. Различаются свободные и связанные вхождения доменных переменных.
Сравните форму записи запроса в исчислении на доменах 
и аналогичную форму для исчисления на кортежах 
.
7.6.1 Синтаксис запросов DRC в WinRDBI
Запрос имеет вид: , где 
— формула исчисления, а 
— доменные переменные, действующие как глобальные переменные в и определяющие схему результата.
Результатом запроса DRC будет множество всех образованных кортежей
, для которых формула истинна.
Обозначим: 
— переменная-домен, 
— константа уровня домена, 
— оператор сравнения. Тогда атомами будут: 
.
Пусть 
— формулы. Тогда формулами будут: 
. Если 
свободна (свободная переменная не квантифицирована действием 
или 
) в 
, формулами будут 
, 
.
7.6.2 Реляционная полнота реляционного исчисления на доменах
Как в исчислении на кортежах, для доказательства достаточно выразить операции реляционной алгебры через операции исчисления. Обозначим условия принадлежности через 
. Сведем представления в таблицу 7.3.
| Реляционная алгебра | Реляционное исчисление на доменах |
 |  |
 |  |
 |  |
 |  |
 |  |
7.6.3 Примеры запросов в исчислении на доменах
Войдите в WinRDBI, откройте базу empTraining.rdb и файл empTrain-ing.drc с набором запросов в исчислении на доменах. Форма записи запроса в исчислении на доменах
похожа на аналогичную форму для исчисления на кортежах
,
но формула исчисления на доменах обязательно содержит условие приадлежности домена кортежу. Пример запроса:
Переменные EID, ELast, EFirst, ETitle, ESalary доменные, а employee(EID, ELast, EFirst, ETitle, ESalary) — условие связи.
Сравните его с эквивалентным запросом в исчислении на кортежах (рисунок 7.3)
7.7 Запросы, основанные на реляционной алгебре и на исчислениях
Основное отличие языков, основанных на реляционной алгебре и на исчислениях, состоит в уровне процедурности. Запросы, основанные на реляционной алгебре, задают дерево алгебраических операций, то есть имеют однозначную процедурную интерпретацию (с учетом старшинства операций и расстановки скобок). Запрос реляционного исчисления не имеет однозначной процедурной интерпретации. Он только устанавливает условия, которым должны удовлетворять кортежи результирующего отношения. Поэтому языки реляционного исчисления являются менее процедурными и, соответственно, более декларативными.
Любой реляционно-полный язык позволяет не только моделировать язык запросов реляционной алгебры, но и языки запросов реляционных исчислений на кортежах или на доменах. То есть языки исчислений могут быть шире, но минимальный уровень моделируется реляционно-полным языком.
Языки реляционных баз данных
7.2 Понятие исчисления. Свойства исчислений
В соответствии с общими понятиями семиотики будем выделять синтаксис (способ записи чего-либо), семантику (смыслы) и прагматику (способы употребления). Эта трехчастная конструкция называется треугольником Фреге. Заметим, что насыщение баз данных смыслами мало изучено, но может представлять большой интерес как для практики, так и для обучения.
Займемся исчислениями. Изложение по недостатку места и времени будет неполным и поверхностным, но достаточным для практического освоения исчислений на кортежах и доменах.
7.2.1 Логические исчисления
Дедуктивной называют систему, в которой работает дедуктивный вывод.
Исчисление высказываний изучает логические связи между высказываниями, рассматриваемыми как единое целое, без учета их строения. Значений истинности два. Третье значение истинности «полуистинно-полуложно» (или значение «не знаю»), связанное с NULL, здесь не используется.
Исчисление предикатов формализует логику, изучающую субъектно-предикатную структуру высказываний. Предполагается, что в высказывании есть некоторые переменные, и потому истинность предиката может быть разной в зависимости от того, как вы означите эти переменные.
7.2.2 Алгебра множеств и логика
Когда вы будете пытаться понять разницу в эффективности языков, основанных на исчислениях и на реляционной алгебре, обратите внимание на то, что в школьной математике принято допускать одну неточность. Операции над множествами и логические операции там часто иллюстрируют на примере линейно упорядоченных множеств. То есть работают с интервальными, а не произвольными множествами. Потому операции над множествами и эквивалентные операции над соответствующими предикатами, по сути, совпадают, точнее, находятся во взаимно-однозначном соответствии.
Отношения — это неупорядоченные множества кортежей, и потому вычисление предикатов может быть существенно эффективнее действий над множествами кортежей. В алгебре результат каждой операции — это промежуточное отношение, которое в реализациях языка должно быть создано. При этом работают со всеми кортежами, а не только с граничными элементами, как в интервальных множествах. В простых запросах в исчислениях могут проверяться сложные условия, выраженные предикатами, и строиться единственное результирующее отношение.
7.2.3 Предикаты
Исчисление высказываний не позволяет оперировать обобщенными утверждениями, содержащими переменные. Этот недостаток устраняется использованием предикатов.
Определение. Предикат 
—это утверждение 
об объектах 
.
Сами объекты могут рассматриваться как переменные, означивая которые мы получаем из предиката высказывания с разными значениями истинности. Можно понимать предикат как функцию в множество значений истинности 
. Примеры:
Здесь «погода» — предикатный символ (предикат); 
и 
— переменные; «вторник», «дождь» — константы.
Одноместные предикаты обозначают свойства (например, «быть человеком»), предикаты двухместные и с большей арностью обозначают отношения и операции. Пример: двухместный предикат «выше, чем».
Особый интерес представляют предикаты, значение истинности которых определяется на некотором наборе переменных. Высказывания о множествах объектов строятся с помощью кванторов.
Кванторы
Реже употребляется: сильный квантор существования 
— «существует единственный». Примеры:
Переменная, на которую навешен квантор, называется связанной. Например, в формулах 
и 
переменная 
связана, а 
свободна.
7.2.4 Понятие исчисления
Важно понимать, что исчисление или формальная теория —это система правил оперирования со знаками, используемая для доказательства или опровержения предложений, выразимых с помощью допустимого набора знаков. Исчисления работают с так называемыми правильно построенными формулами (ППФ). Аксиомы — это набор ППФ, принятых за исходные. В самом исчислении нет представления об истинности аксиом.
Кроме знаков ничего нет — никаких смыслов. Но исчисление может быть интерпретировано. И вот тогда появляется семантика.
Исчисление состоит из:
Выделяют логические аксиомы, определяющие базовую логику. Специфика теории может потребовать добавления нелогических аксиом.
Мы будем рассматривать исчисления с конечным алфавитом, конечным числом аксиом и формулами конечной длины.
Правила вывода
Используются, в частности, следующие правила вывода:
Формальное доказательство формулы 
в исчислении — это построение конечной последовательности формул 
, причем, 
. Каждая из формул этой цепочки либо аксиома, либо получена из других формул с помощью правил вывода. называется теоремой. С помощью символа «доказуемо» 
запишем этот факт как 
.
Свойства исчисления
Определяющими свойствами любого исчисления являются полнота и непротиворечивость.
Определение (Полнота). Формальная теория называется полной, если для любого высказывания А логики предикатов или 
или 
Определение (Непротиворечивость). Формальная теория называется непротиворечивой, если формула 
в ней недоказуема для произвольного высказывания А теории.
Замечание. Как показал К. Гедель в своей знаменитой теореме о неполноте арифметической логики, доказательство непротиворечивости невозможно выполнить даже в рамках формальных теорий для простых математических объектов.
7.2.5 Языки запросов, основанные на логических исчислениях
Реляционная алгебра определяет набор операций, комбинируя которые, можно создать отношение, которое представляет ответ на запрос.
Знания только реляционной алгебры даже для практики недостаточно, потому что два наиболее известных языка для работы с реляционными базами данных — SQL (Structured Query Language) и QBE (Query-by-Example) — основаны, соответственно, на реляционных исчислениях на кортежах и доменах.
В настоящее время языками, основанными на реляционной алгебре, не пользуются. Так зачем же мы ее изучаем? По двум причинам:
Определение. Язык запросов к базе данных, способный моделировать реляционную алгебру, обладает свойством реляционной полноты. Используемые в практике языки сверхполны, то есть кроме реляционных запросов, они позволяют делать много чего еще. Понятно, что реляционно-неполные языки интереса не представляют.
Удобство исчислений в том, что в запросах формируются условия, которым должен удовлетворять результат запроса. По ним и отбираются строки. В запросах реляционной алгебры при выполнении каждой операции последовательно получаются промежуточные отношения. Это замедляет получение ответа.
