Safety of recursive Horn clauses with infinite relations

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.

REFERENCES

• Afrati et al 86: Foto Afrati , Christos Papadimitriou , George Papageorgiou , Athena Roussou , Yehoshua Sagiv , Jeffrey D Ullman, Convergence of sideways query evaluation, Proceedings of the fifth ACM SIGACT-SIGMOD symposium on Principles of database systems, p.24-30, March 24-26, 1986, Cambridge, Massachusetts, United States [doi>10.1145/6012.15400]
• Ramakrishnan et al 87: "Safety of Recurslve Horn Clauses With Infimte Relaaons," R. Ramaknshnan, F Bancflhon and A Sflberschatz, Manuscnpt
• Sagiv and Ullman 84: "Complexity of a Top-Town Capture Rule," Y. Sager and J D Ullman, STAN-CS-84-1009, Department of Computer Sctence, Stanford Umverstty, 1984
• Ullman 82: "Pnnc~ples of Database Systems," J D Ullman, Computer Sczence Press, 1982
• Ullman and Van Gelder 85: "Tesang ApphcabflRy of Top-Down Capture Rules," J D Ullman and A. Van Gelder, STAN-CS-85-1046, Department of Computer Sctence, Stanford Umverstty, 1985
• Zaniolo 86: "Safety and Compdauon of Non-Recurmvo Horn Clauses," C Zamolo Proc Ftrst lntl Conference on Expert Database Systems, Charleston, 1986

INDEX TERMS

Classification:
  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.1 Mathematical Logic
          Subjects: Logic and constraint programming

  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.0 General
          Subjects: Security, integrity, and protection**
      H.2.4 Systems
          Subjects: Query processing

General Terms:
Algorithms, Management, Performance, Theory