3. Архитектуры экспертных баз данных, инструменты и методы.

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

5. Доступ к интеллектуальным базам данных и взаимодействие с ними.

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

23.7. Minker J. (ed.). Foundations of Deductive Databases and Logic Programming. - San Mateo, Calif: Morgan Kaufmann, 1988.

23.8. Mylopoulos J., Brodie M.L. (eds). Readings in Artificial Intelligence and Databases. - San Mateo, Calif.: Morgan Kaufmann, 1988.

23.9. Ullman J.D. Database and Knowledge-Base Systems. В 2-х томах. - Rockville, Md: Computer Science Press, 1988, 1989.

Одна из десяти глав первого тома целиком посвящена логическим методам. В этой большой по объему главе (в которой впервые был представлен язык Datalog) обсуждается связь между логической и реляционной алгеброй, а также реляционное исчисление в виде особого случая логического подхода- версии как для доменов, так и для кортежей. Второй том состоит из семи глав, пять из которых посвящены различным аспектам логических СУБД. 23.10.Gardarin G., Valduriez P. Relational Databases and Knowledge Bases.- Reading, Mass.: Addison-Wesley, 1989.

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

23.11.Stonebraker М. Introduction to Integration of Knowledge and Data Management M. Stonebraker (ed.). Readings in Database Systems. - San Mateo, Calif: Morgan Kaufmann, 1988.

23.12.Gallaire H., Minker J., Nicolas J.-M. Logic and Databases: A Deductive Approach ACM Сотр. Surv. - June, 1984. - 16, № 2.

23.13.Dahl V. On Database Systems Development through Logic ACM TODS. - March, 1982. -7, № 1.

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

23.14.Agrawal R. Alpha: An Extension of Relational Algebra to Express a Class of Recursive Queries IEEE Transaction on Software Engineering. - July, 1988. - 14, № 7. Здесь предлагается новый оператор alpha, с помощью которого в рамках традиционной реляционной алгебры поддерживается формулировка большого класса рекурсивных запросов (в действительности - надмножество линейных рекурсивных запросов). Существует мнение, что оператор alpha является достаточно мощным для решения многих практических проблем, включая рекурсию, и более простым в применении по сравнению с другими общими механизмами рекурсии. В

книге приводится несколько примеров его использования. В частности, показано, как могут обрабатываться задачи транзитивного замыкания и обобщенных требований (см. соответственно публикацию [23.17] и раздел 23.6). Материал по этой теме содержится также в публикациях [23.18] и [23.19].

23.15.Reiter R. Towards а Logical Reconstruction of Relational Database Theory On Conceptual Modelling: Perspectives from Artificial Intelligence, Databases, and Programming Languages (eds. M.L. Brodie, J. Mylopoulos, J.W. Schmidt). - New York,N.Y.: Springer-Verlag, 1984.

Как уже отмечалось в разделе 23.2, хотя работа Рейтера и является первоисточником в этой области, многие исследователи до него изучали связь между логикой и базами данных (см., например, [23.5], [23.7] и [23.13]). Однако, по всей вероятности, именно логическая реконструкция реляционной теории значительно повысила интерес к предмету и побудила к активным исследованиям в этой области. 23.l6.Bancilhon Р., Ramakrishnan R. An Amateurs Introduction to Recursive Query Processing Strategies Proc. 1986 ACM SIGMOD Int. Conf on Management of Data. - Washington, D.C, 1986. (B переработанном виде опубликована в сборнике М. Stonebraker (ed.). Readings in Database Systems.- San Mateo, Calif: Morgan Kauftnann, 1988, a также в [23.8].)

Прекрасный обзор положительных и отрицательных сторон существующих методов рещения проблемы реализации рекурсивного запроса. Положительно оценивается наличие множества технологий, разработанных для рещения этой проблемы, а отрицательно - трудности выбора технологии, наиболее подходящей для конкретной ситуации (в частности, многие технологии представлены без описания характеристик производительности). После описания основных идей логических баз данных в статье предлагается множество алгоритмов - наивное и полунаивное оценивание, итерационные запросы и подзапросы, рекурсивные запросы и подзапросы, APEX, язык Prolog, алгоритмы Хеншена/Нэкви, Ахо-Ульмана, Кифера-Лозинского, вычислительный алгоритм, магические множества и их обобщение. Сравниваются различные подходы на основе домена приложения (т.е. класса проблем, для которых применяется данный алгоритм), производительности и простоты их реализации. В статье также приводятся показатели производительности (со сравнительным анализом), полученные в результате проверки различных алгоритмов на основе простого теста.

23.17.Ioannidis Y.E. On the Computation of the Transitive Closure of Relational Operators Proc. 12th Int. Conf on Very Large Data Bases. - Kyoto, Japan, August, 1986. Транзитивное замыкание является операцией фундаментального значения при обработке рекурсивного запроса [23.18]. В статье предлагается новый алгоритм реализации этой операции (основанный на подходе типа разделяй и властвуй ). Об этом также речь идет в работах [23.14], [23.18]-[23.20], [23.49], [23.50].

23.18.Jagadish H.V., Agrawal R., Ness L. A Study of Transitive Closure as a Recursion Mechanism Proc. 1987 ACM SIGMOD Int. Conf on Management of Data. - San Francisco, Calif, May, 1987.

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

реляционной алгебре . В статье также делается предположение, что для эффективной реализации линейной рекурсии в общем случае, а значит, и для создания эффективных дедуктивных СУБД для большого класса рекурсивных проблем достаточно обеспечить эффективную реализацию транзитивного замыкания. 23.19.Agrawal R., Jagadish Н. Direct Algorithms for Computing the Transitive Closure of Database Relations Proc 13th Int. Conf on Very Large Data Bases. - Brighton, UK, September, 1987.

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

23.20.Lu И. New Strategies for Computing the Transitive Closure of a Database Relation Proc 13th Int. Conf. on Very Large Data Bases. - Brighton, UK, September, 1987. Приводится описание других алгоритмов транзитивного замыкания. Так же, как и в [23.19], в этой статье содержится полезный обзор разработанных ранее подходов к рассматриваемой проблеме.

23.21.Bancilhon F., Maier D., Sagiv Y., Ullman J.D. Magic Sets and Other Strange Ways to Implement Logic Programs Proc. 5th ACM SIGMOD-SIGFACT Symposium on Principles of Database Systems, 1986.

Основная идея магических множеств заключается в динамическом введении нового набора магических правил, которые гарантируют получение того же результата, что и оригинальный запрос, но гораздо эффективнее за счет сокращения числа необходимых фактов (см. раздел 23.7). Изложение подробностей несколько сложно для восприятия и выходит за рамки данного комментария. Читателю предлагается прочесть эту статью или обратиться к работам [23.9], [23.10], [23.16], чтобы получить более подробные сведения. Однако следует отметить, что существуют также многочисленные варианты этой основной идеи [23.22]-[23.24]. Кроме того, следует учесть работы [17.24]-[ 17.26], указанные в главе 17. 23.22.Beeri С, Ramakrishnan R. On the Power of Magic Proc. 6th ACM SIGMOD-SIGFACT Symposium on Principles of Database Systems, 1987.

23.23. Sacca D., Zaniolo C. Magic Counting Methods Proc. 1987 ACM SIGMOD Int. Conf on Management of Data. - San Francisco, Calif., May, 1987.

23.24. Gardarin G. Magic Functions: A Technique to Optimize Extended Datalog Recursive Programs Proc. 13th Int. Conf on Very Large Data Bases. - Brighton, UK, September, 1987.

23.25.Aho A., Ullman J.D. Universality of Data Retrieval Languages Proc. 6th ACM Symposium on Principles of Programming Languages. - San Antonio, Texas, 1979. Для данной последовательности отношений R, f(R), f{f{R)),... (где f- некоторая фиксированная функция) крайней точкой неизменности называется отношение R*, выведенное в соответствии со следующим алгоритмом наивного оценивания (см. раздел 23.7).

R* := R ;

do until R* stops growing ;

/* выполнять, пока R* не достигнет точки неизменности */

R* := R* UNION f(R*) ; end :