МД и СУБД(Л4)

1.

МД и СУБД
Реляционное исчисление
Математической основой реляционного исчисления
предикатов – один из разделов математической логики.
является
исчисление
В теории исчисления предикатов под предикатом подразумевается истинностная
функция с переменными. После подстановки значений вместо переменных
функция становится выражением, называемым суждением, которое может быть
истинным или ложным. Например, предложения «Иванов И.И. является
сотрудником данной организации" и «Иванов И.И. имеет более высокую зарплату,
чем Сидоров С.С." являются суждениями, поскольку можно определить их
истинность или ложность. В первом случае функция "является сотрудником данной
организации" имеет один параметр ("Иванов И.И."), а во втором случае функция
"имеет более высокую зарплату, чем" имеет два параметра
(" Иванов И.И. " и " Сидоров С.С .").
Неформально говоря, предикат – это высказывание, в которое можно подставлять
аргументы. Если аргумент один – то предикат выражает свойство аргумента, если
больше – то отношение между аргументами.
Являясь формализованным аналогом обычной логики, реляционное исчисление
дает возможность строго рассуждать об истинности и ложности утверждений и об
их взаимосвязи, в частности, о логическом следовании одного утверждения из
другого, или, например, об их эквивалентности.

2.

МД и СУБД
Чтобы задать n-местный предикат P(x1,…,xn), следует указать множества D1,…, Dn области изменения предметных переменных x1,…,xn.
Предикат называют тождественно-истинным и пишут:
P(x1,…,xn) = 1 ,
если на любом наборе аргументов он принимает значение 1.
Предикат называют тождественно-ложным и пишут:
P(x1,…,xn) = 0 ,
если на любом наборе аргументов он принимает значение 0.
Операции над предикатами.
Логические операции:
Конъюнкцией двух предикатов А(х) и В(х) называется новый предикат , который
принимает значение «истина» при тех и только тех значениях х из D= D1 X…XDn ,
при которых каждый из предикатов принимает значение «истина», и принимает
значение «ложь» во всех остальных случаях. Множеством истинности Т
конъюнкции предикатов А(х), В(х), является пересечение множеств истинности
предикатов А(х) – Т1 и В(х) – Т2, т.е. Т= Т1 ∩Т2.
Например: А(х): «х –четное число», В(х): « х кратно 3». А(х)&В(х) – «х – четное
число и х кратно 3». Т.е. предикат «х делится на 6».

3.

МД и СУБД
Дизъюнкцией двух предикатов А(х) и В(х) называется новый предикат ,
который принимает значение «ложь» при тех и только тех значениях х из D,
при которых каждый из предикатов принимает значение «ложь» и
принимает значение «истина» во всех остальных случаях. Областью
истинности предиката А(х), В(х) является объединение областей
истинности предикатов А(х), В(х).
Отрицанием предиката А(х) называется новый предикат , который
принимает значение «истина» при всех значениях х из D , при которых
предикат А(х) принимает значение «ложь», и принимает значение «ложь»,
если А(х) принимает значение «истина». Множеством истинности предиката
является дополнение Т' к множеству Т истинности А(х) в множестве D.
Импликацией предикатов А(х) и В(х) называется новый предикат, который
является ложным при тех и только тех значениях х из D , при которых А(х)
принимает значение «истина», а В(х) – значение «ложь» и принимает
значение «истина» во всех остальных случаях. Читают: «Если А(х), то В(х)».
Например. А(х): «Натуральное число х делится на 3». В(х): «Натуральное
число х делится на 4», можно составить предикат: «Если натуральное
число х делится на 3, то оно делится и на 4». Множеством истинности
предиката А(х), В(х) является объединение множества Т2 – истинности
предиката В(х) и дополнения к множеству Т1 истинности предиката А(х).

4.

МД и СУБД
Кванторные операции. (Ква́нтор — общее название для логических
операций, ограничивающих область истинности какого-либо предиката).
В математической логике приписывание квантора к формуле называется
связыванием или квантификацией.
Квантор (все-)общности.
Квантор существования.
Квантор существования по переменной.
Синтаксически задание n-местного предиката осуществляется указанием
формулы логико-математического языка, содержащей n переменных.
В наиболее распространённом случае такой язык содержит предметные
переменные x, y,z,…, функциональные символы f, g, h,… с различным
количеством аргументных мест и предикатные символы P, Q, R,… также с
различным количеством аргументных мест. Из переменных и функциональных
символов конструируются термы языка, содержательно интерпретируемые как
имена объектов исследования. Если P есть n местный предикатный символ,
n 0, а t1,…,tn – термы, то P(t1,…,tn) есть, по определению, атомарная формула.
Содержательно P(t1,…,tn) означает, что истинно высказывание, гласящее, что
t1,…,tn связаны отношением P.

5.

МД и СУБД
Из атомарных формул с помощью пропозициональных связок и кванторов конструируются
формулы языка. Обычный набор связок состоит из операторов сравнения, а набор
операций включает конъюнкцию, дизъюнкцию, импликацию, отрицание, квантор “для всех”,
квантор “существует”. Вхождения переменной x в формулу называется связанным, если x
входит в часть вида x или x . Остальные вхождения называются свободными.
В контексте баз данных исчисление предикатов существует в двух формах: реляционного
исчисления кортежей и реляционного исчисления доменов.
В реляционном исчислении кортежей задача состоит в нахождении таких кортежей, для
которых предикат является истинным. Это исчисление основано на переменных кортежа, то
есть переменных, для которых допустимыми значениями могут быть только кортежи
данного отношения.
Описательную часть исчисления можно представить в виде:
RANGE OF <переменная> IS <список>.
Здесь <переменная> – это идентификатор переменной кортежа, <список> – конструкция
вида X1[,X2[,…,Xn]…]. Список содержит элементы, каждый из которых является либо
отношением, либо выражением над отношениями.
Область допустимых значений <переменной> образуется путем объединения значений всех
элементов списка. Выражение реляционного исчисления, формирующего запрос на языке
исчисления кортежей, упрощенно можно записать в виде:
(Y1[,Y2[…,Ym]…]) [WHERE wff].
Здесь Yi – это запись вида
{<переменная> <переменная>.<атрибут>} [AS <атрибут>]

6.

МД и СУБД
Соответственно, wff – well-formed formula (правильно построенная формула) – это
предикат, который записывается одним из следующих типов:
<условие>
NOT wff
<условие> AND wff
<условие> OR wff
IF <условие> THEN wff
EXISTS <переменная> (wff)
FOR ALL <переменная> (wff)
(wff)

7.

МД и СУБД
Например, предположим, что имеется три отношения, О1, О2, О3:
O1
O3
ПР
КАФ
ФАКУЛТ
П1
К1
Ф1
П2
К1
П3
К2
O2СТУД
КУРС
ГР
С1
3
2
Ф1
С2
3
1
Ф1
С3
4
2
С4
4
1
ПР
СТУД
ЧАС
П1
С1
10
П2
С2
10
П2
С3
10
П3
С1
10
П3
С4
20

8.

МД и СУБД
Создадим список преподавателей, работающих на кафедре К1.
RANGE OF S IS O1
(S.ПР) WHERE S.КАФ=’К1’
Создадим список преподавателей, студентов и часов, для студентов четвёртого
курса.
RANGE OF P IS O2
RANGE OF V IS O3
(V) WHERE EXISTS P (V.СТУД=P.СТУД AND P.КУРС=4)
Этот же список можно сформировать следующим образом
RANGE OF P IS O2
RANGE OF V IS O3
RANGE OF VP IS (V) WHERE EXISTS P (V.СТУД=P.СТУД AND P.КУРС=4)
(VP)

9.

МД и СУБД
В реляционном исчислении доменов используются переменные, значения которых
берутся из доменов, а не из кортежей отношений. Исчисление доменов
поддерживает дополнительную форму условий, называемую условием
принадлежности. В общем виде условие принадлежности
записывается в виде R(A1:p1, A2:p2,…), где Ai – атрибут отношения R, а pi –
переменная домена или литерал. Условие считается истинным тогда и только
тогда, когда в отношении R имеется кортеж со значениями pi для атрибутов Ai.
Для приведенных выше в примере первого списка выражения исчисления доменов
будут иметь вид
(S) WHERE О1 (КАФ : ‘К1’)
Здесь S – переменная домена атрибута ПР, объявленная каким-либо образом,
подобно оператору RANGE исчисления кортежей
(например, RANGE OF S IS D(КАФ);).
В заключении заметим, что если реляционное исчисление ограничивается только
безопасными (т.е. имеющими смысл) выражениями, то реляционное исчисление
доменов эквивалентно реляционному исчислению кортежей, которое в свою
очередь эквивалентно реляционной алгебре.