Понятие предиката

Даны некоторые попарно не пересекающиеся произвольные множества D₁, D₂, …, D_n, D_i ∩ D_j = 0 для любых i ≠ j, и переменные x₁, x₂, …, x_n, принимающие значения из соответствующих множеств: x_i ∈ D_i для любых i.

Тогда предикатом (или предикатной функцией) называется функция P(x₁, x₂, …, x_n), принимающая одно из двух значений – 1 или 0 (истина или ложь).

Переменные x₁, x₂, …, x_n называются предикатными переменными. Множества D₁, D₂, …, D_n образуют область интерпретации предиката.

В записи предиката, наряду с логическими операциями ∧, ∨, ¬, смысл и использование которых традиционны, используются специальные операции – кванторы: всеобщности ∀ и существования ∃. Смысл использования кванторов следующий:

∀ x (f(x)) означает, что для всех значений x из области интерпретации формула f(x) имеет значение "истина";

∃ x (f(x)) означает, что существует, по крайней мере, одно значение x из области интерпретации, для которого формула f(x) имеет значение "истина".

Примеры

Пусть переменная x определена на множестве "учебная группа"; f(t) – утверждение

" t получает стипендию"; тогда предикат ∃ x (f(x)) имеет значение "истина", если хотя бы один член группы (не важно, кто именно) получает стипендию, и ложь, если никто в группе не получает стипендию.

Пусть переменная x определена на множестве "учебная группа"; f(t) – утверждение

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

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

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

Рассмотрим следующий пример:

В примере пронумеровано использование переменных, в соответствии с их появлением в кванторах и в формуле. В соответствии с этим, в первой подформуле все вхождения x (помеченные цифрой 1) связаны квантором ∀; первое вхождение y (помеченное цифрой 2) свободно; следующие вхождения y (помеченные цифрой 3) связаны квантором ∃; вхождение переменной z (помеченное цифрой 4) свободно. Во второй подформуле все вхождения переменной x (помеченные цифрами 5 и 8) связаны кванторами ∀ и ∃, соответственно; вхождение y (помеченное цифрой 7) свободно; и, наконец, вхождение переменной r (помеченное цифрой 6) связано квантором ∃.

Кванторы в реляционном исчислении определяют области значений и видимости переменных. Это означает следующее.

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

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

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

Приведенный предикат интерпретируется следующим образом: существует хотя бы одно значение x ∈ D, которое четно и совпадает со значением некоторой свободной переменной y. Следовательно, если свободная переменная y имеет конкретное значение, например, 6, приведенный предикат будет иметь значение "истина", и значение переменной y входит в результат. Если же переменная y будет иметь значение 7 или 12, тогда предикат будет иметь значение "ложь", и данное значение y не войдет в результат.

В реляционном исчислении областью интерпретации предиката является база данных – т.е. множество всех значений всех доменов, на которых определены все схемы отношений, определяющие схему базы данных. Соответствие между предикатом P и отношением r(A₁, A₂,..., A_n) заключается в следующем:

Если P(a₁, a₂,..., a_n) = 1, то < a₁, a₂,..., a_n > есть выборка отношения r(A₁, A₂,..., A_n), т.е.

<a₁, a₂, …, a_n> ∈ r;

Если P(b₁, b₂,..., b_n) = 0, то <b₁, b₂, …, b_n> ∉ r.

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

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

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

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

Правильно построенные формулы служат для выражения условий, накладываемых на переменные (кортежи или на доменах).

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

Как уже говорилось, в данном случае областью определения переменных являются отношения. Переменные-кортежи должны удовлетворять определенной схеме отношения R. Правильно построенная формула (wff – well formulated formula) определяет результаты отбора: выбираются те кортежи, для которых wff дает значение 1.

Обозначим правильно построенную формулу (предикат, значения которого 0 или 1) через ψ(t).

Рассмотрим правила построения ψ(t).

I. Основой формулы являются атомы, которые могут иметь значения 0 или 1.

Существует три типа атомов формулы ψ(t).

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

2. Пусть r(R) – некоторая реализация отношения, удовлетворяющая схеме R; u и v – переменные-кортежи из отношения r(R) (т.е. u ∈ r, v ∈ r); θ – арифметическая операция сравнения (<, =, >, ≥, ≠, ≤); A, B – атрибуты схемы отношения R, сравнимые по операции θ; тогда u[A] θ v[B] – атом.

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

В приведенных выше условиях запись u[A] означает «значение переменной-кортежа u по атрибуту A».

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

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

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

3. Если x(R) – переменная-кортеж из отношения r со схемой R; ψ(x) – формула, в которой переменная x имеет свободное вхождение; тогда ∀ x(R) (ψ(x)) – формула, в которой вхождение переменной x становится связанным квантором ∀. Данная формула утверждает, что для всех кортежей x из отношения r(R) при подстановке их в формулу ψ(x) вместо всех свободных вхождений x получим значение "истина". Например, формула ∀ x(R) (x[A] ≠ ∅) утверждает, что для всех кортежей значение атрибута A не пусто, т.е. атрибут А является обязательным.

4. Если ψ(x) и ϕ(x) – формулы, тогда ¬ψ(x), ψ(x) ∧ ϕ(x), ψ(x) ∨ ϕ(x) – тоже формулы. Вхождения переменной x в эти формулы остаются свободными или связанными – такими, какими были в ψ(x) или ϕ(x), соответственно. Например, если переменная x имела в ϕ(x) свободное вхождение, а в ψ(x) – связанное, то в этих функциях сохраняется тип вхождения переменных.