Document Open Access Logo

Combined Tractability of Query Evaluation via Tree Automata and Cycluits

Authors Antoine Amarilli, Pierre Bourhis, Mikaël Monet, Pierre Senellart

PDF
Thumbnail PDF

File

LIPIcs.ICDT.2017.6.pdf
  • Filesize: 472 kB
  • 19 pages

Document Identifiers

Author Details

Antoine Amarilli
Pierre Bourhis
Mikaël Monet
Pierre Senellart

Cite AsGet BibTex

Antoine Amarilli, Pierre Bourhis, Mikaël Monet, and Pierre Senellart. Combined Tractability of Query Evaluation via Tree Automata and Cycluits. In 20th International Conference on Database Theory (ICDT 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 68, pp. 6:1-6:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
https://doi.org/10.4230/LIPIcs.ICDT.2017.6

Abstract

We investigate parameterizations of both database instances and queries that make query evaluation fixed-parameter tractable in combined complexity. We introduce a new Datalog fragment with stratified negation, intensional-clique-guarded Datalog (ICG-Datalog), with linear-time evaluation on structures of bounded treewidth for programs of bounded rule size. Such programs capture in particular conjunctive queries with simplicial decompositions of bounded width, guarded negation fragment queries of bounded CQ-rank, or two-way regular path queries. Our result is shown by compiling to alternating two-way automata, whose semantics is defined via cyclic provenance circuits (cycluits) that can be tractably evaluated. Last, we prove that probabilistic query evaluation remains intractable in combined complexity under this parameterization.
Keywords
  • query evaluation
  • tree automata
  • provenance
  • treewidth
  • circuits

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Serge Abiteboul, Richard Hull, and Victor Vianu. Foundations of databases. Addison-Wesley, 1995. Google Scholar
  2. Noga Alon, Raphael Yuster, and Uri Zwick. Finding and counting given length cycles. Algorithmica, 17(3), 1997. Google Scholar
  3. Antoine Amarilli. The possibility problem for probabilistic XML. In AMW, 2014. URL: http://ceur-ws.org/Vol-1189/paper_2.pdf.
  4. Antoine Amarilli, Pierre Bourhis, Mikaël Monet, and Pierre Senellart. Combined tractability of query evaluation via tree automata and cycluits (extended version). CoRR, abs/1612.04203, 2017. URL: https://arxiv.org/abs/1612.04203.
  5. Antoine Amarilli, Pierre Bourhis, and Pierre Senellart. Provenance circuits for trees and treelike instances. In ICALP, volume 9135 of LNCS, 2015. Google Scholar
  6. Antoine Amarilli, Pierre Bourhis, and Pierre Senellart. Provenance circuits for trees and treelike instances (extended version). CoRR, abs/1511.08723, 2015. Extended version of [5]. Google Scholar
  7. Antoine Amarilli, Pierre Bourhis, and Pierre Senellart. Tractable lineages on treelike instances: Limits and extensions. In PODS, 2016. Google Scholar
  8. Vince Bárány, Balder ten Cate, and Martin Otto. Queries with guarded negation. PVLDB, 5(11), 2012. Google Scholar
  9. Vince Bárány, Balder ten Cate, and Luc Segoufin. Guarded negation. J. ACM, 62(3), 2015. Google Scholar
  10. Pablo Barceló. Querying graph databases. In PODS, 2013. Google Scholar
  11. Pablo Barceló, Miguel Romero, and Moshe Y Vardi. Does query evaluation tractability help query containment? In PODS, 2014. Google Scholar
  12. Michael Benedikt, Pierre Bourhis, and Pierre Senellart. Monadic datalog containment. In ICALP, 2012. Google Scholar
  13. Michael Benedikt, Pierre Bourhis, and Michael Vanden Boom. A step up in expressiveness of decidable fixpoint logics. In LICS, 2016. Google Scholar
  14. Michael Benedikt and Georg Gottlob. The impact of virtual views on containment. PVLDB, 3(1-2), 2010. Google Scholar
  15. Michael Benedikt, Balder ten Cate, and Michael Vanden Boom. Effective interpolation and preservation in guarded logics. In LICS, 2014. Google Scholar
  16. Anne Berry, Romain Pogorelcnik, and Genevieve Simonet. An introduction to clique minimal separator decomposition. Algorithms, 3(2), 2010. Google Scholar
  17. Dietmar Berwanger and Erich Grädel. Games and model checking for guarded logics. In LPAR, 2001. Google Scholar
  18. Jean-Camille Birget. State-complexity of finite-state devices, state compressibility and incompressibility. Mathematical systems theory, 26(3), 1993. Google Scholar
  19. Hans L Bodlaender. A linear-time algorithm for finding tree-decompositions of small treewidth. SIAM J. Comput., 25(6), 1996. Google Scholar
  20. Thierry Cachat. Two-way tree automata solving pushdown games. In Automata logics, and infinite games, chapter 17. Springer, 2002. Google Scholar
  21. Diego Calvanese, Giuseppe De Giacomo, Maurizio Lenzeniri, and Moshe Y. Vardi. Containment of conjunctive regular path queries with inverse. In KR, 2000. Google Scholar
  22. Sara Cohen, Benny Kimelfeld, and Yehoshua Sagiv. Running tree automata on probabilistic XML. In PODS, 2009. Google Scholar
  23. H. Comon, M. Dauchet, R. Gilleron, C. Löding, F. Jacquemard, D. Lugiez, S. Tison, and M. Tommasi. Tree automata: Techniques and applications, 2007. Available from URL: http://tata.gforge.inria.fr/.
  24. Bruno Courcelle. The monadic second-order logic of graphs. I. Recognizable sets of finite graphs. Inf. Comput., 85(1), 1990. Google Scholar
  25. Nilesh Dalvi and Dan Suciu. Management of probabilistic data: foundations and challenges. In PODS, 2007. Google Scholar
  26. Daniel Deutch, Tova Milo, Sudeepa Roy, and Val Tannen. Circuits for Datalog provenance. In ICDT, 2014. Google Scholar
  27. Reinhard Diestel. Simplicial decompositions of graphs: A survey of applications. Discrete Math., 75(1), 1989. Google Scholar
  28. Ronald Fagin. Degrees of acyclicity for hypergraphs and relational database schemes. J. ACM, 30(3), 1983. Google Scholar
  29. J. Flum and M. Grohe. Parameterized Complexity Theory. Springer, 2006. Google Scholar
  30. Jörg Flum, Markus Frick, and Martin Grohe. Query evaluation via tree-decompositions. J. ACM, 49(6), 2002. Google Scholar
  31. Fǎnicǎ Gavril. The intersection graphs of subtrees in trees are exactly the chordal graphs. J. Combinatorial Theory, 16(1), 1974. Google Scholar
  32. Georg Gottlob, Erich Grädel, and Helmut Veith. Datalog LITE: A deductive query language with linear time model checking. ACM Trans. Comput. Log., 3(1), 2002. Google Scholar
  33. Georg Gottlob, Gianluigi Greco, and Francesco Scarcello. Treewidth and hypertree width. In Lucas Bordeaux, Youssef Hamadi, and Pushmeet Kohli, editors, Tractability: Practical Approaches to Hard Problems, chapter 1. Cambridge University Press, 2014. Google Scholar
  34. Georg Gottlob, Nicola Leone, and Francesco Scarcello. Hypertree decompositions and tractable queries. JCSS, 64(3), 2002. Google Scholar
  35. Georg Gottlob, Nicola Leone, and Francesco Scarcello. Robbers, marshals, and guards: game theoretic and logical characterizations of hypertree width. JCSS, 66(4), 2003. Google Scholar
  36. Georg Gottlob, Reinhard Pichler, and Fang Wei. Monadic Datalog over finite structures of bounded treewidth. TOCL, 12(1), 2010. Google Scholar
  37. Todd J Green, Grigoris Karvounarakis, and Val Tannen. Provenance semirings. In PODS, 2007. Google Scholar
  38. Martin Grohe and Dániel Marx. Constraint solving via fractional edge covers. TALG, 11(1), 2014. Google Scholar
  39. Tomasz Imielinski and Witold Lipski, Jr. Incomplete information in relational databases. J. ACM, 31(4), 1984. URL: http://dx.doi.org/10.1145/1634.1886.
  40. Benny Kimelfeld, Yuri Kosharovsky, and Yehoshua Sagiv. Query efficiency in probabilistic XML models. In SIGMOD, 2008. Google Scholar
  41. Benny Kimelfeld and Pierre Senellart. Probabilistic XML: Models and complexity. In Zongmin Ma and Li Yan, editors, Advances in Probabilistic Databases for Uncertain Information Management. Springer, 2013. Google Scholar
  42. Steffen L Lauritzen and David J Spiegelhalter. Local computations with probabilities on graphical structures and their application to expert systems. J. Royal Statistical Society. Series B, 1988. Google Scholar
  43. Hanns-Georg Leimer. Optimal decomposition by clique separators. Discrete Math., 113(1-3), 1993. Google Scholar
  44. Dirk Leinders, Maarten Marx, Jerzy Tyszkiewicz, and Jan Van den Bussche. The semijoin algebra and the guarded fragment. Journal of Logic, Language and Information, 14(3), 2005. Google Scholar
  45. Sharad Malik. Analysis of cyclic combinational circuits. In ICCAD, 1993. Google Scholar
  46. Silviu Maniu, Reynold Cheng, and Pierre Senellart. ProbTree: A query-efficient representation of probabilistic graphs. In BUDA, June 2014. Workshop without formal proceedings. Google Scholar
  47. Dániel Marx. Can you beat treewidth? Theory of Computing, 6(1), 2010. Google Scholar
  48. Alberto O. Mendelzon and Peter T. Wood. Finding regular simple paths in graph databases. In VLDB, 1989. Google Scholar
  49. Albert R. Meyer. Weak monadic second order theory of succesor is not elementary-recursive. In Logic Colloquium, 1975. Google Scholar
  50. Mikaël Monet. Probabilistic evaluation of expressive queries on bounded-treewidth instances. In SIGMOD/PODS PhD Symposium, June 2016. Google Scholar
  51. Marc D. Riedel and Jehoshua Bruck. Cyclic Boolean circuits. Discrete Applied Mathematics, 160(13-14), 2012. Google Scholar
  52. Neil Robertson and Paul D. Seymour. Graph minors. II. Algorithmic aspects of tree-width. J. Algorithms, 7(3), 1986. Google Scholar
  53. Robert E. Tarjan. Decomposition by clique separators. Discrete Math., 55(2), 1985. Google Scholar
  54. Alfred Tarski. A lattice-theoretical fixpoint theorem and its applications. Pacific Journal of Mathematics, 5, 1955. Google Scholar
  55. Moshe Y Vardi. The complexity of relational query languages. In STOC, 1982. Google Scholar
  56. Moshe Y. Vardi. On the complexity of bounded-variable queries. In PODS, pages 266-276, 1995. Google Scholar
  57. Mihalis Yannakakis. Algorithms for acyclic database schemes. In VLDB, 1981. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact