ACM SIGMOD Anthology VLDB dblp.uni-trier.de

Computing Facts in Non-Horn Deductive Systems.

Eliezer L. Lozinskii: Computing Facts in Non-Horn Deductive Systems. VLDB 1988: 273-279
@inproceedings{DBLP:conf/vldb/Lozinskii88,
  author    = {Eliezer L. Lozinskii},
  editor    = {Fran\c{c}ois Bancilhon and
               David J. DeWitt},
  title     = {Computing Facts in Non-Horn Deductive Systems},
  booktitle = {Fourteenth International Conference on Very Large Data Bases,
               August 29 - September 1, 1988, Los Angeles, California, USA,
               Proceedings},
  publisher = {Morgan Kaufmann},
  year      = {1988},
  isbn      = {0-934613-75-3},
  pages     = {273-279},
  ee        = {db/conf/vldb/Lozinskii88.html},
  crossref  = {DBLP:conf/vldb/88},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

Let S be a set of clauses (non-Horn as well as Horn ones), and q an atomic query. Consider the problem of deriving from S all ground unit clauses satisfyingq , which we call computing all facts for q . It is shown how a non-Horn system S can be transformed into a set of singleton -head -rules , SH (S) , such that computing of all facts for a given query q in S is reduced to the query evaluation in a set of Horn clauses relevant to q which is a subset of SH(S). The transformation is sound and complete.

Copyright © 1988 by the VLDB Endowment. Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the VLDB copyright notice and the title of the publication and its date appear, and notice is given that copying is by the permission of the Very Large Data Base Endowment. To copy otherwise, or to republish, requires a fee and/or special permission from the Endowment.


Online Paper

ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 1 Issue 4, VLDB '75-'88" and ... DVD Version: Load ACM SIGMOD Anthology DVD 1" and ...

Printed Edition

François Bancilhon, David J. DeWitt (Eds.): Fourteenth International Conference on Very Large Data Bases, August 29 - September 1, 1988, Los Angeles, California, USA, Proceedings. Morgan Kaufmann 1988, ISBN 0-934613-75-3
CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

References

[1]
Krzysztof R. Apt, Howard A. Blair, Adrian Walker: Towards a Theory of Declarative Knowledge. Foundations of Deductive Databases and Logic Programming. 1988: 89-148 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[2]
François Bancilhon, David Maier, Yehoshua Sagiv, Jeffrey D. Ullman: Magic Sets and Other Strange Ways to Implement Logic Programs. PODS 1986: 1-15 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[3]
Catriel Beeri, Raghu Ramakrishnan: On the Power of Magic. PODS 1987: 269-284 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[4]
...
[5]
Keith L. Clark: Negation as Failure. Logic and Data Bases 1977: 293-322 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[6]
...
[7]
Hervé Gallaire, Jack Minker, Jean-Marie Nicolas: Logic and Databases: A Deductive Approach. ACM Comput. Surv. 16(2): 153-185(1984) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[8]
Georges Gardarin, Christophe de Maindreville: Evaluation of Database Recursive Logic Programs as Recurrent Function Series. SIGMOD Conference 1986: 177-186 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[9]
Lawrence J. Henschen, Shamim A. Naqvi: On compiling queries in recursive first-order databases. J. ACM 31(1): 47-85(1984) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[10]
Michael Kifer, Eliezer L. Lozinskii: Filtering Data Flow in Deductive Databases. ICDT 1986: 186-202 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[11]
Eliezer L. Lozinskii: Evaluating Queries in Deductive Databases by Generating. IJCAI 1985: 173-177 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[12]
John McCarthy: Circumscription - A Form of Non-Monotonic Reasoning. Artif. Intell. 13(1-2): 27-39(1980) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[13]
Jack Minker: On Indefinite Databases and the Closed World Assumption. CADE 1982: 292-308 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[14]
Jack Minker, Jean-Marie Nicolas: On recursive axioms in deductive databases. Inf. Syst. 8(1): 1-13(1983) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[15]
Raymond Reiter: On Closed World Data Bases. Logic and Data Bases 1977: 55-76 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[16]
Raymond Reiter: A Logic for Default Reasoning. Artif. Intell. 13(1-2): 81-132(1980) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[17]
Domenico Saccà, Carlo Zaniolo: On the Implementation of a Simple Class of Logic Queries for Databases. PODS 1986: 16-23 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[18]
Jeffrey D. Ullman: Implementation of Logical Query Languages for Databases. ACM Trans. Database Syst. 10(3): 289-321(1985) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[19]
Allen Van Gelder: A Message Passing Framework for Logical Query Evaluation. SIGMOD Conference 1986: 155-165 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[20]
Allen Van Gelder: Negation as Failure Using Tight Derivations for General Logic Programs. SLP 1986: 127-138 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[21]
Laurent Vieille: Recursive Axioms in Deductive Databases: The Query/Subquery Approach. Expert Database Conf. 1986: 253-267 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[22]
Adnan H. Yahya, Lawrence J. Henschen: Deduction in Non-Horn Databases. J. Autom. Reasoning 1(2): 141-160(1985) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

Copyright © Tue Mar 16 02:22:00 2010 by Michael Ley (ley@uni-trier.de)