ACM SIGMOD Anthology ACM SIGMOD dblp.uni-trier.de

Data Functions, Datalog and Negation (Extended Abstract).

Serge Abiteboul, Richard Hull: Data Functions, Datalog and Negation (Extended Abstract). SIGMOD Conference 1988: 143-153
@inproceedings{DBLP:conf/sigmod/AbiteboulH88,
  author    = {Serge Abiteboul and
               Richard Hull},
  editor    = {Haran Boral and
               Per-{\AA}ke Larson},
  title     = {Data Functions, Datalog and Negation (Extended Abstract)},
  booktitle = {Proceedings of the 1988 ACM SIGMOD International Conference on
               Management of Data, Chicago, Illinois, June 1-3, 1988},
  publisher = {ACM Press},
  year      = {1988},
  pages     = {143-153},
  ee        = {http://doi.acm.org/10.1145/50202.50218, db/conf/sigmod/AbiteboulH88.html},
  crossref  = {DBLP:conf/sigmod/88},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

Datalog is extended to incoporate single-valued "data functions", which correspond to attributes in semantic models, and which may be base (user-specified) or delived (computed). Both conventional and stratified datalog are considered. Under the extension, a datalog program may not be consistent, because a derived function symbol may evaluate to something which is not a function. Consistency is shown to be undecidable, and is decidable in a number of restricted cases. A syntactic restriction, pairwise consistency, is shown to guarantee consistency. The framework developed here can also be used to incorporate single-valued data functions into the Complex Object Language (COL), which supports deductive capabilities, complex database objects, and set-valued data functions.

There is a natural correspondence between the extended datalog introduced here, and the usual datalog with functional dependencies. For families Phi and Gamma of dependencies and a family of datalog programs Lambda, the Phi-Gamma implication problem for Lambda asks, given sets F <= Phi and G <= Gamma and a program P in Lambda, whether for all inputs I, I |= F implies P(I) |= G. The FD-FD implication problem is undecidable for datalog, and the TGD-EGD implication problem is decidable for stratified datalog. Also, the Ø-MVD problem is undecidable (and hence also the MVD-preservation problem).

Copyright © 1988 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.


ACM SIGMOD Anthology

Online Version (ACM WWW Account required): Full Text in PDF Format

CDROM Version: Load the CDROM "Volume 1 Issue 2, SIGMOD '75-'92" and ...

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

Printed Edition

Haran Boral, Per-Åke Larson (Eds.): Proceedings of the 1988 ACM SIGMOD International Conference on Management of Data, Chicago, Illinois, June 1-3, 1988. ACM Press 1988 BibTeX , SIGMOD Record 17(2), June 1988
Contents

Online Edition: ACM Digital Library


References

[AG]
Serge Abiteboul, Stéphane Grumbach: COL: A Logic-Based Language for Complex Objects. DBPL 1987: 347-374 BibTeX
[AGr]
Serge Abiteboul, Gösta Grahne: Update Semantics for Incomplete Databases. VLDB 1985: 1-12 BibTeX
[AKGr]
Serge Abiteboul, Paris C. Kanellakis, Gösta Grahne: On the Representation and Querying of Sets of Possible Worlds. SIGMOD Conference 1987: 34-48 BibTeX
[AH1]
Serge Abiteboul, Richard Hull: IFO: A Formal Semantic Database Model. ACM Trans. Database Syst. 12(4): 525-565(1987) BibTeX
[AH2]
...
[AH3]
...
[AV]
Serge Abiteboul, Victor Vianu: Equivalence and optimization of relational transactions. J. ACM 35(1): 70-120(1988) BibTeX
[ABW]
...
[BK]
François Bancilhon, Setrag Khoshafian: A Calculus for Complex Objects. PODS 1986: 53-60 BibTeX
[Be+]
Catriel Beeri, Shamim A. Naqvi, Raghu Ramakrishnan, Oded Shmueli, Shalom Tsur: Sets and Negation in a Logic Database Language (LDL1). PODS 1987: 21-37 BibTeX
[BV]
Catriel Beeri, Moshe Y. Vardi: Formal Systems for Tuple and Equality Generating Dependencies. SIAM J. Comput. 13(1): 76-98(1984) BibTeX
[BH]
Nicole Bidoit, Richard Hull: Minimalism, Justification and Non-Monotonicity in Deductive Databases. J. Comput. Syst. Sci. 38(2): 290-325(1989) BibTeX
[BFN]
Peter Buneman, Robert E. Frankel, Rishiyur S. Nikhil: An Implementation Technique for Database Query Languages. ACM Trans. Database Syst. 7(2): 164-186(1982) BibTeX
[CFP]
Marco A. Casanova, Ronald Fagin, Christos H. Papadimitriou: Inclusion Dependencies and Their Interaction with Functional Dependencies. J. Comput. Syst. Sci. 28(1): 29-59(1984) BibTeX
[DL]
...
[GJ]
M. R. Garey, David S. Johnson: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman 1979, ISBN 0-7167-1044-7
BibTeX
[G]
Allen Van Gelder: Negation as Failure Using Tight Derivations for General Logic Programs. SLP 1986: 127-138 BibTeX
[Gr]
Gösta Grahne: Dependency Satisfaction in Databases with Incomplete Information. VLDB 1984: 37-45 BibTeX
[HM]
Michael Hammer, Dennis McLeod: Database Description with SDM: A Semantic Database Model. ACM Trans. Database Syst. 6(3): 351-386(1981) BibTeX
[H]
...
[HK]
Richard Hull, Roger King: Semantic Database Modeling: Survey, Applications, and Research Issues. ACM Comput. Surv. 19(3): 201-260(1987) BibTeX
[IL]
Tomasz Imielinski, Witold Lipski Jr.: Incomplete Information in Relational Databases. J. ACM 31(4): 761-791(1984) BibTeX
[KP]
...
[K]
Gabriel M. Kuper: Logic Programming With Sets. PODS 1987: 11-20 BibTeX
[L]
John W. Lloyd: Foundations of Logic Programming, 1st Edition. Springer 1984, ISBN 3-540-13299-6
BibTeX
[MMS]
David Maier, Alberto O. Mendelzon, Yehoshua Sagiv: Testing Implications of Data Dependencies. ACM Trans. Database Syst. 4(4): 455-469(1979) BibTeX
[N]
...
[Sa]
Yehoshua Sagiv: Optimizing Datalog Programs. PODS 1987: 349-362 BibTeX
[Sc]
Oded Shmueli: Decidability and Expressiveness of Logic Queries. PODS 1987: 237-249 BibTeX
[Sh]
David W. Shipman: The Functional Data Model and the Data Language DAPLEX. ACM Trans. Database Syst. 6(1): 140-173(1981) BibTeX
[TZ]
Shalom Tsur, Carlo Zaniolo: LDL: A Logic-Based Data Language. VLDB 1986: 33-41 BibTeX
[U]
Jeffrey D. Ullman: Principles of Database Systems, 2nd Edition. Computer Science Press 1982, ISBN 0-914894-36-6
BibTeX

Referenced by

  1. Zoé Lacroix, Claude Delobel, Philippe Brèche: Object Views and Database Restructuring. DBPL 1997: 180-201
  2. Serge Abiteboul, Richard Hull, Victor Vianu: Foundations of Databases. Addison-Wesley 1995, ISBN 0-201-53771-0
    Contents
  3. Ke Wang, Li-Yan Yuan: First-Order Logic Characterization of Program Properties. IEEE Trans. Knowl. Data Eng. 6(4): 518-533(1994)
  4. Marc Gyssens, Jan Paredaens, Jan Van den Bussche, Dirk Van Gucht: A Graph-Oriented Object Database Model. IEEE Trans. Knowl. Data Eng. 6(4): 572-586(1994)
  5. Xian Ye, Christine Parent, Stefano Spaccapietra: Cardinality Consistency of Derived Objects in DOOD Systems. ER 1994: 278-295
  6. Serge Abiteboul, Georg Lausen, Heinz Uphoff, Emmanuel Waller: Methods and Rules. SIGMOD Conference 1993: 32-41
  7. Alon Y. Levy, Inderpal Singh Mumick, Yehoshua Sagiv, Oded Shmueli: Equivalence, Query-Reachability, and Satisfiability in Datalog Extensions. PODS 1993: 109-122
  8. Kenneth A. Ross, Yehoshua Sagiv: Monotonic Aggregation in Deductive Databases. PODS 1992: 114-126
  9. Serge Abiteboul, Stéphane Grumbach: A Rule-Based Language with Functions and Sets. ACM Trans. Database Syst. 16(1): 1-30(1991)
  10. Laks V. S. Lakshmanan, Héctor J. Hernández: Structural Query Optimization - A uniform Framework for Semantic Query Optimization in Deductive Databases. PODS 1991: 102-114
  11. Ke Wang, Li-Yan Yuan: First-Order Logic Reducible Programs. ICDE 1991: 746-755
  12. Andreas Heuer, Peter Sander: Preserving and Generating Objects in the LIVING IN A LATTICE Rule Language. ICDE 1991: 562-569
  13. Richard Hull, Masatoshi Yoshikawa: ILOG: Declarative Creation and Manipulation of Object Identifiers. VLDB 1990: 455-468
  14. Serge Abiteboul, Eric Simon, Victor Vianu: Non-Deterministic Languages to Express Deterministic Transformations. PODS 1990: 218-229
  15. Stefano Ceri, Georg Gottlob, Letizia Tanca: What you Always Wanted to Know About Datalog (And Never Dared to Ask). IEEE Trans. Knowl. Data Eng. 1(1): 146-166(1989)
  16. Serge Abiteboul, Paris C. Kanellakis: Object Identity as a Query Language Primitive. SIGMOD Conference 1989: 159-173
  17. Yehoshua Sagiv, Moshe Y. Vardi: Safety of Datalog Queries over Infinite Databases. PODS 1989: 160-171
  18. Erik Lambrichts, Peter Nees, Jan Paredaens, Peter Peelman, Letizia Tanca: Integration of Functions in the Fixpoint Semantics of Rule-Based Systems. MFDBS 1989: 301-316
  19. Serge Abiteboul, Stéphane Grumbach, Agnès Voisard, Emmanuel Waller: An Extensible Rule-Based Language with Complex Objects and data-Functions. DBPL 1989: 298-314
BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Sat May 16 23:39:53 2009