Query compilation under the disjunctive well-founded semantics

• Autorzy: Johnson C. A.
• Języki publikacji: EN

Abstrakty

EN

A top-down method is presented for compiling queries in unstratified propositional disjunctive deductive databases under the disjunctive well-founded semantics. Compilation entails the construction of a set of compilation trees, and the run-time processing of the compiled query then amounts to checking that some such tree can be extended within the extensional database to yield a tree that encapsulates a proof of the original query. Issues surrounding the extension of our techniques to the first order level are discussed.

Słowa kluczowe

EN

disjunctive deductive databases; disjunctive well-founded semantics; query compilation; top-down computation

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2004
• Tom: Vol. 62, nr 3,4
• Strony: 343--368
• Opis fizyczny: Bibliogr. 29 poz., rys.

Twórcy

autor

Johnson C. A.

• School of Computing, University of Plymouth, Devon, PL4 8AA, England,

Bibliografia

• [1] C. Aravindan, J. Dix and T. Niemela, DISLOP: A research project on disjunctive logic programming, AI communications, vol. 10(1997), 151-165.
• [2] C. Baral, J. Lobo and J. Minker, WF*3: A semantics for negation in normal disjunctive logic programs, in Z. Ras and M. Zemankova (eds.). Proceedings of the 6th International Symposium on Methodologies for Intelligent Systems, (Springer, 1991), 459-468.
• [3] C. Baral, J. Lobo and J. Minker, Generalised disjunctive well-founded semantics for logic programs. Annals of Mathematics and Artificial Intelligence, vol. 5 (1992). 89-132.
• [4] P. Baumgartner, Hyper-tableaux - The next generation. Technical Report 32/97, Institut für Informatik, Universität Koblenz-Landau (1997).
• [5] S Brass and J. Dix, A disjunctive semantics based upon unfolding and bottom-up evaluation, in : B Wolfinger, (ed.), Innovationen bei Rechen- und Kommunikationssystemen (IFIP- Congress, Workshop FG2: Disjunctive Logic Programming and Disjunctive Databases), (Springer, 1994), 83-91.
• [6] S. Brass and J. Dix, Disjunctive semantics based upon partial and bottom-up evaluation, in : L. Sterling (ed.), Proc. 12th Int'l Cont. on Logic Programming, Tokyo (MIT Press, 1995), 199-213.
• [7] S. Brass, J. Dix, 1. Niemela and T. C. Przymusinski, A comparison of the static and disjunctive well-founded semantics, in: A.G. Cohn, L.K. Schubert and S.C. Shapiro (eds.). Proceedings of the 6th International Conference on Principles of Knowledge Representation and Reasoning (Morgan Kaufmann, 1998), 74-85.
• [8] S. Brass and J. Dix, Characterisations of the disjunctive well-founded semantics: confluent calculi and iterated GCWA,J. Automated Reasoning, vol. 20(1998), 143-165.
• [9] S. Brass and J. Dix, Semantics of disjunctive logic programs based upon partial evaluation, J. Logic Programming, vol. 40(1999), 1-46.
• [10] J. Dix, Semantics of logic programs: Their intuitions and formal properties, in A. Fuhrman and H. Rott (eds.). Logic, Action and Information, Essays on Logic in Philosophy and Artificial Intelligence (DeGruyter, 1995), 241-327.
• [11] J. Dix, U. Furbach and L Niemelä, Nonmonotonic Reasoning: Towards Efficient Calculi and Implementations, in A. Robinson and A Voronkov (eds). Handbook of Automated Reasoning, vol. 2, (Elsevier Science, 2001), 1121-1234.
• [12] J. Fernandez, J. Minker and A. Yahya, Computing perfect and stable models using ordered model trees. Computational Intelligence, vol. 11 (1995), 89-112.
• [13] M. Gelfond and V. Lifschitz, The stable model semantics for logic programming, in: R. Kowalski and K. Bowen (eds.). Proc. 5th Int'l Conference on Logic Programming. Seattle (1988), 1070-1080.
• [14] M. Gelfond and V. Lifschitz. Classical negation in logic programs and disjunctive databases. New Generation Computing, vol. 9 (1991), 365-385,
• [15] J. Grant, J. Horty, J. Lobo and J. Minker, View updates in stratified disjunctive databases. J. Automated Reasoning, vol. 11 (1993), 249-267.
• [16] L. J. Henschen and H. Park, Compiling the GCWA in indefinite databases, in J. Minker, ed.. Foundations of Deductive Databases, (Morgan Kaufmann, 1988), 395-438.
• [17] T. Janhunen. I. Niemelä, D. Seipel, P. Simons and J.H. You, Unfolding partiality and disjunctions in stable model semantics, in: A.G. Cohn. F. Giunchiglia and B. Selman (eds.): Proceedings of the 7th International Conference on the Principles of Knowledge Representation and Reasoning, (Morgan Kaufmann. San Francisco, 2000),411-419.
• [18] C. A. Johnson. On computing minimal and perfect model membership. Data and Knowledge Engineering, vol. 18(1996), 225-276.
• [19] C. A. Johnson, Deduction trees and the view update problem in indefinite deductive databases, J, Automated Reasoning, vol. 19 (1997), 31-85,
• [20] C. A. Johnson, Top-down query processing in indefinite stratified databases, Data and Knowledge Engineering, vol. 26 (1998). 1-36.
• [21] C. A. Johnson, On cyclic covers and perfect models. Data and Knowledge Engineering, vol. 31 (1999), 25-65.
• [22] C. A. Johnson, Processing deductive databases under the disjunctive stable model semantics, Fundamenta Informaticae, vol, 40(1999), 31-51.
• [23] C, A, Johnson. On the computation of the disjunctive well-founded semantics, J. Automated Reasoning, vol, 26(2001),333-356.
• [24] C. A. Johnson, Top-down query processing in first order deductive databases under the DWFS, J. Automated Reasoning, vol. 32 (2004), 167-184.
• [25] C. A. Johnson, Computing only minimal answers. Technical report. www.tech.plym.acuk/soc/staff/chrisjohnsonyminimai/minimal.pdf (available June, 2004).
• [26] N. Leone, G. Pfeifer. W, Faber, T. Eiter, G. Gottlob, S. Perri, and F. Scarcello. The DLV System for Knowledge Representation and Reasoning, arxiv.org/abs/cs.AI/02l 1004 (available June 2004).
• [27] J. Lobo, J. Minker. and A, Rajasekar, Foundations of Disjunctive Logic Programming, (MIT Press. 1992),
• [28] T Przymusinski, Stable semantics for disjunctive programs. New Generation Computing, vol. 9 (1991), 401-424.
• [29] A. Yahya. Duality tor efficient query processing in disjunctive deductive databases, J. Automated Reasoning, vol. 28(2002), 1-34.