Magic sets revisited. (English) Zbl 0881.68044
Summary: This paper distinguishes among three kinds of linear recursions: canonical strongly linear recursion (CSLR), non-interdependent linear recursion (NILR) and interdependent linear recursion (ILR) and presents an optimal algorithm for each. First, for the CSLRs, the magic-set method is refined in such a way that queries can be evaluated efficiently. Then, for the NILRs and ILRs, the concept of query dependency graphs is introduced to partition the rules of a program into a set of CSLRs and the computation is elaborated so that the oplimization for CSLRs can also be applied.
MSC:
| 68P15 | Database theory |
Software:
DatalogReferences:
| [1] | Bancilhon F, Ramakrishnan R. An Amateur’s introduction to recursive query processing strategies. InProc. 1986 ACM-SIGMOD Conf. on Management of Data, Washington, D.C., May 1986, pp.16–52. |
| [2] | Han J, Zeng K, Lu T. Normalization of linear recursion in deductive databases. InProc. of the 9th Int’l Conf. on Data Engineering, Vienna, Austria, April 1993, pp.559–567. |
| [3] | Han J, Chen S. Graphic representation of linear recursive rules.International Journal of Intelligence System, 1992, 7: 317–337. · Zbl 0761.68032 · doi:10.1002/int.4550070403 |
| [4] | Henschen L J, Naqvi S. On compiling queries in recursive first-order database.J. ACM, 1984, 31(1): 47–85. · Zbl 0629.68095 · doi:10.1145/2422.2423 |
| [5] | Ioannidis Y, Wong E. Towards an algebraic theory of recursion.Journal of the Association for Coinpuling Machinery, 1991, 38(2): 329–381. · Zbl 0799.68062 |
| [6] | Knuth D E. The Art of Computer Programming. Addison-Wesley Series in Computer Science and Information Processing, 1968, pp.257–265. · Zbl 0191.17903 |
| [7] | Nejdl W. Recursive strategies for answering recursive queries–The RQA/FQI strategy. InProc. 13th VLDB Conf., Brighton, 1987, pp.43–50. |
| [8] | Marchetti-Spaccamela A, Pelaggi A, Sacca D. Worst case complexity analysis of methods for logic query implementation. InProc. ACM-PODS 87, · Zbl 0635.68030 |
| [9] | Chang C. On the Evaluation of Queries Containing Derived Relations in Relational Database. Advances in Data Base Theory, Vol.1, Plenum, 1981. |
| [10] | Chen Y, Härder T. Improving RQA/FQI recursive query algorithm. InProc. ISMM-First Int’l Conf. on Information and Knowledge Management, Baltimore, Maryland, Nov. 1992. |
| [11] | Chen Y. A bottom-up query evaluation method for stratified databases. In Proc. 9th Int’l Conf. on Data Engineering, Vienna, Austria, April 1993, pp.568–575. |
| [12] | Chen Y, Härder T. On the optimal top-down evaluation of recursive queries. InProc. of 5th Int’l Conf. on Database and Expert Systems Applications, Athens, Greece, Sept. 1994, pp.47–56. |
| [13] | Chen Y, Härder T. An optimal graph traversal algorithm for evaluating linear binary-chain programs. InProc. CIKM’94–The 3th Int’l Conf. on Information and Knowledge Management, Gaithersburg, Maryland, Nov. 1994, pp.34–41. |
| [14] | Chen Y, Härder T. Graph traversal and linear binary-chain programs. ZRI-Report 4/94, University of Kaiserslautem, 1994. |
| [15] | Chen Y. Processing of recursive rules in knowledge-based systems–Algorithms for handling recursive rules and negative information and performance measurements. Ph.D. Thesis, Computer Science Department, University of Kaiserslautem, Germany, Feb. 1995. |
| [16] | Sacca D, Zaniolo C. Implementation of recursire queries for a data language based on pure Horn logic. InProc. the 4th Int’l Conf. on Logic Programming, Univ. of Melbourne, 1987, pp.104–135. |
| [17] | Bancilhon F. Naive Evaluation of Recursively Defined Relations. On Knowledge Base Management Systems-Integrating Database and AI Systems. Springer-Verlag, 1985. |
| [18] | BancilhonF, Maier D, Sagiv Y, Ullman J D. Magic sets and other strange ways to implement logic programs. InProc. 5th ACM Symp. Principles of Database Systems, Cambridge, MA, March 1986, pp.1–15. |
| [19] | Beeri C, Ramakrishnan R. On the power of magic.J. Logic Programming, 1991, 10: 255–299. · Zbl 0722.68018 · doi:10.1016/0743-1066(91)90038-Q |
| [20] | Ullman J D. Implementation of logical query languages for databases.ACM Trans. Database Systems, 1985, 10(3). · Zbl 0573.68060 |
| [21] | Aly H, Ozsoyoglu Z M. Synchronized Counting Method. InProc. the 5th Int’l Conf. on Data Engineering, Los Angeles, 1989. |
| [22] | Sacca D, Zaniolo C. On the implementation of a simple class of logic queries for databases. InProc. the 5th ACM SIGMOD-SIGACT Symp. on Principles of Database Systems, 1986, pp.16–23. |
| [23] | Shapiro S, McKay. Inference with recursive rules. InProc. of the 1st Annual National Conference on Artificial Intelligence, 1980. |
| [24] | Marchetti-Spaccamela A, Pelaggi A, Sacca D. Comparison of methods for logic-query implementation.J. Logic Programming, 1991, 10: 333–360. · Zbl 0722.68021 · doi:10.1016/0743-1066(91)90040-V |
| [25] | Haddad R W, naughton J F. Counting method for cyclic relations. InProc. the 7th ACM SIGMOD-SIGACT Symp. on Principles of Database Systems, 1986, pp.16–23. |
| [26] | Han J, Henschen L J. The level-cycle merging method. InProc. of the 1st Int’l Conf. on Deductive and Object-Oriented Databases, Kyoto, 1989. |
| [27] | Vieille L. From QSQ to QoSaQ: Global optimization of recursive queries. InProc. 2nd Int’l Conf. on Expert Database System, Kerschberg L (ed.), Charleston, 1988. |
| [28] | Ceri S, Gottlob G, Tanca L. Logic Programming and Databases. Springer-Verlag, Berlin, 1990. |
| [29] | Balbin G S, Port K R, Meenakshi. Efficient bottom-up computation of queries on stratified databases.J. Logic Programming, 1991, 10: 295–344. · Zbl 0764.68012 · doi:10.1016/0743-1066(91)90030-S |
| [30] | Bancilhon F, Ramakrishnan R. Performance evaluation of data intensive logic programs. InPreprints of Workhop on Foundations of Deductive Databases and Logic Programming, August 1986. |
| [31] | Tarjan R. Depth-first search and linear graph algorithms.SIAM J. Compt., 1972, 1(2). · Zbl 0251.05107 |
| [32] | Wu C, Henschen L J. Answering linear recursive queries in cyclic databases. InProc. the 1988 Int’l Conf. on Fifth Gen. Computer Systems, Tokyo, 1988. |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
