Реляционное исчисление

Общая характеристика Запрос – формула некоторой формально-логической теории; описывает свойства желаемого результата. Ответ – множество объектов из области интерпретации (базы данных), на котором истинна формула, соответствующая запросу. Формально-логическая теория – теория исчисления предикатов первого порядка, в которой формула задается в виде предиката.

Понятие предиката (1) Даны произвольные множества D 1, D 2, …, D n, D i D j = 0 для любых i j, и переменные x 1, x 2, …, x n, x i D i для любых i = 1, 2, …, n. Предикатом (или предикатной функцией) называется функция P(x 1, x 2, …, x n ), принимающая одно из двух значений – 1 или 0 (истина или ложь). x 1, x 2, …, x n – предикатные переменные D 1, D 2, …, D n – область интерпретации предиката

Понятие предиката (2) Логические операции – (и), (или), (не) Кванторы – (всеобщности), (существования) x (f(x)) – для всех значений x из области интерпретации предиката формула f(x) имеет значение "истина"; x (f(x)) – существует, по крайней мере, одно значение x из области интерпретации предиката, для которого формула f(x) имеет значение "истина" x (f(x)) эквивалентно x ( f(x))

Пример использования кванторов S – множество "учебная группа" f1(t) – утверждение t получает стипендию, t S f2(t) – утверждение t не имеет задолженностей в сессию, t S Переменная x S 1. x (f1(x)) имеет значение "истина", если хотя бы один член группы получает стипендию, и ложь, если никто в группе не получает стипендию. 2. x (f2(x)) имеет значение "истина", если все члены группы не имеют задолженностей в сессию, и ложь, если хотя бы один член группы имеет задолженность

Вхождение переменных Предикатная формула (предикат) (t) Вхождение переменной t в формулу связано, если переменная t находится в в подформуле, начинающейся кванторами или, за которыми непосредственно следует переменная t; тогда о кванторе говорят, что он связывает переменную t. В остальных случаях t входит в свободно

Пример x(R(x, y) y(U(x, y, z) Q(x, y))) Переменная x связана квантором Свободное вхождение переменной y Переменная у связана квантором Свободное вхождение переменной z

Области значений и видимости переменных (1) 1. В предикате используются и свободные, и связанные переменные 2. Если для какого-то определенного набора свободных переменных при вычислении предикатной формулы получено значение "истина", значит, этот набор значений свободных переменных войдет в результат, определяемый предикатом

Области значений и видимости переменных (2) 2. Если вхождение переменной в формулу связано квантором, такая переменная не видна за пределами формулы, связавшей эту переменную. При вычислении значения такой формулы используются все значения из области определения данной переменной

Области значений и видимости переменных (3) Пример: дано множество десятичных цифр D = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}. Подмножество, состоящее из четных цифр, можно определить следующим образом: множество всех значений y, таких, для которых выполняется условие: x (x D x 2 = 0 y = x).

Связь предиката с базой данных Область интерпретации предиката – база данных Соответствие между предикатом P(x 1, x 2, …, x n ) и отношением r(R), R(A 1 :D 1, A 2 :D 2,..., A n :D n ): a 1 D 1, a 2 D 2, …, a n D n 1. Если P(a 1, a 2,..., a n ) = 1, то есть выборка отношения R(A 1 :D 1, A 2 :D 2,..., A n :D n ), т.е. r 2. Если P(a 1, a 2,..., a n ) = 0, то r

Реляционное исчисление с переменными-кортежами 1. Областью определения переменных являются отношения 2. Переменные-кортежи должны удовлетворять определенной схеме отношения R 3. Предикат – это правильно построенная формула (wff – well formulated formula) (t). Выбираются те кортежи t, для которых (t) дает значение 1

Атомы wff (1) 1. Пусть r(R) – некоторая реализация отношения, удовлетворяющая схеме R; t – некоторая переменная-кортеж, удовлетворяющая схеме R. Тогда r(t) – атом; означает, что t есть кортеж в отношении r (т.е. формула истинна, если t r)

Атомы 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

Атомы wff (3) 3. Пусть u – переменная-кортеж из отношения r(R) (т.е. u r); – арифметическая операция сравнения (,,,,, ); A, B – атрибуты схемы отношения R, сравнимые по операции ; c – константа из домена, на котором определен атрибут B. Тогда u[A] c (или c u[A]) – атом

Правила построения wff (1) 1. Каждый атом есть формула. Все вхождения переменных-кортежей, упомянутых в атоме, являются свободными. Например, формула r(t) утверждает, что переменная- кортеж t является кортежем отношения r(R)

Правила построения wff (2) 2. Пусть x(R) – переменная-кортеж из отношения r со схемой R; (x) – формула, в которой переменная x имеет свободное вхождение. Тогда x(R) ( (x)) – формула, в которой вхождение переменной x становится связанным квантором : существует хотя бы один кортеж x в отношении r(R), такой, что при подстановке его в формулу (x) вместо всех свободных вхождений x получим значение "истина "

Правила построения wff (3) Пример Формула x(R) (r(x)) утверждает, что отношение r не пусто – существует хотя бы один кортеж x, принадлежащий r

Правила построения wff (4) 3. Пусть x(R) – переменная-кортеж из отношения r со схемой R; (x) – формула, в которой переменная x имеет свободное вхождение. Тогда x(R) ( (x)) – формула, в которой вхождение переменной x становится связанным квантором : для всех кортежей x из отношения r(R) при подстановке их в формулу (x) вместо всех свободных вхождений x получим значение "истина"

Правила построения wff (5) Пример Формула x(R) (x[A] ) утверждает, что для всех кортежей значение атрибута A не пусто, т.е. атрибут А является обязательным

Правила построения wff (6) 4. Если (x) и (x) – формулы, тогда (x), (x) (x), (x) (x) – тоже формулы. Вхождения переменной x в эти формулы остаются свободными или связанными – такими, какими были в (x) или (x), соответственно

Правила построения wff (7) 5. Если (x) – формула, то ( (x)) – тоже формула; вхождение переменной x остается свободным или связанным – таким, каким оно было в (x) 6. Ничто иное не является формулой

Порядок вычисления wff 1.Атомы, в которых могут быть использованы арифметические операции сравнения 2.Кванторы 3.Отрицание ( ) 4.Операция "И" ( ) 5.Операция "ИЛИ" ( ) Скобки используются для изменения порядка вычисления формулы

Выражение реляционного исчисления (1) {t(R) | (t)}, где t – переменная-кортеж, удовлетворяющая схеме отношения R; единственная переменная, имеющая свободное вхождение в формулу (t); (t) – правильно построенная формула Интерпретация: множество кортежей t, удовлетворяющих схеме отношения R, таких, для которых правильно построенная формула (t) истинна

Выражение реляционного исчисления (2) Пример Есть отношение R(Имя, Стипендия); атрибут Стипендия определен на домене D = {«да», «нет»}. Получить из отношения имена всех студентов, получающих стипендию: { t(Имя) | x(R) (r(x) x[Стипендия] = «да» x[Имя] = t[Имя]}

Безопасные выражения {t | r( t) } – в общем случае, определяет бесконечное отношение, что недопустимо. Безопасные выражения вида { t | ( t) } гарантированно дают ограниченное множество кортежей. Значения атрибутов кортежей t являются элементами некоторого ограниченного универсального множества – DOM( ). DOM( ) – унарное отношение, элементами которого являются символы, которые либо явно появляются в, либо служат компонентами какого-либо кортежа в некотором отношении R, упоминаемом в

Эквивалентность выражений (1) Если E – выражение реляционной алгебры, то существует эквивалентное ему безопасное выражение реляционного исчисления с переменными-кортежами Проекция L (r), r(R), L R – выражение реляционной алгебры {t(L) | u(R) (r(u) u[L] = t[L] } – эквивалентное выражение реляционного исчисления

Эквивалентность выражений (2) Деление r 1 r 2, r 1 (AB), r 2 (B) – выражение реляционной алгебры { t(A) | x(B) ( y(AB) (r 2 (x) r 1 (y) y[B] = x[B] y[A] = t[A] } – эквивалентное выражение реляционного исчисления

Эквивалентность выражений (3) Естественное соединение r 1 r 2, r 1 (AB), r 2 (BC) – выражение реляционной алгебры { t(ABC) | u(AB) v(BC) ( r 1 (u) r 2 (v) u[B] = v[B] t[AB] = u[AB] t[C] = v[C]) } – эквивалентное выражение реляционного исчисления

Примеры запросов (1) Схема базы данных: S(Sid, SN, SC) – ПОСТАВЩИК ( Номер поставщика, Имя, Город) P(Pid, PN, PC) – ДЕТАЛЬ ( Номер детали, Название, Цена) SP(Sid(FK1), Pid (FK2), QTY) – ПОСТАВКА ( Номер поставщика, Номер детали, Количество)

Примеры запросов (2) Обозначения: S, P, SP – и схемы базы данных, и реализации (по месту использования) 1. Получить имена поставщиков, поставляющих деталь с номером P1. {t(SN) | u(S) v(SP) (S(u) SP(v) u[Sid] = v[Sid] v[Pid] = P1 u[SN] = t[SN])}

Примеры запросов (3) 2. Получить имена поставщиков, не поставляющих деталь с номером P1 {t(SN) | u(S)(S(u) v(SP) (SP(v) v[Pid] = P1 u[Sid] = v[Sid] u[SN] = t[SN]))}

Примеры запросов (4) 3. Получить имена поставщиков, поставляющих только деталь с номером P1 {t(SN) | u(S) v(SP)(S(u) SP(v) u[Sid] = v[Sid] v[Pid] = P1 u[SN] = t[SN] w(SP)(SP(w) w[Sid] = u[Sid] w[Pid] P1))}

Примеры запросов (5) 4. Получить имена поставщиков, поставляющих все детали {t(SN) | u(S) w(P) v(SP) (S(u) P(w) SP(v) w[Pid] = v[Pid] u[Sid] = v[Sid] t[SN] = u[SN])}

Реляционное исчисление с переменными на доменах (1) Атомы: r(x 1, x 2, …, x n ), где r – отношение, удовлетворяющее схеме R(A 1, A 2, …A n ), и каждое x i есть константа или переменная на домене; u v, где u и v – константы или переменные, определенные на доменах, совместимых по операции, – арифметическая операция сравнения (,,,,, );

Реляционное исчисление с переменными на доменах (2) Формула реляционного исчисления (t), а также свободные и связанные вхождения переменных определяются так же, как и для исчисления с переменными- кортежами.

Эквивалентность выражений (1) Для каждого безопасного выражения с переменными-кортежами существует эквивалентное безопасное выражение с переменными на доменах {t(R) | (t)}, R = (A 1, A 2, …, A n ) – выражение исчисления с переменными-кортежами Эквивалентное выражение с переменными на доменах: {t 1, t 2, …, t n | ΄(t 1, t 2, …, t n )}

Эквивалентность выражений (2) 1. Переменная-кортеж t заменяется n новыми переменными на доменах t 1, t 2, …, t n 2. ΄ представляет собой, в которой: a) любой атом r(t) заменяется атомом r(t 1, t 2, …, t n ); b) каждое свободное вхождение t[A i ] заменено переменной t i ;

Эквивалентность выражений (3) c) для каждого квантора u или u вводится m новых переменных u 1, u 2, …, u m (m – арность u). Кванторы u (или (u)) заменяются кванторами u 1 u 2 … u m ( u 1 u 2 … u m, соответственно); в подчиненных кванторам выражениях u[A i ] заменяются u i, а r(u) – r(u 1, u 2, …, u m )

Эквивалентность выражений (4) Получить имена поставщиков, поставляющих деталь с номером P1 {t(SN) | u(S) v(SP) (S(u) SP(v) u[SN] = t[SN] u[Sid] = v[Sid] v[Pid] = P1)} Эквивалентное выражение: {t(SN) | u 1 (Sid) u 2 (SN) u 3 (SC) v 1 (Sid) v 2 (Pid) v 3 (QTY) (S(u 1,u 2,u 3 ) SP(v 1,v 2,v 3 ) u 2 = t u 1 = v 1 v 2 = P1)}