Главная » SQL, Базы данных » РЕКУРСИВНАЯ ОБРАБОТКА ЗАПРОСОВ

0

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

В качестве примера еще раз рассмотрим приведенное в разделе 24.6  рекурсивное определение предиката COMPONENT_OF в терминах отношения PART_STRUCTURE (но для  краткости  здесь  вместо  PART_STRUCTURE   применяется  имя  PS,  а  вместо COMPONENT_OF — имя СОМР). Соответствующее определение на языке Datalog выглядит следующим образом.

СОМР ( рх, ру ) ⇐  PS ( рх, ру )

СОМР ( рх, ру ) ⇐  PS ( рх, pz ) AND СОМР ( pz, ру )

Ниже приведен типичный рекурсивный запрос к этой базе данных ("Показать компоненты детали Р1").

?   ⇐  СОМР   (   Р1,   ру   )

Еще раз кратко рассмотрим указанное определение. В этом определении второе правило (т.е. рекурсивное правило) называется линейно рекурсивным,  поскольку предикат, находящийся в голове правила, появляется в теле правила только один раз. Ниже для  сравнения  приведено  такое  определение  предиката  СОМР,  в  котором  второе (рекурсивное) правило не является линейно рекурсивным в указанном выше смысле.

СОМР ( рх, ру ) ⇐  PS ( рх, ру )

СОМР ( рх, ру ) ⇐  СОМР ( рх, pz ) AND СОМР { pz, ру )

Но в целом в литературе чаще всего высказывается мнение о том, что линейная рекурсия представляет собой "наиболее интересный случай". Под этим  подразумевается, что основная часть рекурсивных алгоритмов, применяемых на практике, по своему характеру являются линейными. Кроме того, известны эффективные методы, предназначенные для использования именно в случае линейной рекурсии [24.11]. Поэтому до конца этого раздела ограничимся изучением линейной рекурсии.

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

Р   (   х,   у   )   ⇐  Q   (   х,    z   )   AND  R   (   z,   у   )

Q   (   х,   у   )   ⇐ Р   (   х,    z   )   AND  S    (   z,   у   )

Но для сокращения объема изложения здесь такие уточнения игнорируются. Более подробные сведения на эту тему приведены в [24.11].

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

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

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

алгоритмами, которые были описаны в данном разделе. Но объем книги такого характера, как эта, не позволяет привести весь методический материал, необходимый для полного понимания этих подходов. Дополнительные сведения по этой теме можно найти, например, в [24.11] — [24.25].

24.1. РЕЗЮМЕ

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

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

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

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

■     Доказательство — это процесс демонстрации того, что некоторая конкретная пра вильно построенная формула g (заключение) является логическим следствием из

■   некоторого конкретного множества правильно построенных формул fl,  f2,

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

унификацией.

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

Одним из непосредственно очевидных различий между языком Datalog и  классическими реляционными языками является то, что Datalog поддерживает рекурсивные аксиомы и поэтому — рекурсивные запросы, хотя нет никаких причин, по которым нельзя было бы расширить классическую реляционную  алгебру и исчисление для выполнения такой же задачи9  (см. описание оператора  TCLOSE в главе 7). В данной главе описаны некоторые простые методы выполнения таких запросов.

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

■     Рекурсивная обработка запросов. По поводу этого термина разногласия обычно не возникают. Рекурсивной обработкой запросов называется анализ и, в частности, оптимизация   запросов,   которые   по   определению   являются   рекурсивными (см. раздел 24.7).

■     База знаний. Этот термин иногда используется для обозначения того понятия, ко торое в разделе 24.6 было определено как интенсиональная база данных. Иными словами, база знаний состоит из правил (ограничений целостности и дедуктивных аксиомы), в отличие от собственно базы данных, которая составляет экстенсио нальную базу данных. Однако многие авторы используют термин база знаний для обозначения комбинации экстенсиональной и интенсиональной баз данных, если не считать того, что некоторые специалисты утверждают (как, например в [24.6]), что "база знаний часто содержит сложные объекты, [а также] классические от ношения" (описание сложных объектов приведено в части VI настоящей книги). Наконец, в системах обработки естественных языков этот термин имеет другое, более специализированное значение, поэтому, видимо, лучше вообще избегать его использования.

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

■     Знания. Еще один термин, практически не вызывающий разногласий! Знаниями называют то, что содержится в базе знаний… К сожалению, при использовании этой формулировки проблема определения понятия знания сводится к описанной выше нерешенной проблеме окончательного определения понятиябазя знаний.

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

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

■     Дедуктивная база данных (не рекомендуемый термин). База данных, управляемая дедуктивной СУБД.

■     Экспертная СУБД. Синоним дедуктивной СУБД.

■     Экспертная база данных (не рекомендуемый термин). База данных, управляемая экспертной СУБД.

■     СУБД, поддерживающая логический вывод. Синоним для дедуктивной СУБД.

■      Система, основанная на логике. Синоним для дедуктивной СУБД.

■     Логическая база данных (не рекомендуемый термин). Синоним для  дедуктивной базы данных.

■     Логика как модель данных. Любая модель данных состоит (по меньшей мере) из объектов, правил поддержки целостности и операторов. В дедуктивной СУБД все эти компоненты (объекты, правила поддержки  целостности и операторы) представлены в некоторой единообразной форме (а именно, как аксиомы в таком языке, основанном на логике, как Datalog); в действительности, как было описано в разделе 24.6, база данных в такой системе может рассматриваться именно как логическая программа, состоящая из аксиом этих трех типов. Поэтому вполне обоснованным является утверждение, что абстрактной моделью данных для такой системы служит сама логика.

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

По теме:

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