Слайд 2
Общая характеристика
Запрос – формула некоторой формально-логической теории; описывает
свойства желаемого результата.
Ответ – множество объектов из области
интерпретации (базы данных), на котором истинна формула, соответствующая запросу.
Формально-логическая теория – теория исчисления предикатов первого порядка, в которой формула задается в виде предиката.
Слайд 3
Понятие предиката (1)
Даны произвольные множества D1, D2, …,
Dn,
Di Dj = 0 для любых i
j, и переменные
x1, x2, …, xn, xi Di для любых i = 1, 2, …, n.
Предикатом (или предикатной функцией) называется функция P(x1, x2, …, xn), принимающая одно из двух значений – 1 или 0 (истина или ложь).
x1, x2, …, xn – предикатные переменные
D1, D2, …, Dn – область интерпретации предиката
Слайд 4
Понятие предиката (2)
Логические операции – (и),
(или), (не)
Кванторы – (всеобщности), (существования)
x
(f(x)) – для всех значений x из области интерпретации предиката формула f(x) имеет значение "истина";
x (f(x)) – существует, по крайней мере, одно значение x из области интерпретации предиката, для которого формула f(x) имеет значение "истина"
x (f(x)) эквивалентно x (f(x))
Слайд 5
Связь предиката с базой данных
Область интерпретации предиката –
база данных
Соответствие между предикатом P(x1, x2, …, xn) и
отношением r(R), R(A1:D1, A2:D2,..., An:Dn):
a1 D1, a2 D2, …, an Dn
1. Если P(a1, a2, ..., an) = 1, то
есть выборка отношения R(A1:D1, A2:D2,..., An:Dn), т.е. r
2. Если P(a1, a2, ..., an) = 0, то r
Слайд 6
Реляционное исчисление с переменными-кортежами
1. Областью определения переменных являются
отношения
2. Переменные-кортежи должны удовлетворять определенной схеме отношения R
3. Предикат
– это правильно построенная формула (wff – well formulated formula) (t). Выбираются те кортежи t, для которых (t) дает значение 1
Слайд 7
Атомы wff (1)
1. Пусть r(R) – некоторая реализация
отношения, удовлетворяющая схеме R;
t – некоторая переменная-кортеж, удовлетворяющая
схеме R.
Тогда r(t) – атом; означает, что t есть кортеж в отношении r (т.е. формула истинна, если
t r)
Слайд 8
Атомы wff (2)
2. Пусть r(R) – некоторая реализация
отношения, удовлетворяющая схеме R;
u и v – переменные-кортежи
из отношения r(R) (т.е. u r, v r); – арифметическая операция сравнения (, , , , , );
A, B – атрибуты схемы отношения R, сравнимые по операции .
Тогда u[A] v[B] – атом
t[X] – значение переменной t по атрибуту X
Слайд 9
Атомы wff (3)
3. Пусть u – переменная-кортеж из
отношения r(R) (т.е. u r);
– арифметическая
операция сравнения
(, , , , , );
A, B – атрибуты схемы отношения R, сравнимые по операции ;
c – константа из домена, на котором определен атрибут B.
Тогда u[A] c (или c u[A]) – атом
Слайд 10
Выражение реляционного исчисления (1)
{t(R) | (t)},
где t
– переменная-кортеж, удовлетворяющая схеме отношения R; единственная переменная, имеющая
свободное вхождение в формулу (t);
(t) – правильно построенная формула
Интерпретация: множество кортежей t, удовлетворяющих схеме отношения R, таких, для которых правильно построенная формула (t) истинна
Слайд 11
Выражение реляционного исчисления (2)
Пример
Есть отношение R(Имя, Стипендия);
атрибут
Стипендия определен на домене
D = {«да», «нет»}.
Получить
из отношения имена всех студентов, получающих стипендию:
{ t(Имя) | x(R) (r(x) x[Стипендия] = «да» x[Имя] = t[Имя]}
Слайд 12
Безопасные выражения
{t | r( t) } –
в общем случае, определяет бесконечное отношение, что недопустимо.
Безопасные
выражения вида { t | ( t) } гарантированно дают ограниченное множество кортежей.
Значения атрибутов кортежей t являются элементами некоторого ограниченного универсального множества – DOM().
DOM() – унарное отношение, элементами которого являются символы, которые либо явно появляются в , либо служат компонентами какого-либо кортежа в некотором отношении R, упоминаемом в
Слайд 13
Реляционное исчисление с переменными на доменах (1)
Атомы:
r(x1 ,
x2 , … , xn), где r – отношение,
удовлетворяющее схеме R(A1 , A2 , …An), и каждое xi есть константа или переменная на домене;
u v, где u и v – константы или переменные, определенные на доменах, совместимых по операции , – арифметическая операция сравнения (, , , , , );
Слайд 14
Реляционное исчисление с переменными на доменах (2)
Формула реляционного
исчисления (t), а также свободные и связанные вхождения переменных
определяются так же, как и для исчисления с переменными-кортежами.
Слайд 15
Реляционное исчисление с переменными на доменах (3)
Пример. Пусть
мы имеем базу данных служащих. Будем считать, что мы
определили доменные переменные, имена которых совпадают с именами атрибутов отношения СЛУЖАЩИЕ
WFF исчисления доменов:
СЛУЖАЩИЕ (СЛУ_НОМ:2934, СЛУ_ИМЯ:'Иванов', СЛУ_ЗАРП:22400.00, ПРО_НОМ:1)
примет значение true в том и только в том случае, когда в теле отношения СЛУЖАЩИЕ содержится кортеж <2934, 'Иванов', 22400.00, 1>. Соответствующие значения доменных переменных образуют область истинности этой WFF.
