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

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

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

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

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

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

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

Инференциальная СУБД. Синоним дедуктивной СУБД.

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

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

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

Упражнения

23. L Используя метод резолюции, определите, являются ли приведенные ниже метаутверждения правильными доказательствами в исчислении высказываний.

а)Л=>Б, С= В, D={A OR С), D\-B

б) ( Л => В ) AND ( С => D ), ( В => 5 AND D => F ),

NOT ( г AND F ), Л => С 1- NOT Л

в) ( Л OR В ) => D, D = NOT ( г OR f ), NOT ( В AND С AND В )

- NOT ( G => NOT ( С AND Я ) ) 23.2. Преобразуйте следующие WFF-формулы в стандартную форму.

а) FORALL X ( FORALL у

( P ( X, У )

б) EXISTS X ( EXISTS у

( P ( X, у )

в) EXISTS X ( EXISTS у

( p ( X, у ) = EXISTS z ( g { X, z ) ) ) ) 23.3. Ниже приводится достаточно стандартный пример логической базы данных.

EXISTS z

FORALL z

X, z ) ) ) )

{ X, z ) ) ) )

WOMAN

PARENT PARENT PARENT PARENT PARENT

FATHER MOTHER

Adam ) Eve ) Cain ) Abel ) Enoch )

Adam, Cain ) Adam, Abel ) Eve, Cain ) Eve, Abel ) Cain, Enoch )

X, у ) PARENT ( X, у ) AND MAN ( X ) X, у ) PARENT ( X, у ) AND WOMAN ( X

SIBLING ( X, у ) PARENT ( Z, x ) AND PARENT ( Z, у ) BROTHER ( X, у ) SIBLING ( x, у ) AND MAN ( x ) SISTER ( X, у ) SIBLING ( x, у ) AND WOMAN ( X ) ANCESTOR ( X, у ) PARENT ( x, у )

ANCESTOR ( X, у ) PARENT ( x, z ) AND ANCESTOR ( z, у ) Используйте метод резолюции, чтобы ответить на следующие запросы.

а) Кто является матерью Каина ( Cain)?

б) Кто является братом или сестрой (Sibling) Каина?

в) Кто является братом (Brother) Каина?

г) Кто является сестрой (Sister) Каина?

д) Кто является наследником (Ancestor) Еноха (Enoch)?

23.4. Дайте определение терминам интерпретация и модель.

23.5. Напищите набор аксиом языка Datalog только для части определений базы данных поставщиков, деталей и проектов.

23.6. Запишите на языке Datalog решения для упр. 6.13-6.50, где это возможно.

23.7. Запишите на языке Datalog решения для упр. 8.1, где это возможно.

23.8. Завершите (ради собственного удовольствия) объяснение реализации метода унификации и резолюции, данное в разделе 23.7, для решения запроса Найти все компоненты детали с номером Р1 .

Список литературы

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

Книги [23.1]-[23.9] или посвящены логике в целом (отчасти в контексте вычислений, отчасти в контексте баз данных), или представляют собой сборники статей именно по логическим СУБД.

Работы [23.10]-[23.12] являются учебными пособиями, как и книги [23.46] и [23.47].

Работы [23.14], [23.17]-[23.20], [23.30], [23.49] и [23.50] посвящены операции транзитивного замыкания и ее реализации.

В работах [23.21]-[23.24] описана важная методика выполнения рекурсивных запросов - магические множества , а также различные ее варианты. Замечание. С этим вопросом также связаны публикации [17.24]-[ 17.26].

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

23.1. Stoll R.R. Sets, Logic and Axiomatic Theories. - San Francisco, Calif.: W.H. Freeman and Company, 1961.

Представляет собой весьма неплохое введение в логику.

23.2. Manna Z., Waldinger R. The Logical Basis for Computer Programming. Volume I. Deductive Reasoning (1985); Volume II. Deductive Techniques (1990).- Reading, Mass.: Addison-Wesley, 1985, 1990.

233. Gray P.M.D. Logic, Algebra and Databases. - Chichester, England: Ellis Horwood Ltd., 1984. Книга является прекрасным введением в исчисление высказываний и исчисление предикатов с точки зрения базы данных. В ней также освещены другие темы, имеющие непосредственное отношение к данной.

23.4. Walker А., McCord М., Sowa J.F., Wilson W.G. Knowledge Systems and Prolog (2nd ed.). - Reading, Mass.: Addison-Wesley, 1990.

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

23.5. Gallaire Н., Minker J. Logic and Data Bases. - New York, N.Y.: Plenum Publishing Соф., 1978.

Один из первых (если не самый первый) сборников статей по данной теме.

23.6. Kershberg L. (ed.). Expert Database Systems Proc. 1st Int. Workshop on Expert Database Systems (Kiawah Island, S.C). - Menlo Park, Calif: Benjamin/Cummings, 1986. Прекрасный сборник статей, располагающих к размышлениям. Однако не все они непосредственно связаны с темой данной главы. Даже названия разделов вносят некоторую путаницу в то, что же на самом деле относится к экспертным системам баз данных . Перечислим эти разделы.

1. Теория баз знаний.

2. Логическое профаммирование и базы данных.