Surajit Chaudhuri
ABSTRACT
In this paper, we investigate whether recursive Datalog predicates can be approximated by finite unions of conjunctive queries. We introduce a quantitative notion of error and examine two types of approximation, namely, absolute approximation and relative approximation. We also stipulate that the approximations obey certain qualitative criteria, namely we require them to be upper envelopes or lower envelopes of the Datalog predicate they approximate. We establish that absolute approximation by finite unions of conjunctive queries is not possible, which means that no unbounded Datalog predicate can be approximated by a finite union of conjunctive queries in such a way that the error is bounded uniformly by the same constant on all finite databases. After this, we examine relative approximations, i.e., approximations that guarantee bounds for the error relative to the size of the Datalog predicate under consideration. Although such approximations exist in some cases, we show that for several large and well-studied classes of unbounded Datalog predicates it is not possible to find finite unions of conjunctive queries that satisfy the aforementioned qualitative criteria and have the property that the relative error of the approximation is bounded by a constant. Finally, we consider first-order approximations and obtain sharp negative results for the approximability of the transitive closure query and the cycle query by first-order queries.
- AP87.Afrati F., Papadimitriou C.It.: The parallel complexity of simple chain queries. Proc. 5th A CM Syrup. on Principles of Database Systems, 1987, pp. 210-213. Google Scholar
Digital Library
- AG89.Ajtai M., Gurevich Y.: DATALOG vs. First- Order Logic. Proc. 30th IEEE Syrup. o# Foundatzons of Computer Sczence, 1989, pp. 142- 146. Google ScholarDigital Library
- AU79.Aho, A.V., Ullman, J.D.: Universality of data retrieval languages. Proc. 6th A CM Syrup. on Pmnctples of Programming Languages, 1979, pp. 110-117. Google ScholarDigital Library
- Co74.Cook S. A.: An observation of time-storage trade-off, in Journal of Computing and Systems Sciences, Vol 9, pp.308-316, 1974.Google ScholarDigital Library
- CGKV88.Cosmadakis S. S., Gambian H., Kanellakis P. C., Vardi M. Y.: Decidable Optimization Problems for Database Logic Programs. Proc. 20th A CM Syrup. on Theory of Computing, pp. 477-490 Google ScholarDigital Library
- CM77.Chandra A.K., Merlin P.M., "Optimal Implementation of conjunctive queries in relational databases," Proc. 9th A CM Syrnp. on Theory of Computzng, New York, 1977, pp. 77-90. Google ScholarDigital Library
- C93.Chaudhuri, S.: Finding Nonrecursive Envelopes for Recursive Predicates. Proc. 12th A CM Syrup. on Pmnczples of Database Systems, Washington D.C., 1993. Google ScholarDigital Library
- Fa75.Fagin, R.: Monadic generalized spectra, Ze#tschmft fiir Math. Logzk, 21(1975), pp. 89- 96.Google Scholar
- FSV93.Fagin R., Stockmeyer L., Vardi M. Y.: On Monadic NP vs. Monadic co-NP. Proc. 8th IEEE Conf. on Structure #n Complexzty Theory, 1993, pp. 19-30.Google ScholarCross Ref
- GMSV87.Gaifman, H., Mairson, H., Sagiv, Y., Vardi M.Y.: Undecidable optimization problems for database logic programs. Proc. 2nd IEEE Syrup. on Logic in Computer Sczence, Ithaca, 1987, pp. 106-115.Google Scholar
- GJ79.Garey M. R., Johnson D. S.: Computers and lntractabzhty- A Guide to the Theory of NP- Completeness, W. It. Freeman and Co., 1979. Google ScholarDigital Library
- Io86.Ioannides Y. E.: Bounded recursion in deductive databases. Algomthmzca, Vol 1, 1986, pp.361-385.Google Scholar
- KA89.Kanellakis, P., Abiteboul, S.: Deciding bounded recursion in database logic programs. CoIGACT News 20:4, Fall 1989.Google Scholar
- KV90.Kolaitis P. G., Vardi M. Y.: On the expressive power of Datalog: tools and a case study. in Proc. 9th A CM Syrup. on Princzples of Database Systems, 1990, pp. 61-71. Google ScholarDigital Library
- MUV84.Maier, D., Ullman, :I.D., Vardi, M.Y.: On the foundations of the universal relation model. ACM Trans. oR Database Systems 9(1984), pp. 283-308. Google ScholarDigital Library
- Na89.Naughton J. F.: Data independent recursion in deductive databases.: Journal of Computzng and Systems Sczences, Vol 38, 1989, pp. 259- 289.Google ScholarCross Ref
- PS82.Papadimitriou C., Steiglitz K.: Comb#natomal Optim#zatzon- Algomthms and Complexity, Prentice Hall, New Jersey, 1982. Google ScholarDigital Library
- SY81.Sagiv,Y., Yannakakis M.: Equivalences among Relational Expressions with the union and difference operators. JACM, 27:4, pp 633-655. Google ScholarDigital Library
- U89.Ullman, :I.D.: Prznczples of Database and Knowledge Base Systems- Vol. 2, Computer Science Press, 1989. Google ScholarDigital Library
- Va82.Vardi, M.Y.: The complexity of relational query languages. Proc. ldth A CM Syrup. on Theory of Computzn9, San Francisco, 1982, pp. I37-146. Google ScholarDigital Library
Index Terms
- Can Datalog be approximated?
Recommendations
Can Datalog Be Approximated?
Special issue on principles of database systemsIn this paper, we investigate whether recursive Datalog predicates can be approximated by finite unions of conjunctive queries. We introduce a quantitative notion of error and examine two types of approximation, namely,absoluteapproximation andrelative ...
Datalog rewritability of Disjunctive Datalog programs and non-Horn ontologies
We study the problem of rewriting a Disjunctive Datalog program into an equivalent plain Datalog program (i.e., one that entails the same facts for every dataset). We show that a Disjunctive Datalog program is Datalog rewritable if and only if it can be ...
Monadic datalog containment
ICALP'12: Proceedings of the 39th international colloquium conference on Automata, Languages, and Programming - Volume Part IIWe reconsider the problem of containment of monadic datalog (MDL) queries in unions of conjunctive queries (UCQs). Prior work has dealt with special cases, but has left the precise complexity characterization open. We begin by establishing a 2EXPTIME ...
Comments