4.1. Теоретико-множественная модель предикатов

Логика и предикаты

Под логикой обычно понимают систематический метод рассуждений. В зависимости от того, к каким классам объектов применяют систематический метод рассуждений, различают конкретные системы логики, называемые исчислениями. Если в качестве объектов выступают высказывания (предложения-константы), то говорят об исчислении высказываний. Если оперируют с предложениями-переменными, то говорят об исчислении предикатов.

Примером высказывания является суждение: «SQL есть язык манипулирования данными». Если в суждение вводится параметр-переменная, то мы имеем дело с предикатом. Предикатом называется функция одного или нескольких переменных с логическими значениями истина или ложь.

Примером предиката является суждение "Компания Oracle производит Х". Если вместо «Х» подставить «СУБД Oracle XE 11g», то вы имеете истинное значение суждения. Если вы подставите слово «яблоки», то значение суждения окажется ложным.

Систематический метод рассуждений предполагает наличие определенной алгебраической схемы, в рамках которой определены операции над объектами и законы для этих операций (правила эквивалентных преобразований). В исчислении предикатов в качестве законов выступают законы булевой алгебры, а в качестве операций конъюнкция (AND), дизъюнкция (OR), отрицание (NOT), импликация и эквивалентность. Две последние операции могут быть выражены через три первых.

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

Кванторные утверждения о данных

Для управления областью значений переменных в предикатах используются два специальных знака, называемые кванторами. ∀ - квантор общности, означает «для каждого» или «для всех», а ∃ - квантор существования, означает «существует хотя бы одно» или «для некоторых». Кванторы указываются впереди переменных. Если применяется квантор общности, то мы говорим, что утверждение истинно для всех значений переменной из некоторого множества значений. Квантор общности применяется, когда нужно сказать, что существует хотя бы одно значение переменной, для которой истинно данное утверждение. Кванторы можно комбинировать в одном предложении, а также выносить перед предложением, при этом часто используется переименование переменных в независимых от конкретных кванторов компонентах предложения.

Предложения формулируются на естественном языке. Исчисление предикатов служит формальным средством анализа предложений естественного языка за счет перефразирования последних на язык предикатов и использования законов логики. Для того, чтобы перевести предложение с естественного языка на язык исчисления предикатов, необходимо найти такие слова, как «любой», «каждый», «всякий», которые переходят в кванторы общности, и такие слова, как «некоторый», «какой-то», которые переходят в кванторы существования. Слова, связанные с кванторами, представляют переменные предикатов. Затем, необходимо найти союзы «и», «или» и частицу «не», которые определяют логические связи предикатов предложения. Кроме того, следует обратить внимание на такие слова, как «влечет», «следует», которые определяют операции импликации, и такие слова, как «эквивалентно», «одно и то же», которые определяют операцию эквивалентности. После этого вам можно переходить собственно к определению предикатов, составляющих предложение.

Например, рассмотрим предложение: «Любой футболист “Спартака” имеет возраст меньше 30 лет». Здесь в качестве переменных выступают слова «футболист» (обозначим через x) и «количество» лет (обозначим через y). Переменная x связана квантором всеобщности, а переменная y имеет значение 30 лет. Глагол «имеет» выражает здесь следствие одной части предложения из другой, т.е. импликацию. Окончательно, предложение может быть представлено в виде импликации двух предикатов В_Спартаке_играет(x) и Возраст_меньше(x,y): (∀x) В_Спартаке_играет (x) ⇒ Возраст_меньше ( x,30).

Для предикатов и высказываний справедливы законы булевой логики, основные из которых приведены ниже (A, B, C - некоторые предикаты).

• Коммутативность: A AND B = B AND A; A OR B = B OR A.
• Ассоциативность: A AND (B AND C) = (A AND B) AND C; A OR (B OR C) = (A OR B) OR C.
• Дистрибутивность: A AND (B OR C) = (A AND B) OR (A AND C); A OR (B AND C) = (A OR B) AND (A OR C).
• Свойства AND и OR: A AND true = true; A AND false = false; A OR false = A; A OR true = true.
• Свойства отрицания: A AND NOT A = false; A OR NOT A = true.

Эти пять основных законов определяют булеву алгебру. Из них могут быть получены другие полезные законы, в частности нам потребуется далее закон де Моргана:

NOT (A AND B) = (NOT A) OR (NOT B),

NOT (A OR B) = (NOT A) AND (NOT B).

Для операции «если А, то В» справедлива эквивалентность (NOT A) OR B.

Доказывается, что любое выражение исчисления предикатов можно привести к конъюнктивной (или дизъюнктивной) нормальной форме, т. е. представить как конъюнкцию дизъюнктов, каждый из которых является литерой или дизъюнкцией литер. Это позволяет свести сложное предложение исчисления высказываний к комбинации простых.

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

Множества и предикаты

Область изменения переменных предикатов принято называть предметной областью или универсумом. Для простоты рассуждений ограничимся одноместными предикатами (с одним аргументом). Каждый предикат можно представить множеством значений аргумента, на которых он принимает истинное значение. Это множество называется экстенсионалом предиката. С другой стороны, если взять такое множество, то его характеристическую функцию, равную 1, если точка принадлежит множеству, и 0 в противном случае, можно рассматривать как предикат. Предикат имеет два значения: истина (1) и ложь (0). Таким образом, существует взаимно однозначное соответствие между предикатом и его экстенсионалом.

Пользуясь этим соответствием можно дать интерпретацию выражения, написанного на языке исчисления предикатов, средствами теоретико-множественных операций на их экстенсионалах. Основные эквиваленты логических и теоретико-множественных выражений даны в Таблице 4.1. P и R означают экстенсионалы предикатов p(x) и r(x), соответственно, U - универсум, ∅ - пустое множество.

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

Базы данных и предикаты

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

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

С другой стороны, БД содержат знания о предметной области фрагмента окружающего мира: факты и, возможно, правила манипулирования ими (правила вывода). Факт - это простейший вид утверждения, констатация того, что выполнено определенное отношение между атрибутами объекта (экземпляр отношения). Правила есть также утверждения о выводимости некоторого факта из заданной совокупности фактов (взаимосвязь между фактами). Знания о предметной области БД формулируется на естественном языке. Исчисление предикатов дает средства формализации этих знаний и представления их отношениями.

Запросы к БД формулируются также на естественном языке и могут быть представлены в виде предикатов, истинность которых должна быть проверена (выведена) на предикатах (отношениях) БД.

Связь между отношением БД и предикатом определяется через экстенсионал. Таблица 4.2 дает соответствие между основными понятиями БД и исчислением предикатов.

Таким образом, реляционные БД хранят в своих основных объектах экстенсионалы предикатов, содержащих знания о предметной области БД. Языки манипулирования данными, в нашем случае SQL, в таких БД оперируют с предикатами на отношениях БД.

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

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

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

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

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

Если в качестве переменной предиката выбирается кортеж, то имеем дело с реляционным исчислением с переменными-кортежами. Язык манипулирования данными SQL был построен именно на таком исчислении. Выражения реляционного исчисления с переменными-кортежами записываются в виде: {t|P(t)}, где P есть предикат построенный по правилам классической (булевой) логики, а t есть единственная свободная переменная-кортеж. Предикаты строятся из атомарных выражений и совокупности арифметических и логических операторов. В качестве атомарных выражений выступают выражения вида: R(t), где R - имя отношения, t - кортеж отношения, s[i]θu[j], где s[i] - i-ый атрибут переменных-кортежей s и u, θ - арифметическая операция. Вместо переменной кортежа u в последнем атомарном выражении может быть использована константа. Например, операция проекции на определенные атрибуты π_u(R) будет записана как {t(∃u)(R(u)(t[1] = u[i1]))}.

Конечность реальных отношений в БД накладывает ограничения на возможность формирования некоторых выражений. Так выражения вида {t|¬R (t)} , означающие всевозможные кортежи, не принадлежащие R, не имеют смысла в реальных БД (поскольку домен такого выражения содержит бесконечное число значений). В реляционном исчислении обычно ограничиваются рассмотрением только безопасных выражений. Для безопасных выражений каждый элемент столбца любого кортежа в предикате R принадлежит некоторому конечному множеству. Данное множество строится как объединение всех участвующих в предикате отношений, элементов их кортежей и констант.

Установлено, что для безопасных выражений реляционное исчисление на кортежах эквивалентно реляционной алгебре.

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

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

Атомарные выражения в реляционном исчислении на доменах имеют вид: либо R(x1, x2, ... , xk), где R есть к-местное отношение и каждое xi есть константа или переменная на домене, либо xθy, где x и y есть константы или переменные на доменах, а θ - арифметический оператор равнения. Смысл последнего выражения заключается в том, что x и y представляют собой значения, при которых истинно xθy. Любой предикат в таком исчислении состоит из логической комбинации этих двух видов выражений. Например, выражение {x1x2|R1(x1,x2)∧(∀y) (¬R2(x1,y)∧R3(x2,y))} имеет место для бинарных отношений R1 и R2 и означает множество кортежей из R1, таких, что ни один из их компонентов не является первым компонентом какого-либо кортежа R2.

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

Реляционная алгебра

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

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

Для иллюстрации формального описания реляционных операций введем два отношения R(a, b, c) и Q(d, e) (Таблица 4.3.)

Для обеспечения выделения столбцов из отношения предназначена операция проекции. Суть этой операции заключается в том, что берется отношение R, из него удаляются некоторые столбцы и устраняется дублирование оставшихся строк. Проекция обозначается π_i1,i2(R), где i_j -обозначают номер столбцов отношения, на которые выполняется проекция. Например, π_3,1 (R):

Операция объединения используется для объединения строк двух отношений с одинаковым числом колонок. Объединение отношений R и Q, обозначаемое R∪Q, представляет собой множество кортежей, которые принадлежат либо R, либо Q, либо им обоим. Например, R∪Q:

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

Пусть отношения R и Q имеют n и m колонок соответственно. Декартовым произведением отношений R и Q, обозначаемым как R X Q, называется множество кортежей с числом колонок n + m, в котором первые n колонок берутся из отношения R, а последние m - из отношения Q. Например, R X Q:

Пусть F является формулой над колонками отношения, образованной при помощи арифметических операций сравнения и логических операций. Селекцией (или выбором) отношения R по формуле F, обозначаемой как σ_F(R), называется множество кортежей t из R таких, что при подстановке i-ой колонки t вместо любого вхождения номера i в формулу F для всех i она окажется истинной. Например, σ_2=b(R):

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

Пересечение отношений R и Q, обозначаемое R∩Q, называется множество кортежей, принадлежащих одновременно и R, и Q. Пересечение выражается через разность по формуле R-(R-Q).

Пусть отношения R и Q имеют n и m колонок соответственно, где n > m и Q <> ∅. Тогда частное этих отношений, обозначаемое как R/Q, есть множество кортежей t с числом колонок n - m, таких, что для всех кортежей v, принадлежащих Q, кортеж tv принадлежит R. Чтобы выразить частное через основные операции, обозначим через T = π_1,2,...(n-m)(R). Тогда (TXQ)-R есть множество кортежей, не принадлежащих R. Пусть далее V = π_1,2,..,(n-m) ((TXQ)-R) множество кортежей, принадлежащих R, для которых существует некоторый кортеж Q, такой, что tv не принадлежит R. Откуда следует, что искомое частное есть разность T-V. Окончательно, имеем:

R/Q = π_1,2,..,(n-m) (R) - π_{1,2,...,(n-m)} ((π_{1,2,...,(n-m)} (R)XQ)-R).

Например,

R

Q

R/Q

Соединение отношений R и Q по столбцам i и j, обозначаемое R>_iθj< Q, где есть арифметический оператор сравнения, является обозначением селекции σ_iθ(n+j) (RXQ), если R имеет n столбцов. Например,

R

Q

R > _b<d < Q

Естественное соединение отношений R и Q, обозначаемое R >< Q, возможно лишь при наличии у этих отношений одинаково поименованных атрибутов. Сначала вычисляется декартово произведение отношений R и Q, затем в одинаково поименованных столбцах этих отношений выбираются те кортежи, для которых выполняется равенство значений в этих столбцах, и выполняется проекция π_{1,2,..,(n+m-k)} (σ_{R.A1=Q.A1∧ ... ∧R.Ak=Q.Ak}(RXQ)), где n и m число столбцов в отношениях R и Q, а k - число одинаково поименованных атрибутов. Например,

R

Q

R >< Q = π_A,B,C,D (σ_{R.B=Q.B∧R.C=Q.C}(RXQ)))

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

Сравнение реляционной алгебры и реляционного исчисления

Рассмотренные два абстрактных реляционных исчисления и реляционная алгебра служат основой реальных языков манипулирования данными. Каждый из них эквивалентен по своей выразительности двум другим. Однако, языки исчисления - непроцедурные языки, поскольку их средствами выражается конечный результат, в то время как реляционная алгебра указывает конкретный порядок выполнения операций, что позволяет отнести ее к процедурным языкам. Эффективность выполнения операций манипулирования данными при реализации запросов в реляционном исчислении чаще всего прерогатива интерпретатора, а в случае реляционной алгебры чаще всего этим приходится заниматься самому.

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

Примерами реализации рассмотренных выше языков манипулирования данными являются ISBL ( Informaition System Base Language ) - язык реляционной алгебры. SQL и QBE - языки реляционного исчисления на кортежах и доменах, соответственно.

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

Следует иметь в виду, что реальные языки манипулирования данных несколько шире по своим возможностям, чем предопределено теорией. Они помимо средств определения данных имеют средства определения производных атрибутов, выполнения арифметических операций, математических, строковых и других функций, а также поддерживают трехзначную логику (NULL-значения). Когда вы работаете с реальным языком SQL, вы должны помнить, что все вышеприведенные рассмотрения относятся в большей своей части к двузначной классической логике, хотя фактически поддерживается трехзначная логика.