Pablo Barceló
Reinhard Pichler
Skip Abstract Section
Skip Supplemental Material SectionAbstract
Conjunctive queries (CQs) fail to provide an answer when the pattern described by the query does not exactly match the data. CQs might thus be too restrictive as a querying mechanism when data is semistructured or incomplete. The semantic web therefore provides a formalism—known as (projected) well-designed pattern trees (pWDPTs)—that tackles this problem: pWDPTs allow us to formulate queries that match parts of the query over the data if available, but do not ignore answers of the remaining query otherwise. Here we abstract away the specifics of semantic web applications and study pWDPTs over arbitrary relational schemas. Since the language of pWDPTs subsumes CQs, their evaluation problem is intractable. We identify structural properties of pWDPTs that lead to (fixed-parameter) tractability of various variants of the evaluation problem. We also show that checking if a pWDPT is equivalent to one in our tractable class is in 2EXPTIME. As a corollary, we obtain fixed-parameter tractability of evaluation for pWDPTs with such good behavior. Our techniques also allow us to develop a theory of approximations for pWDPTs.
Supplemental Material
Available for Download
zip
barcelo.zip (388.4 KB)
Supplemental movie, appendix, image and software files for, Efficient Evaluation and Static Analysis forWell-DesignedPattern Trees with Projection
- Isolde Adler, Georg Gottlob, and Martin Grohe. 2007. Hypertree width and related hypergraph invariants. Eur. J. Comb. 28, 8 (2007), 2167--218. Google Scholar
Digital Library
- Shqiponja Ahmetaj, Wolfgang Fischl, Reinhard Pichler, Mantas Simkus, and Sebastian Skritek. 2015. Towards reconciling SPARQL and certain answers. In Proceedings of the 24th International Conference on World Wide Web (WWW’15). ACM, 23--33. Google ScholarDigital Library
- Marcelo Arenas, Gonzalo I. Diaz, and Egor V. Kostylev. 2016. Reverse engineering SPARQL queries. In Proceedings of the 25th International Conference on World Wide Web (WWW’16). ACM, 239--249. Google ScholarDigital Library
- Marcelo Arenas and Jorge Pérez. 2011. Querying semantic web data with SPARQL. In Proceedings of the 30th ACM Symposium on Principles of Database Systems (PODS’11). ACM, 305--316. Google ScholarDigital Library
- Marcelo Arenas and Martín Ugarte. 2016. Designing a query language for RDF: Marrying open and closed worlds. In Proceedings of the 35th ACM Symposium on Principles of Database Systems (PODS’16). ACM, 225--236. Google ScholarDigital Library
- Pablo Barceló, Leonid Libkin, and Miguel Romero. 2014. Efficient approximations of conjunctive queries. SIAM J. Comput. 43, 3 (2014), 1085--1130.Google ScholarCross Ref
- Pablo Barceló, Reinhard Pichler, and Sebastian Skritek. 2015. Efficient evaluation and approximation of well-designed pattern trees. In Proceedings of the 34th ACM Symposium on Principles of Database Systems (PODS’15). ACM, 131--144. Google ScholarDigital Library
- Pablo Barceló, Andreas Pieris, and Miguel Romero. 2017. Semantic optimization in tractable classes of conjunctive queries. SIGMOD Record 46, 2 (2017), 5--17. Google ScholarDigital Library
- Pablo Barceló, Miguel Romero, and Moshe Y. Vardi. 2014. Does query evaluation tractability help query containment? In Proceedings of the 33rd ACM Symposium on Principles of Database Systems (PODS’14). ACM, 188--199. Google ScholarDigital Library
- Pablo Barceló, Miguel Romero, and Moshe Y. Vardi. 2016. Semantic acyclicity on graph databases. SIAM J. Comput. 45, 4 (2016), 1339--1376.Google ScholarDigital Library
- Angela Bonifati, Wim Martens, and Thomas Timm. 2017. An analytical study of large SPARQL query logs. PVLDB 11, 2 (2017), 149--161. Google ScholarDigital Library
- Andrei A. Bulatov, Andrei A. Krokhin, and Benoit Larose. 2008. Dualities for constraint satisfaction problems. In Complexity of Constraints - An Overview of Current Research Themes, Lecture Notes in Computer Science, Vol. 5250. Springer, 93--124. Google ScholarDigital Library
- Ashok K. Chandra and Philip M. Merlin. 1977. Optimal implementation of conjunctive queries in relational data bases. In Proceedings of the 9th Annual ACM Symposium on Theory of Computing. ACM, 77--90. Google ScholarDigital Library
- Chandra Chekuri and Anand Rajaraman. 2000. Conjunctive query containment revisited. Theor. Comput. Sci. 239, 2 (2000), 211--229. Google ScholarDigital Library
- Stephen A. Cook and Pierre McKenzie. 1987. Problems complete for deterministic logarithmic space. J. Algorithms 8, 3 (1987), 385--394. Google ScholarDigital Library
- Víctor Dalmau, Phokion G. Kolaitis, and Moshe Y. Vardi. 2002. Constraint satisfaction, bounded treewidth, and finite-variable logics. In Proceedings of the 8th International Conference on Principles and Practice of Constraint Programming (CP’02), Lecture Notes in Computer Science, Vol. 2470. Springer, 310--326. Google ScholarDigital Library
- Rodney G. Downey and Michael R. Fellows. 1999. Parameterized Complexity. Springer, Berlin. Google ScholarDigital Library
- Ronald Fagin. 1983. Degrees of acyclicity for hypergraphs and relational database schemes. J. ACM 30, 3 (1983), 514--550. Google ScholarDigital Library
- Wolfgang Fischl, Georg Gottlob, and Reinhard Pichler. 2016. General and fractional hypertree decompositions: Hard and easy cases. CoRR abs/1611.01090 (2016).Google Scholar
- Jörg Flum and Martin Grohe. 2010. Parameterized Complexity Theory. Texts in Theoretical Computer Science. An EATCS Series. Springer, 1--495. Google ScholarDigital Library
- Georg Gottlob, Gianluigi Greco, Nicola Leone, and Francesco Scarcello. 2016. Hypertree decompositions: Questions and answers. In Proceedings of the 35th ACM Symposium on Principles of Database Systems (PODS’16). PODS, 57--74. Google ScholarDigital Library
- Georg Gottlob, Nicola Leone, and Francesco Scarcello. 2001. The complexity of acyclic conjunctive queries. J. ACM 48, 3 (2001), 431--498. Google ScholarDigital Library
- Georg Gottlob, Nicola Leone, and Francesco Scarcello. 2002. Hypertree decompositions and tractable queries. J. Comput. Syst. Sci. 64, 3 (2002), 579--627. Google ScholarDigital Library
- Georg Gottlob, Zoltán Miklós, and Thomas Schwentick. 2009. Generalized hypertree decompositions: NP-hardness and tractable variants. J. ACM 56, 6 (2009), 30:1--30:32. Google ScholarDigital Library
- Georg Gottlob and Reinhard Pichler. 2004. Hypergraphs in model checking: Acyclicity and hypertree-width versus clique-width. SIAM J. Comput. 33, 2 (2004), 351--378. Google ScholarDigital Library
- Martin Grohe. 2007. The complexity of homomorphism and constraint satisfaction problems seen from the other side. J. ACM 54, 1 (2007), 1:1--1:24. Google ScholarDigital Library
- Martin Grohe and Dániel Marx. 2014. Constraint solving via fractional edge covers. ACM Trans. Algorithms 11, 1 (2014), 4:1--4:20. Google ScholarDigital Library
- Martin Grohe, Thomas Schwentick, and Luc Segoufin. 2001. When is the evaluation of conjunctive queries tractable? In Proceedings of the 33rd Annual ACM Symposium on Theory of Computing. ACM, 657--666. Google ScholarDigital Library
- Mark Kaminski and Egor V. Kostylev. 2016. Beyond well-designed SPARQL. In Proceedings of the 19th International Conference on Database Theory (ICDT’16) (LIPIcs), Vol. 48. Schloss Dagstuhl—Leibniz-Zentrum fuer Informatik, 5:1--5:18.Google Scholar
- Markus Kröll, Reinhard Pichler, and Sebastian Skritek. 2016. On the complexity of enumerating the answers to well-designed pattern trees. In Proceedings of the19th International Conference on Database Theory (ICDT’16) (LIPIcs), Vol. 48. 22:1--22:18.Google Scholar
- Andrés Letelier, Jorge Pérez, Reinhard Pichler, and Sebastian Skritek. 2013. Static analysis and optimization of semantic web queries. ACM Trans. Database Syst. 38, 4 (2013), 25:1--25:45. Google ScholarDigital Library
- Dániel Marx. 2013. Tractable hypergraph properties for constraint satisfaction and conjunctive queries. J. ACM 60, 6 (2013), 42:1--42:51. Google ScholarDigital Library
- MongoDB. 2017. MongoDB. Retrieved August 07, 2018 from https://www.mongodb.com/.Google Scholar
- Neo4j. 2017. Cypher - Graph Query Language. Retrieved August 07, 2018 from http://neo4j.com/developer/cypher-query-language/.Google Scholar
- Christos H. Papadimitriou and Mihalis Yannakakis. 1999. On the complexity of database queries. J. Comput. Syst. Sci. 58, 3 (1999), 407--427. Google ScholarDigital Library
- Jorge Pérez, Marcelo Arenas, and Claudio Gutierrez. 2009. Semantics and complexity of SPARQL. ACM Trans. Database Syst. 34, 3 (2009), 16:1--16:45. Google ScholarDigital Library
- François Picalausa and Stijn Vansummeren. 2011. What are real SPARQL queries like? In Proceedings of the International Workshop on Semantic Web Information Management (SWIM’11). ACM, 7. Google ScholarDigital Library
- Reinhard Pichler and Sebastian Skritek. 2014. Containment and equivalence of well-designed SPARQL. In Proceedings of the 33rd ACM Symposium on Principles of Database Systems (PODS’14). ACM, 39--50. Google ScholarDigital Library
- Eric Prud′hommeaux and Andy Seaborne. 2008. SPARQL Query Language for RDF. W3C Recommendation. W3C. Retrieved August 07, 2018 from http://www.w3.org/TR/rdf-sparql-query.Google Scholar
- Miguel Romero. 2018. The tractability frontier of well-designed SPARQL queries. In Proceedings of the 37th ACM Symposium on Principles of Database Systems (PODS’18). ACM, 295--306. Google ScholarDigital Library
- Ivan Hal Sudborough. 1977. Time and tape bounded auxiliary pushdown automata. In Proceedings of the 6th Symposium on Mathematical Foundations of Computer Science (MFCS'77), Vol. 53. Springer, 493--503.Google ScholarCross Ref
- Ivan Hal Sudborough. 1978. On the tape complexity of deterministic context-free languages. J. ACM 25, 3 (1978), 405--414. Google ScholarDigital Library
- Mihalis Yannakakis. 1981. Algorithms for acyclic database schemes. In Proceedings of the 7th International Conference on Very Large Data Bases VLDB 1981. IEEE Computer Society, 82--94. Google ScholarDigital Library
- Xiaowang Zhang, Jan Van den Bussche, and François Picalausa. 2016. On the satisfiability problem for SPARQL patterns. J. Artif. Intell. Res. 56 (2016), 403--428. Google ScholarDigital Library
Index Terms
- Efficient Evaluation and Static Analysis for Well-Designed Pattern Trees with Projection
Recommendations
Efficient Evaluation and Approximation of Well-designed Pattern Trees
PODS '15: Proceedings of the 34th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database SystemsConjunctive queries (CQs) fail to provide an answer when the pattern described by the query does not exactly match the data. CQs might thus be too restrictive as a querying mechanism when data is semistructured or incomplete. The semantic web therefore ...
Characterizing Tractability of Simple Well-Designed Pattern Trees with Projection
AbstractWe 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 ...
Static analysis and optimization of semantic web queries
PODS '12: Proceedings of the 31st ACM SIGMOD-SIGACT-SIGAI symposium on Principles of Database SystemsStatic analysis is a fundamental task in query optimization. In this paper we study static analysis and optimization techniques for SPARQL, which is the standard language for querying Semantic Web data. Of particular interest for us is the optionality ...
Comments