Document Open Access Logo

Characterizing Tractability of Simple Well-Designed Pattern Trees with Projection

Authors Stefan Mengel, Sebastian Skritek

PDF
Thumbnail PDF

File

LIPIcs.ICDT.2019.20.pdf
  • Filesize: 0.62 MB
  • 18 pages

Document Identifiers

Author Details

Stefan Mengel
  • CNRS, CRIL UMR 8188, Lens, France
Sebastian Skritek
  • Faculty of Informatics, TU Wien, Vienna, Austria

Funding

  • Skritek, Sebastian: Supported by the Austrian Science Fund (FWF): P30930-N35.

Cite As Get BibTex

Stefan Mengel and Sebastian Skritek. Characterizing Tractability of Simple Well-Designed Pattern Trees with Projection. In 22nd International Conference on Database Theory (ICDT 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 127, pp. 20:1-20:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.ICDT.2019.20

Abstract

We study the complexity of evaluating well-designed pattern trees, a query language extending conjunctive queries with the possibility to define parts of the query to be optional. This possibility of optional parts is important for obtaining meaningful results over incomplete data sources as it is common in semantic web settings.
Recently, a structural characterization of the classes of well-designed pattern trees that can be evaluated in polynomial time was shown. However, projection - a central feature of many query languages - was not considered in this study. We work towards closing this gap by giving a characterization of all tractable classes of simple well-designed pattern trees with projection (under some common complexity theoretic assumptions). Since well-designed pattern trees correspond to the fragment of well-designed {AND, OPTIONAL}-SPARQL queries this gives a complete description of the tractable classes of queries with projections in this fragment that can be characterized by the underlying graph structures of the queries.

Subject Classification

ACM Subject Classification
  • Theory of computation → Database query languages (principles)
  • Theory of computation → Database query processing and optimization (theory)
Keywords
  • SPARQL
  • well-designed pattern trees
  • query evaluation
  • FPT
  • characterizing tractable classes

Metrics

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

Related Versions

References

  1. Marcelo Arenas, Gonzalo I. Diaz, and Egor V. Kostylev. Reverse Engineering SPARQL Queries. In Proc. WWW 2016, pages 239-249. ACM, 2016. Google Scholar
  2. Marcelo Arenas and Jorge Pérez. Querying semantic web data with SPARQL. In Proc. PODS 2011, pages 305-316. ACM, 2011. Google Scholar
  3. Pablo Barceló, Markus Kröll, Reinhard Pichler, and Sebastian Skritek. Efficient Evaluation and Static Analysis for Well-Designed Pattern Trees with Projection. ACM Trans. Database Syst., 43(2):8:1-8:44, 2018. Google Scholar
  4. Hubie Chen. The tractability frontier of graph-like first-order query sets. In Thomas A. Henzinger and Dale Miller, editors, Proc. CSL-LICS 2014, pages 31:1-31:9. ACM, 2014. Google Scholar
  5. Hubie Chen and Víctor Dalmau. Decomposing Quantified Conjunctive (or Disjunctive) Formulas. In Proc. LICS 2012, pages 205-214. IEEE Computer Society, 2012. Google Scholar
  6. Hubie Chen and Dániel Marx. Block-Sorted Quantified Conjunctive Queries. In Fedor V. Fomin, Rusins Freivalds, Marta Z. Kwiatkowska, and David Peleg, editors, Proc. ICALP 2013, volume 7966 of Lecture Notes in Computer Science, pages 125-136. Springer, 2013. Google Scholar
  7. Arnaud Durand and Stefan Mengel. Structural Tractability of Counting of Solutions to Conjunctive Queries. Theory of Computing Systems, pages 1-48, 2014. Google Scholar
  8. Jörg Flum and Martin Grohe. Parameterized Complexity Theory. Texts in Theoretical Computer Science. An EATCS Series. Springer, 2006. Google Scholar
  9. Martin Grohe. The Parameterized Complexity of Database Queries. In Peter Buneman, editor, Proc. PODS 2001, pages 82-92. ACM, 2001. Google Scholar
  10. Martin Grohe. Parameterized Complexity for the Database Theorist. SIGMOD Record, 31(4):86-96, 2002. Google Scholar
  11. Martin Grohe. The complexity of homomorphism and constraint satisfaction problems seen from the other side. Journal of the ACM, 54(1), 2007. Google Scholar
  12. Martin Grohe, Thomas Schwentick, and Luc Segoufin. When is the evaluation of conjunctive queries tractable? In Jeffrey Scott Vitter, Paul G. Spirakis, and Mihalis Yannakakis, editors, Proc. STOC 2001, pages 657-666. ACM, 2001. Google Scholar
  13. Mark Kaminski and Egor V. Kostylev. Beyond Well-designed SPARQL. In Proc. ICDT 2016, volume 48 of LIPIcs, pages 5:1-5:18. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2016. Google Scholar
  14. 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 fuer Informatik, 2015. Google Scholar
  15. Markus Kröll, Reinhard Pichler, and Sebastian Skritek. On the Complexity of Enumerating the Answers to Well-Designed Pattern Trees. In Proc. ICDT 2016, volume 48 of LIPIcs, pages 22:1-22:18. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2016. Google Scholar
  16. 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
  17. Dániel Marx. Tractable hypergraph properties for constraint satisfaction and conjunctive queries. In Leonard J. Schulman, editor, Proc. STOC 2010, pages 735-744. ACM, 2010. Google Scholar
  18. Christos H. Papadimitriou and Mihalis Yannakakis. On the Complexity of Database Queries. J. Comput. Syst. Sci., 58(3):407-427, 1999. Google Scholar
  19. Jorge Pérez, Marcelo Arenas, and Claudio Gutierrez. Semantics and complexity of SPARQL. ACM Trans. Database Syst., 34(3), 2009. Google Scholar
  20. François Picalausa and Stijn Vansummeren. What are real SPARQL queries like? In Proc. SWIM 2011, page 7. ACM, 2011. Google Scholar
  21. Reinhard Pichler and Sebastian Skritek. Containment and equivalence of well-designed SPARQL. In Proc. PODS 2014, pages 39-50. ACM, 2014. Google Scholar
  22. Miguel Romero. The Tractability Frontier of Well-designed SPARQL Queries. In Proc. PODS 2018, pages 295-306. ACM, 2018. 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