в этой статье описывается дополнение реляционной алгебры понятием крайняя точка неизменности .

23.26.Ullman J.D. Implementation of Logical Query Languages for Databases ACM TODS. - September, 1985. - 10, JVg 3.

Описывается важный класс технологий реализации возможных рекурсивных запросов. Методы определены в терминах правил сбора на деревьях правил/целей , которые являются фафами, представляющими некоторую стратегию запроса в терминах предложений и предикатов. В статье определено несколько таких правил: одно из них соответствует приложению операторов реляционной алгебры, два больиле соответствуют прямому формированию цепочки, а косвенное правило позволяет передавать результаты от одной подцели к другой. Косвенная передача информации затем становится основой для так называемых методов магических множеств [23.21]-[23.24]. 23.27.Tsur S., Zaniolo С. LDL: А Logic-Based Data-Language Proc. 12th Int. Conf on Very Large Data Bases. - Kyoto, Japan, August, 1986.

Язык LDL включает генератор типа множества , отрицание (основанное на различиях множеств), операции определения данных и операции обновления. Это язык логического типа (нет никаких зависимостей упорядочения между утверждениями), причем компилируемый, а не интерпретируемый. Материал по этой теме можно также найти в [23.45]. 23.28.Bancilhon F. Naive Evaluation of Recursive Defined Relations M. Brodie and J. Mylopoulos (eds): On Knowledge Base Management Systems: Integrating Database and AI Systems. - New York, N.Y.: Springer-Verlag, 1986.

23.29.Lozinskii E.L. A Problem-Oriented Inferential Database System ACM TODS.- September, 1986. - 11, JS o 3.

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

23.30. Rosenthal А. et al. Traversal Recursion: A Practical Approach to Supporting Recursive

Applications Proc. 1986 ACM SIGMOD Int. Conf on Management of Data.-

Washington, D.C, June, 1986. 23.31.Gardarin G., De Maindreville С Evaluation of Database Recursive Logic Programs as

Recurrent Function Series Proc. 1986 ACM SIGMOD Int. Conf on Management of

Data. - Washington, D.C, June, 1986. 23.32.Raschid L., Su S.Y.W. A Parallel Processing Strategy for Evaluating Recursive Queries

Proc. 12th Int. Conf on Very Large Data Bases. - Kyoto, Japan, August, 1986.

23.33.Spyratos N. The Partition Model: A Deductive Database Model ACM TODS. - March, 1987. - 12, JSo 1.

23.34.Han J., Henschen L.J. Handling Redundancy in the Processing of Recursive Queries Proc. 1987 ACM SIGMOD Intem. Conf on Management of Data. - San Francisco, Calif, May, 1987.

23.35.Zhang W., Yu CT. A Necessary Condition for a Double Recursive Rule to be Equivalent to a Linear Recursive Rule Proc. 1987 ACM SIGMOD Intern. Conf on Management of Data. - San Francisco, Calif, May, 1987.

23.36.Nejdl W. Recursive Strategies for Answering Recursive Queries - The RQA/FQI Strategy Proc. 13th Intern. Conf on Very Large Data Bases. - Brighton, UK, September, 1987.

23.37.Whang K.-Y., Navathe S.B. An Extended Disjunctive Normal Form Approach for Optimizing Recursive Logic Queries in Loosely Coupled Environments Proc. 13th Intern. Conf on Very Large Data Bases. - Brighton, UK, September, 1987.

23.38.Naughton J.F. Compiling Separable Recursions Proc. 1988 ACM SIGMOD Int. Conf

on Management of Data. - Chicago, 111., June, 1988. 23.39.Youn C, Henschen L.J., Han J. Classification of Recursive Formulas in Deductive

Databases Proc. 1988 ACM SIGMOD Int. Conf on Management of Data. - Chicago,

111., June, 1988.

23.40. Ceri S., Gottlob G., Lavazza L. Translation and Optimization of Logic Queries: The Algebraic Approach Proc. 12th Int. Conf on Very Large Data Bases. - Kyoto, Japan, August, 1986.

23.41.Ceri S., Tanca L. Optimization of Systems of Algebraic Equations for Evaluating Datalog Queries Proc. 13th Int. Conf. on Very Large Data Bases. - Brighton, UK, September, 1987.

23.42. Van Gelder A. A Message Passing Framework for Logical Query Evaluation Proc. 1986

ACM SIGMOD Int. Conf on Management of Data. - Washington, D.C., June, 1986. 23.43.Wolfson O., Silberschatz A. Distributed Processing of Logic Programs Proc. 1988

ACM SIGMOD Int. Conf on Management of Data. - Chicago, 111., June, 1988. 23.44.Naughton J.F. et al. Efficient Evaluation of Right-, Left-, and Multi-Linear Rules Proc.

1989 ACM SIGMOD Int. Conf on Management of Data. - Portland, Ore., June, 1989. 23.45.Naqvi S., Tsur S. A Logical Language for Data and Knowledge Bases. - New York.,

N.Y.: Computer Science Press, 1989.

Эта книга полностью посвящена языку LDL [23.27]. 23.46.Ceri S., Gottlob G., Tanca L. Logic Programming and Databases. - New York, N.Y.:

Springer-Verlag, 1990.

23.47.Das S.K. Deductive Databases and Logic Programming. - Reading, Mass.: Addison-Wesley, 1992.

23.48.Kifer M., Lozinskii E. On Compile-Time Query Optimization in Deductive Databases by Means of Static Filtering ACM TODS. - September, 1990. - 15, JS o 3.

23.49.Agrawal R., Dar S and Jagadish H.V. Direct Transitive Closure Algorithms: Design and Performance Evaluation ACM TODS. - September, 1990. - 15, JS o 3.

23.50.Jagadish H.V. A Compression Method to Materialize Transitive Closure ACM TODS. - December, 1990. - 15, JS o 4.

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

23.51.Abiteboul S., Grumbach S. А Rule-Based Language with Functions and Sets ACM TODS. - March, 1991. - 16, JS2 1.

, Описывается язык сложных объектов ( complex object language - COL), который является расширением языка Datalog с интеграцией идеи дедуктивных и объектно-ориентированных баз данных.

Ответы к некоторым упражнениям

23.1. а - правильное, б- правильное, б- неправильное.

23.2. В приведенных ниже выражениях а, Ь и с являются константами Сколема, а f - функцией Сколема.

а) Р ( , У ) => g ( , -f ( , У ) )

б) р ( а, Ь ) => g ( а, Z )

в) р ( а, Ь ) => g ( а, с )

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

23.6.13. ? <f= J ( j, jn, jc )

23.6.14. ? <f= J ( j, jn, London )

23.6.15. RES ( s ) <= SPJ ( s, p, Jl ) ? <f= RES ( s )

23.6.16. ? <f= SPJ ( s, p, j, q ) AND 300 < g AND g < 750

23.6.17. RES ( pi, pc )<= P ( p, рл, pi, w, pc ) ? RES ( pi, pc )

23.6.18. RES ( s, p, j ) <= S ( s, sn, st, с ) AND

( Pi PJi pli с ) AND J ( j, ;л, с ) ? <= RES ( s, p, j ) 23.6.19-23.6.20. He может быть выполнено без операции отрицания.

23.6.21. RES ( р ) <= SPJ ( S, р, j, q ) AND

S ( s, sn, St, London ) ? <= RES ( p )

23.6.22. RES ( p ) <= SPJ ( s, p, j, g ) AND

S ( s, sn, St, London ) AND J ( j, jn, London )

? <= RES ( p )

23.6.23. RES ( ci, c2 )<= SPJ ( s, p, j, g ) AND

S ( s, sn, St, cl ) AND

J ( j, jn, c2 ) ?<= RES ( ci, c2 )

23.6.24. RES ( p ) <= SPJ ( s, p, j, g ) AND

S ( s, sn, st, с ) AND J ( j, jn, с )

? <= RES ( p )

23.6.25. He может быть выполнено без операции отрицания.

23.6.26. RES ( pi, р2 )<= SPJ ( S, pi, ji, gi ) AND

S ( s, p2, j2, q2 ) ? <= RES ( pi, p2 )