Реляционное исчисление с переменными-кортежами.

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

Выражение в РИ строятся из атомов. Атомы могут быть трех типов:

1. , где – имя отношения, а – переменная-кортеж. Этот атом означает, что есть кортеж отношения .

2. , где и – переменные-кортежи, – арифметический оператор сравнения; – номера столбцов кортежей и соответственно. Этот атом означает, что -й компонент находится в отношении с -й компонентой .

3. tⁱ θС, Сθtⁱ , где и – то же, что в 2); С = . Этот атом означает, что -й компонент кортежа находится в отношении с константой С.

Переменная называется связанной, если этой переменной в формуле предшествует квантор или . В противном случае переменная называется свободной.

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

1. Каждый атом является выражением.

2. Если φ₁ и φ₂ – выражения РИ, то φ₁ φ₂, φ₁ φ₂, ¬φ_i – также выражения РИ. В результирующем выражении переменные будут свободными или связанными так же, как они были свободными или связанными в выражениях φ₁ и φ₂.

3. Если φ – формула, то – формула, которая утверждает, что существуют значения , при подстановке которых вместо всех свободных вхождений переменной в формулу , эта формула становится истинной. Переменная становится связанной, остальные свободны или связанны в зависимости от того, свободны они или связанны в формуле .

4. Если φ – формула, то – формула. Эта формула утверждает, что какое бы значение подходящей арности мы не подставляли вместо свободных вхождений в , формула является истинной.

5. _{Приоритет операций: + скобки}

6. Ничто другое не является формулой.

Таким образом, формула в РИ с переменными-кортежами есть выражение вида , где – единственная свободная переменная-кортеж. А само исчисление кортежей определяется так же, как РИ только с другим О.

Пример:

Билет 20. Безопасные выражения РИ.

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

D(φ) - множество символов, которые явно появляются в выражении φ, либо являются компонентами какого-либо кортежа отношения , упомянутого в φ. Множество является функцией отношений, которые должны подставляться вместо переменных отношения в . Т.к. – все отношения предполагаются конечными, то и множество конечно.

R_j имеет n_j компонент, – множество констант.

Выражение реляционного исчисления с переменными-кортежами называется безопасным, если выполняются условия:

1. Всякий раз, когда кортеж t удовлетворяет выражению φ, каждая компонента кортежа t принадлежит множеству D(φ).

2. Для любого подвыражения вида , входящего в выражение , каждый компонент , если t удовлетворяет .

3. Если для любого подвыражения вида , входящего в выражение , каждый компонент , то t будет удовлетворять выражению .

На основании приведенных условий можно утверждать, что если – формула, в которой любая подформула вида или безопасна, то безопасно выражение вида (*), т.к. любой кортеж , удовлетворяющий этой формуле, принадлежит . Следовательно, любая компонента выражения (*).

Если φ состоит из подвыражений φ₁ и φ₂, связанных связками , и каждое φ_i может быть определено правилами 1-3, то безопасность выражения φ определяется безопасностью выражений φ₁ и φ₂.

Безопасные выражения РИ с переменными-кортежами эквивалентны РА.

Теорема: Если существует выражение РА, то существует эквивалентное ему безопасное выражение в РИ с переменными-кортежами.

Пример безопасного выражения:

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

(*),

т.к. любое , удовлетворяющее (*), принадлежит , в силу чего каждый из его компонентов принадлежит . Например, такой вид имеет формула разности множеств: при .

Обобщения: безопасным является выражение:

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

Билет 21. РИ с переменными на доменах. Безопасные выражения.

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

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

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

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

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

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

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

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

Выражение РИ с переменными на доменах имеет вид: , (*), где формула такая, что ее свободные переменные на доменах являются различными переменными .

Пример:

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

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

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

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

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

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

Билет 22. Эквивалентность выражений РА, выражений РИ с переменными-кортежами и выражений РИ с переменными на доменах.

Выражения исчисления с переменными на доменах эквивалентны выражениям исчисления с переменными-кортежами.

Алгоритм перевода выр. исч. с переменными-кортежами в выр. исч. с переменными на доменах:

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

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

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

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

на , на , на , на .

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

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

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

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

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

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

Билет 23. Реляционные языки манипулирования данными. Полный и более чем полные языки манипулирования данными. Примеры языков манипулирования данными.

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

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

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

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

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

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

1. ISBL (Information System Base Language). Основан на РА. Не включает агрегатные функции; отсутствуют операторы обновления, удаления, вставки; зато есть возможность расширения засчет языка PL /1

2. QUEL (QUEry Language) – это язык РИ с переменными-кортежами. В языке существуют возможности удаления, добавления и модификации данных, а также агрегатные функции: сумма, среднее, счетчик, min, max – более чем полный.

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

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

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

Синтаксически SQL близок к исчислению кортежей.

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

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

атрибуты ;

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

.

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

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

.

Билет 24. Целостность баз данных (БД). Основные виды ограничений целостности.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3. и для .

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

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

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

Билет 26. ключа схемы отношений. Правила вывода функциональных зависимостей (ФЗ).

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Билет 25. Покрытие множества зависимостей.

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

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

Теорема: Каждое множество функциональных зависимостей F эквивалентно некоторому минимальному множеству .

Говорят, что множество функциональных зависимостей F минимально, если:

1. правая часть каждой зависимости в F состоит только из одного атрибута;

2. ни для какой зависимости в F множество не эквивалентно F;

3. ни для какой функциональной зависимости в F и собственного подмножества , множества и F не эквивалентны.

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

Замыкание множества атрибутов относительно множества функциональных зависимостей. Пусть F – множество функциональных зависимостей на множестве , и пусть , тогда (замыкание X относительно F) есть множество атрибутов А таких, что зависимость может быть выведена из F по аксиомам 1˚-3˚.

Лемма1: Функциональная зависимость следует из аксиом вывода, если

Билет 27. Определение замыкания множества функциональных зависимостей и замыкания множества атрибутов относительно ФЗ. Алгоритм нахождения замыкания множества атрибутов.

Вычисление замыканий.

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

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

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

Алгоритм вычисления:

Дано: конечное множество атрибутов , множество функциональных зависимостей F на и .

1˚ ;

2˚

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

Выполняем 2) до тех пор, пока не рассмотрим все функциональные зависимости.

Пример: Найти замыкание множества атрибутов относительно замыкания функциональных зависимостей.

1. 

2.

_{3. Рассмотрим функциональные зависимости:}

Билет 28. Определение декомпозиции схемы отношений.

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

1. свойство соединения без потерь:

,

где является естественным соединением его проекций на все .

Метод, проверяющий сохраняется ли свойство соединения без потерь:

Строится таблица с n столбцами и k строками. Столбец j соответствует атрибуту , а i-я строка отношению . На пересечении строки i и столбца j поместим символ a_j, если . В противном случае туда поместим символ b_ij.

Повторно рассматриваем каждую из зависимостей в до тех пор, пока в таблице невозможно будет сделать какие-либо изменения. Всякий раз, рассматривая зависимости , мы ищем строки, которые совпадают по всем столбцам, соответствующим атрибутам из X. При обнаружении двух таких строк отождествляем их символы в столбцах, соответствующих атрибутам из Y. Если при этом один из отождествляемых символов = a_j, приравниваем и другому a_j. В том случае, когда они равны b_lj и b_lj, делаем их оба равными b_lj или b_lj по своему усмотрению.

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

Пример:

	N	A	T	C
R1	a1	a2	b13	b14 a4
R2	a1	b22 a2	a3	a4

• декомпозиция обладает свойством соединения без потерь.

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

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

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

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

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

Билет 29. Аномалии, возникающие при проектировании БД. Нормализация отношений.

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

Пример: Поставщик (ФИО; номер; адрес; товар; количество)

Избыточность: если разный товар поставляется одним и тем же поставщиком, то его адрес повторяется всякий раз.  Обновление: если изменяется адрес поставщика, то его надо менять во всех кортежах; если этого не случится, то у поставщика будут разные адреса. Удаление: если в данный момент прекратил поставлять товар, то его адрес утрачивается. Включение: не может быть включена запись о поставщике, не поставляющем в данный момент товар.

Все проблемы исчезают, если заменить это отношение двумя:

Поставщик (ФИО; номер; адрес)

Поставка (номер поставщика; товар; количество)

Такая схема получается в результате нормализации отношений. Введены 4 уровня нормализации схем отношений, которые называются соответственно 4-мя нормальными формами:

1НФ: Схема отношений находится в 1НФ т. и т.т., когда все входящие в нее атрибуты являются атомарными (неделимыми).

1НФ достаточна для рассматриваемых языков запросов.

2НФ: Если – ключ отношения , непервичный атрибут отношения ( ), первичный атрибут, если он является элементом какого-либо ключа отношения , то говорят, что в отношении имеет место частичная зависимость (неполная функциональная зависимость), когда наблюдается: и . Если это условие не выполняется, то говорят, что атрибут функционально полно зависит от в отношении : .

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

3НФ: Транзитивная зависимость. Для данной схемы отношений , подмножества , атрибута в и множества функциональных зависимостей , атрибут называется транзитивно зависимым от в , если существует подмножество такое, что относительно и .

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

3НФ избавляет от аномалий включения, удаления, модификации.

НФБК: (Бойса-Кодда) Схема отношений находится в НФБК относительно множества функциональных зависимостей , если она находится в 1НФ и никакой атрибут в не зависит транзитивно ни от одного ключа . (ни один из выделенных ключей не зависит транзитивно ни от одного ключа +3НФ). НФБК=> 3НФ.

Билет 30. Алгоритмы приведения отношений к 3 НФ.

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

П ример: номер поставщика → товар | номер поставщика → индекс товара товар ФИО, адрес → товар |

2НФ | 3НФ

Алгоритм 1: пополняющий декомпозицию схем отношений, которая обладает свойством соединения без потерь и приводит к отношениям находящимся в НФБК.

Входные данные: схема отношения и функциональные зависимости .

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

Метод: декомпозиция для конструируется итеративным методом

. Существует ключ . Если схема отношения из и не находится в НФБК, то пусть – зависимость, имеющая место в , где не содержит ключа , а . Тогда в должен существовать некоторый атрибут, который не принадлежит и не принадлежит . В противном случае содержал бы ключ . Заменим на и , где состоит из и атрибутов , а – из всех атрибутов , за исключением . и . (это удаление транзитивной зависимости .

Декомпозиция на и обладает свойством соединения без потерь относительно множества функциональных зависимостей, спроецированных на . Если в и существуют транзитивные зависимости, то делаем декомпозиции и для . Т.к. в и меньше атрибутов, чем в , мы достигнем в конце концов некоторого момента, когда любая схема отношения в будет находиться в НФБК. При этом обладает свойством соединения без потерь, т.к. начальное состояние состоит только из , и все модификации сохраняли свойство соединения без потерь.

Алгоритм 2: приведения отношения к 3НФ, использующей декомпозицию, сохраняющую функциональные зависимости.

Входные данные: схема отношения и множество функциональных зависимостей .

Выходные данные: сохраняющая зависимости декомпозиция схемы отношения такая, что каждая входящая в нее схема отношения находится в 3НФ относительно проекции на эту схему.

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

Теорема: Пусть декомпозиция , образованная схемами отношений в 3НФ и построенная по алгоритму 2. Пусть ключ . Тогда декомпозиция такая, что все ее схемы отношений находятся в 3НФ. Эта декомпозиция сохраняет зависимости и обладает свойством соединения без потерь.

Пример:

В декомпозицию будут входить

Билет 31. Многозначные зависимости(МЗ). Правила вывода для МЗ. Четвертая НФ.

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

Пусть задана схема отношений , атрибуты . Существует (X мультиопределяет Y) – многозначная зависимость, если:

Из симметрии определения и следует, что в существует :

.

Правила вывода (аксиомы) для многозначных зависимостей.

А1. (дополнение для многозначной зависимости)

Если , то

А2. (пополнение для мн.з.)

Если и , то

А3. (транзитивность для мн.з.)

Если и , то