Jeffrey D. Ullman
Abstract
We examine methods of implementing queries about relational databases in the case where these queries are expressed in first-order logic as a collection of Horn clauses. Because queries may be defined recursively, straightforward methods of query evaluation do not always work, and a variety of strategies have been proposed to handle subsets of recursive queries. We express such query evaluation techniques as “capture rules” on a graph representing clauses and predicates. One essential property of capture rules is that they can be applied independently, thus providing a clean interface for query-evaluation systems that use several different strategies in different situations. Another is that there be an efficient test for the applicability of a given rule. We define basic capture rules corresponding to application of operators from relational algebra, a top-down capture rule corresponding to “backward chaining,” that is, repeated resolution of goals, a bottom-up rule, corresponding to “forward chaining,” where we attempt to deduce all true facts in a given class, and a “sideways” rule that allows us to pass results from one goal to another.
- 1 AHO, A. V., AND ULLMAN, J.D. Universality of data retrieval languages. In Proceedings of the 6th ACM Symposium on Principles of Programming Languages (1979), ACM, New York, 110- 120. Google Scholar
Digital Library
- 2 CHANDRA, A. K., AND HAREL, D. Horn clauses and the fixpoint hierarchy. In Proceedings of the ACM Symposium on Principles of Database Systems (1982), ACM, New York, 158-163. Google ScholarDigital Library
- 3 CHANG, C.L. On evaluation of queries containing derived relations in a relational database. In Formal Bases {or Data Bases (Toulouse, France, 1979), Plenum, New York.Google Scholar
- 4 CLARK, K.L. Negation as failure. In Logic and Databases, Plenum, New York, 1978, 293-323.Google Scholar
- 5 GALLAIRE, H., AND MINKER, J. Logic and Databases, Plenum, New York, 1978. Google ScholarDigital Library
- 6 GENESERETH, M. R. MRS: A metalevel representation system. Rep. HPP-83-28, Dept. of Computer Science, Stanford Univ., Stanford, Calif., 1983.Google Scholar
- 7 HENSCHEN, L. J., AND NAQVI, S.A. On compiling queries in recursive first-order databases. J. ACM 31, 1984, 47-85. Google ScholarDigital Library
- 8 KOWALSKI, R. A proof procedure using connection graphs. J. ACM 22, 4 (1975), 572-595. Google ScholarDigital Library
- 9 KOWALSKI, R. Logic/or Problem Solving. North Holland, Amsterdam, 1979. Google ScholarDigital Library
- 10 McKAY, D., AND SHAPIRO, S. Using active connection graphs for reasoning with recursive rules. In Proceedings 7th IJCAI (1981), 368-374.Google Scholar
- 11 NAISH, L. Automatic generation of control for logic programs. TR 83/6, Dept. of Computer Science, Univ. of Melbourne, 1983.Google Scholar
- 12 NmSSON, N. Principles of Artificial Intelligence. Tioga Press, Palo Alto, Calif., 1980. Google ScholarDigital Library
- 13 REITER, R. On closed world databases. In {5}, pp. 55-76.Google Scholar
- 14 REITER, R. Deductive question-answering in relational databases. In Logic and Databases, Plenum, New York, 1978, 149-177.Google Scholar
- 15 SAGIV, Y., AND ULLMAN, J. D. Complexity of a top-down capture rule. STAN-CS-84-1009, Dept. of Computer Science, Stanford Univ., Stanford, Calif., July, 1984. Google ScholarDigital Library
- 16 SICKEL, S. A search technique for clause interconnectivity graphs. IEEETC C-25 8 (1976), 823- 834.Google Scholar
- 17 SUSSMAN, G. J., WINOGRAD, T., AND CHARNIAK, E. Microplanner reference manual. MIT-AI 203a, AI Laboratory, MIT, Cambridge, Mass. 1970. Google ScholarDigital Library
- 18 TARJAN, R.F. Depth-first search and linear graph algorithms. SIAM J. Comput. 1, 2 (1972), 146-160.Google ScholarDigital Library
- 19 TAYLOR, S., ET AL. Logic programming using parallel associative operations. In International Symposium on Logic Programming (1984), 58-68.Google Scholar
- 20 ULLMAN, J.D. Principles of Database Systems. Computer Science Press, Rockville, Md., 1982. Google ScholarDigital Library
- 21 ULLMAN, J. D., AND VAN GELDER, A. Testing applicability of top-down capture rules. STAN- CS-85-1046, Dept. of Computer Science, Stanford Univ., Stanford, Calif., Feb. 1985.Google Scholar
- 22 VAN EMDEN, M. H., AND KOWALSK{, R. The semantics of predicate logic as a programming language. J. ACM 23, 4 (1976), 733-742. Google ScholarDigital Library
Index Terms
- Implementation of logical query languages for databases
Recommendations
Query languages for data exchange: beyond unions of conjunctive queries
ICDT '09: Proceedings of the 12th International Conference on Database TheoryThe class of unions of conjunctive queries (UCQ) has been shown to be particularly well-behaved for data exchange; its certain answers can be computed in polynomial time (in terms of data complexity). However, this is not the only class with this ...
Query evaluation in deductive databases with alternating fixpoint semantics
First-order formulas allow natural descriptions of queries and rules. Van Gelder's alternating fixpoint semantics extends the well-founded semantics of normal logic programs to general logic programs with arbitrary first-order formulas in rule bodies. ...
Query Languages for Constraint Databases: First-Order Logic, Fixed-Points, and Convex Hulls
ICDT '01: Proceedings of the 8th International Conference on Database TheoryWe define various extensions of first-order logic on linear as well as polynomial constraint databases. First, we extend first-order logic by a convex closure operator and show this logic, FO(conv), to be closed and to have Ptime data-complexity. We ...
Reviews
Edward Sciore
The area of database query evaluation is relatively well understood, as is shown by a recent survey article [1]. The two basic strategies are bottom-up, which creates intermediate relations (using, e.g., sort-merge joining), and top-down, which avoids intermediate relations by means of indexing and relation scanning. These two approaches each have relative advantages, and are intermixed in many standard implementations. The same principles apply to recursive queries, but their interaction is much less understood; in fact, lately there has been heated debate between adherents of PROLOG (top-down) and Deductive Databases (bottom-up). The present paper is the first serious attempt at merging these techniques. Ullman represents a query as a graph, and each evaluation technique is represented as a “capture rule” which operates on the graph by capturing nodes. The sequence of capture rules used to capture the goal node denotes an evaluation of the query. A feature of the capture rule idea is that many capture rules can be defined, not just top-down and bottom-up. (Ullman defines a “sideways” rule, for example.) The relative advantage of any rule is expressed by the kinds of graphs in which it can capture nodes. The choice of which strategies to use can be made by preprocessing the query, and the chosen evaluation can be proven correct and terminating. The main contribution of this paper is a framework for understanding evaluation strategies. The idea has a lot of potential, and can result in more flexible, efficient, and automatic database/logic-programming systems.
Access critical reviews of Computing literature here
Become a reviewer for Computing Reviews.
Comments