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

Download PDF file (www.vldb.org, Darmstadt, Germany)
Download PDF file (www.acm.org, New York, USA)

ACM SIGMOD Anthology

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

Windows: Click the letter of your CD drive
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Mac: Click here
UNIX/LINUX: mount the CD and click on the path of your mount point:
/Anthology/vldb7588 or /cdrom

DVD Version: Load ACM SIGMOD Anthology DVD 1" and ...

Windows: Click the letter of your CD drive
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Mac: Click here
UNIX/LINUX: mount the DVD and click on the path of your mount point:
/Anthology/aDVD1 or /dvd

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

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