On the Complexity of Enumerating the Answers to Well-designed Pattern Trees
Document Open Access Logo

On the Complexity of Enumerating the Answers to Well-designed Pattern Trees

Authors Markus Kröll, Reinhard Pichler, Sebastian Skritek

PDF
Thumbnail PDF

File

LIPIcs.ICDT.2016.22.pdf
  • Filesize: 0.56 MB
  • 18 pages

Document Identifiers

Author Details

Markus Kröll
Reinhard Pichler
Sebastian Skritek

Cite As Get BibTex

Markus Kröll, Reinhard Pichler, and Sebastian Skritek. On the Complexity of Enumerating the Answers to Well-designed Pattern Trees. In 19th International Conference on Database Theory (ICDT 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 48, pp. 22:1-22:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.ICDT.2016.22

Abstract

Well-designed pattern trees (wdPTs) have been introduced as an extension of conjunctive queries to allow for partial matching - analogously to the OPTIONAL operator of the semantic web query language SPARQL. Several computational problems of wdPTs have been studied in recent years, such as the evaluation problem in various settings, the counting problem, as well as static analysis tasks including the containment and equivalence problems. Also restrictions needed to achieve tractability of these tasks have been proposed. In contrast, the problem of enumerating the answers to a wdPT has been largely ignored so far. In this work, we embark on a systematic study of the complexity of the enumeration problem of wdPTs. As our main result, we identify several tractable and intractable cases of this problem both from a classical complexity point of view and from a parameterized complexity point of view.

Subject Classification

Keywords
  • SPARQL
  • Pattern Trees
  • CQs
  • Enumeration
  • Complexity

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, Reading, Massachusetts, 1995. Google Scholar
  2. Shqiponja Ahmetaj, Wolfgang Fischl, Reinhard Pichler, Mantas Simkus, and Sebastian Skritek. Towards reconciling SPARQL and certain answers. In Proc. WWW 2015, pages 23-33. ACM, 2015. Google Scholar
  3. Guillaume Bagan, Arnaud Durand, and Etienne Grandjean. On acyclic conjunctive queries and constant delay enumeration. In Computer Science Logic, pages 208-222. Springer, 2007. Google Scholar
  4. Pablo Barceló, Reinhard Pichler, and Sebastian Skritek. Efficient evaluation and approximation of well-designed pattern trees. In Proc. PODS 2015, pages 131-144. ACM, 2015. Google Scholar
  5. Andrei A. Bulatov, Víctor Dalmau, Martin Grohe, and Dániel Marx. Enumerating homomorphisms. J. Comput. Syst. Sci., 78(2):638-650, 2012. Google Scholar
  6. Chandra Chekuri and Anand Rajaraman. Conjunctive query containment revisited. Theor. Comput. Sci., 239(2):211-229, 2000. Google Scholar
  7. Nadia Creignou and J-J Hébrard. On generating all solutions of generalized satisfiability problems. Informatique théorique et applications, 31(6):499-511, 1997. Google Scholar
  8. Nadia Creignou, Arne Meier, Julian-Steffen Müller, Johannes Schmidt, and Heribert Vollmer. Paradigms for parameterized enumeration. CoRR, abs/1306.2171, 2013. Google Scholar
  9. Nadia Creignou and Heribert Vollmer. Parameterized complexity of weighted satisfiability problems: Decision, enumeration, counting. Fundam. Inform., 136(4):297-316, 2015. URL: http://dx.doi.org/10.3233/FI-2015-1159.
  10. Víctor Dalmau, Phokion G. Kolaitis, and Moshe Y. Vardi. Constraint satisfaction, bounded treewidth, and finite-variable logics. In Proc. CP, pages 310-326, 2002. Google Scholar
  11. Rodney G. Downey and Michael R. Fellows. Parameterized Complexity. Springer, Berlin/Heidelberg/New York, 1999. Google Scholar
  12. Arnaud Durand, Nicole Schweikardt, and Luc Segoufin. Enumerating answers to first-order queries over databases of low degree. In Proc. PODS 2014, pages 121-131. ACM, 2014. Google Scholar
  13. Jörg Flum and Martin Grohe. Parameterized complexity theory. Berlin/Heidelberg/New York, 2010. Google Scholar
  14. Georg Gottlob, Nicola Leone, and Francesco Scarcello. The complexity of acyclic conjunctive queries. J. ACM, 48(3):431-498, 2001. Google Scholar
  15. Georg Gottlob, Nicola Leone, and Francesco Scarcello. Hypertree decompositions and tractable queries. J. Comput. Syst. Sci., 64(3):579-627, 2002. Google Scholar
  16. Martin Grohe. The complexity of homomorphism and constraint satisfaction problems seen from the other side. J. ACM, 54(1), 2007. Google Scholar
  17. David S. Johnson, Christos H. Papadimitriou, and Mihalis Yannakakis. On generating all maximal independent sets. Inf. Process. Lett., 27(3):119-123, 1988. URL: http://dx.doi.org/10.1016/0020-0190(88)90065-8.
  18. Dimitris J Kavvadias, Martha Sideri, and Elias C Stavropoulos. Generating all maximal models of a boolean expression. Information Processing Letters, 74(3):157-162, 2000. Google Scholar
  19. Wojciech Kazana and Luc Segoufin. Enumeration of first-order queries on classes of structures with bounded expansion. In Proc. PODS 2013, pages 297-308. ACM, 2013. Google Scholar
  20. Egor V. Kostylev, Juan L. Reutter, and Martín Ugarte. CONSTRUCT queries in SPARQL. In Proc. ICDT 2015, volume 31 of LIPIcs, pages 212-229. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2015. Google Scholar
  21. Matthieu Latapy. Main-memory triangle computations for very large (sparse (power-law)) graphs. Theoretical Computer Science, 407(1):458-473, 2008. Google Scholar
  22. François Le Gall. Powers of tensors and fast matrix multiplication. In Proc. ISAAC 2014, pages 296-303. ACM, 2014. Google Scholar
  23. Andrés Letelier, Jorge Pérez, Reinhard Pichler, and Sebastian Skritek. Static analysis and optimization of semantic web queries. ACM Trans. Database Syst., 38(4):25, 2013. Google Scholar
  24. Christos H. Papadimitriou and Mihalis Yannakakis. On the complexity of database queries. J. Comput. Syst. Sci., 58(3):407-427, 1999. Google Scholar
  25. Jorge Pérez, Marcelo Arenas, and Claudio Gutierrez. Semantics and complexity of SPARQL. ACM Trans. Database Syst., 34(3), 2009. Google Scholar
  26. Reinhard Pichler and Sebastian Skritek. Containment and equivalence of well-designed SPARQL. In Proc. PODS 2014, pages 39-50. ACM, 2014. Google Scholar
  27. Reinhard Pichler and Sebastian Skritek. On the hardness of counting the solutions of SPARQL queries. In Proc. AMW 2014, volume 1189 of CEUR Workshop Proceedings. CEUR-WS.org, 2014. Google Scholar
  28. Eric Prud'hommeaux and Andy Seaborne. SPARQL Query Language for RDF. W3C Recommendation, World Wide Web Consortium (W3C), January 2008. URL: http://www.w3.org/TR/rdf-sparql-query/.
  29. Luc Segoufin. Enumerating with constant delay the answers to a query. In Proc. ICDT 2013, pages 10-20. ACM, 2013. Google Scholar
  30. Luc Segoufin. A glimpse on constant delay enumeration (invited talk). In Proc. STACS 2014, volume 25 of LIPIcs, pages 13-27. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2014. Google Scholar
  31. Yann Strozecki. Enumeration complexity and matroid decomposition. PhD thesis, Universite Paris Diderot - Paris 7, December 2010. URL: http://www.prism.uvsq.fr/~ystr/these_strozecki.
  32. Mihalis Yannakakis. Algorithms for acyclic database schemes. In Proc. VLDB, pages 82-94, 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 About DROPS Imprint Privacy Contact