Semantic Acyclicity Under Constraints

ABSTRACT

A conjunctive query (CQ) is semantically acyclic if it is equivalent to an acyclic one. Semantic acyclicity has been studied in the constraint-free case, and deciding whether a query enjoys this property is NP-complete. However, in case the database is subject to constraints such as tuple-generating dependencies (tgds) that can express, e.g., inclusion dependencies, or equality-generating dependencies (egds) that capture, e.g., functional dependencies, a CQ may turn out to be semantically acyclic under the constraints while not semantically acyclic in general. This opens avenues to new query optimization techniques. In this paper we initiate and develop the theory of semantic acyclicity under constraints. More precisely, we study the following natural problem: Given a CQ and a set of constraints, is the query semantically acyclic under the constraints, or, in other words, is the query equivalent to an acyclic one over all those databases that satisfy the set of constraints?

We show that, contrary to what one might expect, decidability of CQ containment is a necessary but not sufficient condition for the decidability of semantic acyclicity. In particular, we show that semantic acyclicity is undecidable in the presence of full tgds (i.e., Datalog rules). In view of this fact, we focus on the main classes of tgds for which CQ containment is decidable, and do not capture the class of full tgds, namely guarded, non-recursive and sticky tgds. For these classes we show that semantic acyclicity is decidable, and its complexity coincides with the complexity of CQ containment. In the case of egds, we show that if we focus on keys over unary and binary predicates, then semantic acyclicity is decidable (NP-complete). We finally consider the problem of evaluating a semantically acyclic query over a database that satisfies a set of constraints. For guarded tgds and functional dependencies the evaluation problem is tractable.

References

1. S. Abiteboul, R. Hull, and V. Vianu. Foundations of Databases. Addison-Wesley, 1995.
2. J.-F. Baget, M.-L. Mugnier, S. Rudolph, and M. Thomazo. Walking the complexity lines for generalized guarded existential rules. In IJCAI, pages 712--717, 2011.
3. V. Bárány, G. Gottlob, and M. Otto. Querying the guarded fragment. Logical Methods in Computer Science, 10(2), 2014.
4. P. Barceló, L. Libkin, and M. Romero. Efficient approximations of conjunctive queries. SIAM J. Comput., 43(3):1085--1130, 2014.
5. P. Barceló, R. Pichler, and S. Skritek. Efficient evaluation and approximation of well-designed pattern trees. In PODS, pages 131--144, 2015.
6. P. Barceló, M. Romero, and M. Y. Vardi. Semantic acyclicity on graph databases. In PODS, pages 237--248, 2013.
7. C. Beeri and M. Y. Vardi. The implication problem for data dependencies. In ICALP, pages 73--85, 1981.
8. A. Calı, G. Gottlob, and M. Kifer. Taming the infinite chase: Query answering under expressive relational constraints. J. Artif. Intell. Res., 48:115--174, 2013.
9. A. Calı, G. Gottlob, and T. Lukasiewicz. A general Datalog-based framework for tractable query answering over ontologies. J. Web Sem., 14:57--83, 2012.
10. A. Calı, G. Gottlob, and A. Pieris. Towards more expressive ontology languages: The query answering problem. Artif. Intell., 193:87--128, 2012.
11. D. Calvanese, G. De Giacomo, and M. Lenzerini. Conjunctive query containment and answering under description logic constraints. ACM Trans. Comput. Log., 9(3), 2008.
12. A. K. Chandra and P. M. Merlin. Optimal implementation of conjunctive queries in relational data bases. In STOC, pages 77--90, 1977.
13. H. Chen and V. Dalmau. Beyond hypertree width: Decomposition methods without decompositions. In CP, pages 167--181, 2005.
14. V. Dalmau, P. G. Kolaitis, and M. Y. Vardi. Constraint satisfaction, bounded treewidth, and finite-variable logics. In CP, pages 310--326, 2002.
15. R. Fagin. A normal form for relational databases that is based on domians and keys. ACM Trans. Database Syst., 6(3):387--415, 1981.
16. R. Fagin, P. G. Kolaitis, R. J. Miller, and L. Popa. Data exchange: Semantics and query answering. Theor. Comput. Sci., 336(1):89--124, 2005.
17. D. Figueira. Semantically acyclic conjunctive queries under functional dependencies. In LICS, 2016. To appear.
18. T. Gogacz and J. Marcinkowski. Converging to the chase - A tool for finite controllability. In LICS, pages 540--549, 2013.
19. G. Gottlob, G. Greco, and B. Marnette. Hyperconsistency width for constraint satisfaction: Algorithms and complexity results. In Graph Theory, Computational Intelligence and Thought, pages 87--99, 2009.
20. G. Gottlob, G. Orsi, and A. Pieris. Query rewriting and optimization for ontological databases. ACM Trans. Database Syst., 2014.
21. P. Hell and J. Nesetril. Graphs and Homomorphisms. Oxford University Press, 2004.
22. D. S. Johnson and A. C. Klug. Testing containment of conjunctive queries under functional and inclusion dependencies. J. Comput. Syst. Sci., 28(1):167--189, 1984.
23. M. Krötzsch and S. Rudolph. Extending decidable existential rules by joining acyclicity and guardedness. In IJCAI, pages 963--968, 2011.
24. T. Lukasiewicz, M. V. Martinez, A. Pieris, and G. I. Simari. From classical to consistent query answering under existential rules. In AAAI, pages 1546--1552, 2015.
25. D. Maier, A. O. Mendelzon, and Y. Sagiv. Testing implications of data dependencies. ACM Trans. Database Syst., 4(4):455--469, 1979.
26. C. H. Papadimitriou and M. Yannakakis. On the complexity of database queries. J. Comput. Syst. Sci., 58(3):407--427, 1999.
27. M. Yannakakis. Algorithms for acyclic database schemes. In VLDB, pages 82--94, 1981.

Index Terms

• Information systems

  • Data management systems

    • Query languages