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

Safety of Recursive Horn Clauses With Infinite Relations.

Raghu Ramakrishnan, François Bancilhon, Abraham Silberschatz: Safety of Recursive Horn Clauses With Infinite Relations. PODS 1987: 328-339
@inproceedings{DBLP:conf/pods/RamakrishnanBS87,
  author    = {Raghu Ramakrishnan and
               Fran\c{c}ois Bancilhon and
               Abraham Silberschatz},
  title     = {Safety of Recursive Horn Clauses With Infinite Relations},
  booktitle = {Proceedings of the Sixth ACM SIGACT-SIGMOD-SIGART Symposium on
               Principles of Database Systems, March 23-25, 1987, San Diego,
               California},
  publisher = {ACM},
  year      = {1987},
  isbn      = {0-89791-223-3},
  pages     = {328-339},
  ee        = {http://doi.acm.org/10.1145/28659.28694, db/conf/pods/RamakrishnanBS87.html},
  crossref  = {DBLP:conf/pods/87},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

A database query is said to be safe if its result consists of a finite set of tuples. If a query is expressed using a set of pure Horn Clauses, the problem of determining whether it is safe is in general undecidable. In this paper, we show that the problem is decidable when terms involving function symbols (including arithmetic) are represented as distinct occurrences of uninterpreted infinite predicates over which certain finiteness dependencies hold. We present a sufficient condition for safety when some monotonicity constraints also hold.

Copyright © 1987 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.

Load The ACM SIGMOD Anthology, CDROM Edition, Volume 1-3, PODS '82-'98. and ... Load The ACM SIGMOD Anthology, Silver Edition, DVD 1, Proceedings. and ... BibTeX

Printed Edition

Proceedings of the Sixth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, March 23-25, 1987, San Diego, California. ACM 1987, ISBN 0-89791-223-3
Contents BibTeX

Online Edition: ACM Digital Library

References

[Afrati et al. 86]
Foto N. Afrati, Christos H. Papadimitriou, George Papageorgiou, Athena Roussou, Yehoshua Sagiv, Jeffrey D. Ullman: Convergence of Sideways Query Evaluation. PODS 1986: 24-30 BibTeX
[Ramakrishnan et al. 87]
...
[Sagiv and Ullman 84]
...
[Ullman 82]
Jeffrey D. Ullman: Principles of Database Systems, 2nd Edition. Computer Science Press 1982, ISBN 0-914894-36-6
BibTeX
[Ullman and Van Gelder 85]
...
[Zaniolo 86]
Carlo Zaniolo: Safety and Compilation of Non-recursive Horn Clauses. Expert Database Conf. 1986: 237-252 BibTeX

Referenced by

  1. Michael Benedikt, Leonid Libkin: Safe Constraint Queries. PODS 1998: 99-108
  2. Gösta Grahne, Matti Nykänen: Safety, Translation and Evaluation of Alignment Calculus. ADBIS 1997: 295-304
  3. Jiawei Han: Chain-Split Evaluation in Deductive Databases. IEEE Trans. Knowl. Data Eng. 7(2): 261-273(1995)
  4. Serge Abiteboul, Richard Hull, Victor Vianu: Foundations of Databases. Addison-Wesley 1995, ISBN 0-201-53771-0
    Contents
  5. Jiawei Han: Constraint-Based Query Evaluation in Deductive Databases. IEEE Trans. Knowl. Data Eng. 6(1): 96-107(1994)
  6. Gösta Grahne, Matti Nykänen, Esko Ukkonen: Reasoning about Strings in Databases. PODS 1994: 303-312
  7. Jan Chomicki, Tomasz Imielinski: Finite Representation of Infinite Query Answers. ACM Trans. Database Syst. 18(2): 181-223(1993)
  8. Martha Escobar-Molano, Richard Hull, Dean Jacobs: Safety and Translation of Calculus Queries with Scalar Functions. PODS 1993: 253-264
  9. Jiawei Han: Chain-Split Evaluation in Deductive Databases. ICDE 1992: 376-384
  10. Jiawei Han: Compilation-Based List Processing in Deductive Databases. EDBT 1992: 104-119
  11. Alexander Brodsky, Yehoshua Sagiv: Inference of Inequality Constraints in Logic Programs. PODS 1991: 227-240
  12. Jiawei Han: Constraint-Based Reasoning in Deductive Databases. ICDE 1991: 257-265
  13. Dean Jacobs, Richard Hull: Database Programming with Delayed Updates. DBPL 1991: 416-428
  14. Michael Kifer, Eliezer L. Lozinskii: On Compile-Time Query Optimization in Deductive Databases by Means of Static Filtering. ACM Trans. Database Syst. 15(3): 385-426(1990)
  15. Jan Chomicki, Tomasz Imielinski: Relational Specifications of Infinite Query Answers. SIGMOD Conference 1989: 174-183
  16. Moshe Y. Vardi: Automata Theory for Database Theoreticans. PODS 1989: 83-92
  17. Yehoshua Sagiv, Moshe Y. Vardi: Safety of Datalog Queries over Infinite Databases. PODS 1989: 160-171
  18. Alexander Brodsky, Yehoshua Sagiv: Inference of Monotonicity Constraints in Datalog Programs. PODS 1989: 190-199
  19. Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume II. Computer Science Press 1989, ISBN 0-7167-8162-X
    Contents
  20. Ravi Krishnamurthy, Raghu Ramakrishnan, Oded Shmueli: A Framework for Testing Safety and Effective Computability of Extended Datalog (Extended Abstract). SIGMOD Conference 1988: 154-163
  21. Raghu Ramakrishnan, Catriel Beeri, Ravi Krishnamurthy: Optimizing Existential Datalog Queries. PODS 1988: 89-102
  22. Michael Kifer, Raghu Ramakrishnan, Abraham Silberschatz: An Axiomatic Approach to Deciding Query Safety in Deductive Databases. PODS 1988: 52-60
  23. Jan Chomicki, Tomasz Imielinski: Temporal Deductive Databases and Infinite Objects. PODS 1988: 61-73
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:33:52 2009