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

A Framework for Testing Safety and Effective Computability of Extended Datalog (Extended Abstract).

Ravi Krishnamurthy, Raghu Ramakrishnan, Oded Shmueli: A Framework for Testing Safety and Effective Computability of Extended Datalog (Extended Abstract). SIGMOD Conference 1988: 154-163
@inproceedings{DBLP:conf/sigmod/KrishnamurthyRS88,
  author    = {Ravi Krishnamurthy and
               Raghu Ramakrishnan and
               Oded Shmueli},
  editor    = {Haran Boral and
               Per-{\AA}ke Larson},
  title     = {A Framework for Testing Safety and Effective Computability of
               Extended Datalog (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     = {154-163},
  ee        = {http://doi.acm.org/10.1145/50202.50219, db/conf/sigmod/KrishnamurthyRS88.html},
  crossref  = {DBLP:conf/sigmod/88},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

This paper presents a methodology for testing a general logic program containing function symbols and built-in predicates for safety and effective computability. Safety is the property that the set of answers for a given query is finite. A related issue is whether the evaluation strategy can effectively compute all answers and terminate. We consider these problems under the assumption that queries are evaluated using a bottom-up fixpoint computation. We also approximate the use of function symbols by considering Datalog programs with infinite base relations over which finiteness constraints and monotonicity constraints are considered. One of the main results of this paper is a recursive algorithm, check_clique, to test the safety and effective computabtity of predicates in arbitrarily complex cliques. This algorithm takes certain procedures as parameters, and its applicability can be strengthened by making these procedures more sophisticated. We specify the properties required of these procedures precisely, and present a formal proof of correctness for algorithm check_clique. This work provides a framework for testing safety and effective computability of recursive programs, and is based on a clique by clique analysis. The results reported here form the basis of the safety testing for the LDL language, being implemented at MCC.

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

[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
[Bancilhon et al. 86]
François Bancilhon, David Maier, Yehoshua Sagiv, Jeffrey D. Ullman: Magic Sets and Other Strange Ways to Implement Logic Programs. PODS 1986: 1-15 BibTeX
[Bancilhon and Ramakrishnan 86]
François Bancilhon, Raghu Ramakrishnan: An Amateur's Introduction to Recursive Query Processing Strategies. SIGMOD Conference 1986: 16-52 BibTeX
[Bancilhon and Ramakrishnan 87]
...
[Beeri and Ramakrishnan 87]
Catriel Beeri, Raghu Ramakrishnan: On the Power of Magic. PODS 1987: 269-284 BibTeX
[Gaifman 86]
...
[Kifer and Lozinskii 88]
Michael Kifer, Eliezer L. Lozinskii: SYGRAF: Implementing Logic Programs in a Database Style. IEEE Trans. Software Eng. 14(7): 922-935(1988) BibTeX
[Krishnamurthy et al. 87]
...
[LLoyd 84]
John W. Lloyd: Foundations of Logic Programming, 1st Edition. Springer 1984, ISBN 3-540-13299-6
BibTeX
[Ramakrishnan et al. 87]
Raghu Ramakrishnan, François Bancilhon, Abraham Silberschatz: Safety of Recursive Horn Clauses With Infinite Relations. PODS 1987: 328-339 BibTeX
[Sagiv and Ullman 84]
...
[Shmueli 87]
Oded Shmueli: Decidability and Expressiveness of Logic Queries. PODS 1987: 237-249 BibTeX
[Ullman 85]
Jeffrey D. Ullman: Implementation of Logical Query Languages for Databases. ACM Trans. Database Syst. 10(3): 289-321(1985) BibTeX
[Ullman and Van Gelder 85]
...
[Van Gelder and Topor 87]
Allen Van Gelder, Rodney W. Topor: Safety and Correct Translation of Relational Calculus Formulas. PODS 1987: 313-327 BibTeX
[Zaniolo 86]
Carlo Zaniolo: Safety and Compilation of Non-recursive Horn Clauses. Expert Database Conf. 1986: 237-252 BibTeX

Referenced by

  1. Divesh Srivastava, S. Sudarshan, Raghu Ramakrishnan, Jeffrey F. Naughton: Space Optimization in Deductive Databases. ACM Trans. Database Syst. 20(4): 472-516(1995)
  2. Alexander Aiken, Joseph M. Hellerstein, Jennifer Widom: Static Analysis Techniques for Predicting the Behavior of Active Database Rules. ACM Trans. Database Syst. 20(1): 3-41(1995)
  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. Jiawei Han: Chain-Split Evaluation in Deductive Databases. ICDE 1992: 376-384
  7. Jiawei Han: Compilation-Based List Processing in Deductive Databases. EDBT 1992: 104-119
  8. Alexander Brodsky, Yehoshua Sagiv: Inference of Inequality Constraints in Logic Programs. PODS 1991: 227-240
  9. Jiawei Han: Constraint-Based Reasoning in Deductive Databases. ICDE 1991: 257-265
  10. Danette Chimenti, Ruben Gamboa, Ravi Krishnamurthy, Shamim A. Naqvi, Shalom Tsur, Carlo Zaniolo: The LDL System Prototype. IEEE Trans. Knowl. Data Eng. 2(1): 76-90(1990)
  11. Danette Chimenti, Ruben Gamboa, Ravi Krishnamurthy: Towards on Open Architecture for LDL. VLDB 1989: 195-203
  12. Hirohisa Seki: On the Power of Alexander Templates. PODS 1989: 150-159
  13. Moshe Y. Vardi: Automata Theory for Database Theoreticans. PODS 1989: 83-92
  14. Yehoshua Sagiv, Moshe Y. Vardi: Safety of Datalog Queries over Infinite Databases. PODS 1989: 160-171
  15. Alexander Brodsky, Yehoshua Sagiv: Inference of Monotonicity Constraints in Datalog Programs. PODS 1989: 190-199
  16. Jianhua Zhu, David Maier: Computational Objects in Object-Oriented Data Models. DBPL 1989: 139-160
  17. Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume II. Computer Science Press 1989, ISBN 0-7167-8162-X
    Contents
  18. Ravi Krishnamurthy, Shamim A. Naqvi: Towards a Real Horn Clause Language. VLDB 1988: 252-263
  19. Michael Kifer, Raghu Ramakrishnan, Abraham Silberschatz: An Axiomatic Approach to Deciding Query Safety in Deductive Databases. PODS 1988: 52-60
  20. Ravi Krishnamurthy, Carlo Zaniolo: Control and Optimization Strategies in the Implementation of LDL. DBPL 1987: 329-345
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