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

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

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 является операция отображения, представляющая собой композицию выбора и проекции. Общий вид отображения:

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

атрибуты ;

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

.

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

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

.

 

Язык запросов в SQL.

1. Отображение:

Select A₁…A_n

from R

Where B₁θ₁b₁Ù…ÙB_mθ_mb_m

Выражение, следующее за where, может содержать атрибуты отношения, арифметические операции сравнения, булевские связки and, not, or, может содержать операции над множествами (union – , intersect – ∩, minus – /), операции принадлежности множеству (X in R, R contain X, R does not contain X, X not in S). Во всех этих операциях X – элемент множества, или кортеж, или множество.

1) Выражение, следующее за where может содержать операнды, которые представляют собой отношения, сформированные другим предложением select _ from _ where.

2) SQL может оперировать не только одним отношением в предложении from. На значение атрибута любого из отношений, указанных в предложении from, может ссылаться как в select, так и в where. Если А является атрибутом более одного отношения, то пишут R.А, указывая тем самым, что имеется в виду атрибут А из отношения R.

При наличии в запросе предложения from R₁,…,R_n будут рассматриваться все списки t₁,…,t_n кортежей, где t_iÎR_i. Если данный список удовлетворяет условиям, указанным в предложении where, в результат оператора включается список компонентов, специфицированных в предложении select.

Операторы включения, удаления, модификации в SQL являются синтаксически улучшенной версией соответствующих операторов SQUARE.

2. Операция обновления:

Update имя_БД

Set <выражение1>

Where < выражение2 >

– обновление одной таблицы.

3. Операция удаления:

Delete имя_БД

Where

В – удаляет записи БД, удовлетворяющие условию.

Delete имя_БД – таблица есть, но она пустая.

Все операции SQL сами открывают БД.

4. Дополнение БД.

Дополняемая БД может быть не открыта, а после дополнения она остается открытой и активной.

1) Insert into <имя_БД> [(<поле1> [,<поле2> [,…]])]

Values (<выражение1> [,<выражение2> [,…]])

Добавляем записи в конец существующей БД; значение <вырi> записывается в <полеi>; если <полеi> опущено, то значение <вырi> записывается в поля в соответствии со структурой.

3) Insert into <имя_БД> from array {из мн-ва}

<массив> from memvar {из врем. пер-х}

Временные переменные должны существовать и иметь имена полей = имени поля БД, но первая буква M. Такие переменные вырабатываются по команде Scatter memvar.

5. Операция создания БД:

Create dbf <имя dbf -файла>

(<имя поля> <тип> [(<размер>[,<дробный р-р>]

[,<имя поля>]]) / From array <массив>

¯

массив из 4-х столбцов и строк = числу полей

Тип: C,N,D,M,F,L.

fix пл. точк.

Массив, соответствующий описанию полей, создается функцией Afields () (при открытой БД).

ЗАЩИТА БАЗ ДАННЫХ.

Защита данных в БнД – это решение двух проблем:

1) ограничение целостности данных;

2) секретность данных.

Проблема целостности данных заключается в обеспечении соответствия данных, хранящихся в БД, реальному текущему состоянию ПО. Логические ограничения, накладываемые на данные, называются ограничениями целостности. Ограничение целостности – это свойство, которое для данного множества или отношения либо истинно, либо ложно. Это значение должно сохраняться для каждого возможного значения, в котором находится объект. Существует 3 основных вида ограничений целостности:

1. Внутренние (структурные) – те ограничения, которые лежат в основе структуры БД. Например, РМД присуще внутреннее ограничение, что сущности и связи между сущностями представлены в виде отношений (таблиц).

2. Явные (семантические) ограничения целостности или утверждения.

3. Ограничения, вводимые на основе внутренних и явных. Это подразумеваемые.

Семантические ограничения делятся на 2 вида:

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

2) Показывает связь между атрибутами одного отношения. Записывается в виде функциональной зависимости.

 

Функциональные зависимости.

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

Пусть – схема отношения, а – подмножества (множество атрибутов). Говорят, что X функционально определяет Y (Y функционально зависит от X), и обозначается , если в любом отношении R не существует 2-х кортежей, компоненты которых совпадают по всем атрибутам, принадлежащим , но не совпадают по одному или более атрибутам, принадлежащим Y.

Функциональные зависимости возникают различными способами:

1) Если, например, является ключом, то .

2) – есть отображение набора объектов к набору . Среди есть атрибуты, образующие ключ для , и ключ для , то справедливо .

3) и для .

Если заданы функциональные зависимости, то СУБД будет:

а) поддерживать ограничения целостности;

б) более эффективно будет реализовываться отношение, однако при этом будет невозможно хранение некоторой информации. Например, Имя Телефон; то не может быть 2-х телефонов для одного человека.

В связи с введением функциональной зависимости можно дать другое определение ключа:

Если – схема отношения с атрибутами и множество функциональных зависимостей , а подмножество , то X называется ключом отношения R, если

1) , где – замыкание множества функциональных зависимостей;

2) Ни для какого собственного подмножества . F⁺ – все функциональные зависимости, которые могут быть получены для данного отношения с использованием правил вывода.

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

1˚. аксиома рефлексивности: Это правило дает тривиальные зависимости, т.е. зависимости, правая часть которых содержится в левой части. Его использование не зависит от .

2˚. аксиома пополнения:

3˚. аксиома транзитивности:

Пример: R (индекс, город, адрес)

F: индекс → город

город, адрес → индекс

F⁺: индекс, адрес → город, адрес

город, адрес → индекс, город, адрес

индекс, адрес → индекс, город, адрес

Рассмотренные аксиомы являются надежными, т.е. приводят к истинным заключениям. Другие правила вывода, которые являются следствием из 1˚-3˚:

4˚. правило объединения:

5˚. правило декомпозиции: (вытекает из 1˚, 3˚).

6˚. правило псевдотранзитивности:

Правило объединения и декомпозиции порождают важное следствие:

Если – атрибуты, то зависимость справедлива т. и т.т., когда .

Не существует алгоритма для нахождения множества функциональной зависимости.