Глава

Логические системы управления базами данных

23.1. Введение

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

Назначение приведенного здесь материала- объяснить сущность логических баз данных читателям, знакомым с обычными базами данных, но не совсем знакомым с основами логики. Причем каждая новая логическая идея по возможности будет разъясняться с помощью традиционных терминов. Конечно, некоторые логические идеи уже были представлены в этой книге, в частности в главе 7 при обсуждении реляционного исчисления, которое непосредственно базируется на логике. Однако, как показано ниже, под логическими базами данных подразумевается нечто большее, чем просто одно из приложений реляционного исчисления.

Структура этой главы такова. После краткого введения следует раздел 23.2 с небольшим обзором обсуждаемой темы и основных предпосылок ее возникновения. Затем в разделах 23.3 и 23.4 приводится элементарное и весьма упрощенное описание исчисления высказываний (вычислений на основе логических утверждений) и исчисления предикатов. После этого в разделе 23.5 представлен так называемый доказательно-теоретический подход, а в разделе 23.6 описывается дедуктивная СУБД. Далее в разделе 23.7 рассматриваются некоторые подходы к проблеме выполнения рекурсивных запросов, и наконец в разделе 23.8 предлагаются резюме и несколько заключительных замечаний.

23.2. Обзор ОСНОВНЫХ концепций

Исследования связей между базами данных и логикой начались еще в конце 70-х годов, и о них можно прочесть в работах [23.5], [23.7] и [23.13]. Однако интерес к этой теме значительно возрос после публикации в 1984 году работы Рейтера (Reiter) [23.15]. В ней традиционное представление баз данных характеризуется как модельно-теорети-ческое. Проще говоря, это означает следующее.

1. База данных в любой момент может рассматриваться как набор явно заданных (т.е. базовых) отношений, каждое из которых включает набор явно заданных кортежей.

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

Замечание. Более точное определение термина модельно-теоретический будет дано в разделе 23.5.

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

1. База данных рассматривается как набор аксиом ( основных аксиом, соответствующих значениям домена и кортежам базовых отношений, а также определенных дедуктивных аксиом, которые более подробно описаны ниже).

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

Замечание. Более точное определение термина доказательно-теоретический будет дано в разделе 23.5, хотя можно сразу отметить, что доказательно-теоретическое представление очень близко к описанию базы данных как набора истинных высказываний, которое приводилось в разделе 1.3 главы 1 (см. также [1.2]).

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

SPX WHERE SPX.QTY > 250

(Здесь SPX - это, конечно, переменная кортежа, принимающая значения из отношения поставок.) В традиционной, т.е. модельно-теоретической, интерпретации необходимо последовательно проверить все кортежи с данными о поставках и оценить для каждого из них результат вычисления формулы QTY > 250. При выполнении этого запроса будут извлечены все кортежи с описанием поставок, для которых данное выражение будет истинным. В противоположность этому при доказательно-теоретической интерпретации кортежи с описанием поставок (а также некоторые дополнительные объекты) рассматриваются как аксиомы некой логической теории. Затем при обработке запроса применяется доказательно-теоретический метод с целью выяснения, для каких возможных значений переменной SPX формула SPX.QTY>250 является логическим следствием аксиом этой теории. Результатом выполнения запроса будут отдельные значения переменной-отношения SPX.

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

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

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

Семантическое моделирование. Появляется твердая основа для построения множества семантических расширений основной модели.

Расширенное применение. Наконец, обеспечивается основа для решения таких проблем, с которыми не могут справиться системы на основе классических подходов, например для работы с дизъюнктивной информацией наподобие Поставщик с номером S5 поставляет либо деталь с номером Р1, либо деталь с номером Р2, но какую именно, точно неизвестно .

Дедуктивные аксиомы

в этом подразделе объясняется уже упоминавшееся понятие дедуктивной аксиомы, которое также называется правилом вывода (или правилом заключения). По своей сути дедуктивная аксиома- это правило, следуя которому на основе определенных фактов можно вывести новые факты. Например, на основе фактов Anne is the mother of Betty ( Анна - мать Бетти ) и Betty is the mother of Celia ( Бетти - мать Селии ) согласно очевидной дедуктивной аксиоме можно вывести, что Anne is the grandmother of Celia ( Анна- бабушка Селии ). Забегая наперед, можно представить дедуктивную СУБД, в которой два данных факта оформлены в виде кортежей отношения MOTHER OF с атрибутами MOTHER (мать) и DAUGHTER (дочь).

MOTHER OF

Эти два факта будут основными аксиомами для системы. Предположим также, что дедуктивная аксиома формально определена в СУБД с использованием следующего гипотетического упрощенного синтаксиса.

IF MOTHER OF [ X, у )

AND MOTHER OF { У, Z )

THEN GRANDMOTHER OF { x, z ) ;

Теперь это правило, выраженное в форме дедуктивной аксиомы, можно применить к данным, выраженным в форме основных аксиом (конкретные способы такого применения будут обсуждаться в разделе 23.4). Это позволит получить результат GRANDMOTHER OF(Anne, Celia). Таким образом, пользователи СУБД смогут создавать запросы наподобие Кто является бабушкой Селии? и Кто является внучкой Анны? (точнее будет спросить Чьей бабушкой является Анна? ).