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

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

Статическое фильтрование

Статическое фильтрование базируется на основной идее классической теории оптимизации - налагать ограничения на самых ранних этапах вычислений. Его можно рассматривать как приложение метода прямого формирования цепочки, поскольку в нем информация запроса (заключения) фактически используется для модификации правил (предпосылок). Иногда этот способ называется сокращением набора необходимых фактов, так как в нем информация запроса используется (вновь) для исключения ненужных кортежей из экстенсиональной базы данных непосредственно на выходе [23.29]. Эффективность этого способа мы продемонстрируем с помощью следующей процедуры на псевдокоде.

NEW := PS WHERE РХ = Р# ( Pl ) ;

СОМР := NEW ;

do until NEW is empty ;

/* Выполнять, пока отношение NEW не окажется пустым */

NEW := (NEW й PS) MINUS СОМР ;

СОМР := СОМР UNION NEW ; end ;

DISPLAY := СОМР ;

Далее приводится последовательное описание этого алгоритма. Перед началом выполнения цикла переменные-отнощения NEW и СОМР выглядят так, как показано ниже.

После первой итерации эти переменные-отношения примут следующий вид.

На следующей итерации переменная-отношение NEW окажется пустой и вьшолнение цикла завершится.

На этом заканчивается краткий обзор стратегий рекурсивного выполнения запросов. В опубликованной литературе можно найти множество более сложных подходов, однако их описание явно выходит за рамки этой книги, в которой преследуется совсем другая цель. Более детально изучить эти подходы и получить все необходимые для их понимания основные сведения можно, обратившись к [23.16]-[23.43].

23.8. Резюме

На этом завершается краткое введение в СУБД, основанные на логике. Хотя рассмотренные здесь идеи еше не получили широкого распространения в научном мире, некоторые из них уже нашли свою реализацию в коммерческих продуктах, в частности это относится к некоторым методам оптимизации. Определенные потенциальные преимущества этой сравнительно новой концепции, представляющей значительный интерес, описаны в различных разделах данной главы. Однако здесь не было упомянуто еще одно преимущество: логика может быть использована как основа для поистине полной интеграции между базами данных и языками программирования общего назначения. Другими словами, вместо не совсем элегантного подхода с применением внедряемого подъязыка данных (который используется во многих современных СУБД, поддерживающих язык SQL) этот подход предполагает наличие единого языка, основанного на логике. В таком случае данные являются данными независимо от того, хранятся ли они в совместно используемой базе данных или локально по отношению к некоторому приложению. (Конечно, на пути к этой цели потребуется преодолеть множество препятствий; и прежде всего весьма важно убедить специалистов в области информационных технологий в том, что логика может служить основой для создания языков программирования общего назначения.)

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

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

Модель для набора WFF-формул - это интерпретация, для которой все WFF-формулы в наборе истинны. В общем случае для данного набора WFF-формул может существовать любое количество моделей.

Доказательство- это демонстрация того, что данная WFF-формула д (заключение) является логическим следствием некоторого заданного набора WFF-формул fl, f2, fn (предпосылок). В качестве примера рассматривался один из методов доказательства под названием резолюция и унификация.

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

Одно соверщенно очевидное отличие языка Datalog от традиционных реляционных языков - возможность поддержки рекурсивных аксиом, а значит, и рекурсивных запросов. При этом не существует никаких принципиальных ограничений на расщирение соответствующим образом традиционной реляционной алгебры и исчисления (см. обсуждение оператора TCLOSE в главе 6). Также рассматривались некоторые простые методы выполнения таких запросов.

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

Рекурсивная обработка запросов Этот тип обработки предусматривает анализ и отчасти оптимизацию запросов, которые по определению являются рекурсивными

(см. раздел 23.7).

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

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