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

0

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

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

Эта глава имеет следующую структуру. За данным вступительным разделом находится раздел 24.2, содержащий краткий обзор по этой теме и небольшую  историческую справку. В разделах 24.3 и 24.4 приведена элементарная (и в значительной степени упрощенная) трактовка, соответственно, исчисления высказываний и исчисления предикатов. Затем  в  разделе  24.5  содержится  вводное  описание  так  называемого  доказательнотеоретического  представления  базы данных, а в разделе 24.6 на основе понятий, представленных в разделе 24.5, приведено описание того, что подразумевается под термином дедуктивная СУБД. После этого в разделе 24.7 обсуждаются некоторые подходы к решению проблемы рекурсивной обработки запросов. Наконец, в разделе 24.8 приведено резюме и дано несколько заключительных замечаний.

КРАТКИЙ ОБЗОР

Исследования связей между теорией баз данных и логикой начались еще в  конце 1970-х годов или даже раньше (см., например, [24.3], [24.4] и [24.8]). Но, по-видимому, самым важным стимулом к пробуждению в последнее время значительного интереса к этой теме стала публикация в 1984 году чрезвычайно  важной статьи Рейтера (Reiter) [24.10]. В этой статье Рейтер охарактеризовал традиционное восприятие систем баз данных как модельно-теоретическое. Под этим в его статье подразумевались приведенные ниже особенности (в неформальном изложении).

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

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

Примечание. Термин модельно-теоретический будет определен более точно в разделе 24.5.

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

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

1  Для согласования с другими работами в этой области, в настоящей главе автор использует термин домен, а не  более предпочтительный(сеготочкизрения)терминтип.

и кортежам в базовых отношениях, а также некоторых дедуктивных аксиом, которые рассматриваются ниже).

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

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

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

SPX  WHERE   SPX.QTY   >   250

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

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

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

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

■     Семантическое моделирование. Благодаря этому свойству создается прочная осно ва, на которой могут формироваться различные семантические дополнения к базо вой модели.

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

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

В этом подразделе приведено краткое и предварительное определение понятия дедуктивной аксиомы, которое уже несколько раз встречалось в настоящей главе. По сути, дедуктивная аксиома (называемая также правилом логического вывода) представляет собой правило, с помощью которого при наличии определенных  фактов можно осуществить дедуктивный логический вывод (называемый также просто логическим выводом) дополнительных фактов. Например, если известны факты "Анна — мать Бетти" и "Бетти — мать Селии", то существует очевидная  дедуктивная аксиома, позволяющая сделать логический вывод, что Анна — бабушка Селии. Поэтому, чтобы немного опередить ход нашего описания, мы можем представить себе дедуктивную СУБД, в которой два указанных факта представлены в виде кортежей отношения следующим образом.

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

IF MOTHER_OF ( X, у ) AND MOTHER_OF ( у, z ) THEN GRANDMOTHER_OF ( X, z ) END IF

Теперь система может применить правило, выраженное в виде дедуктивной аксиомы, к данным, представленным с помощью основных аксиом, тем способом, который будет  описан  в  разделе   24.4,  чтобы  дедуктивным   путем   получить  результат GRANDMOTHER_OF (Anne,Celia). Таким образом, пользователи могут задавать системе примерно такие вопросы: "Кто является бабушкой Селии?" или "Кто является внучкой Анны?" (или, более точно, "Чьей бабушкой является Анна?").

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

VAR GRANDMOTHER_OF VIEW

{ MX.MOTHER AS GRANDMOTHER, MY.DAUGHTER AS GRANDDAUGHTER } WHERE MX.DAUGHTER = MY.MOTHER ;

Здесь намеренно использован стиль реляционного исчисления; мх и MY — переменные области значений, принимающие свои значения в отношении MOTHER_OF. Запросы, подобные приведенным выше, теперь могут оформляться  в терминах указанного представления, следующим образом.

GX.GRANDMOTHER WHERE GX.GRANDDAUGHTER = NAME (‘Celia’) GX . GRANDDAUGHTER WHERE GX.GRANDMOTHER = NAME ( ‘ Anne ‘ )

Здесь GX — переменная области значений, принимающая свои значения в отношении

GRANDMOTHER_OF.

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

Источник: Дейт К. Дж., Введение в системы баз данных, 8-е издание.: Пер. с англ. — М.: Издательский дом «Вильямс», 2005. — 1328 с.: ил. — Парал. тит. англ.

По теме:

  • Комментарии