{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,5]],"date-time":"2022-04-05T18:09:37Z","timestamp":1649182177783},"reference-count":24,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2020,9,10]],"date-time":"2020-09-10T00:00:00Z","timestamp":1599696000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2020,9,10]],"date-time":"2020-09-10T00:00:00Z","timestamp":1599696000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"Austrian Science Fund","award":["P30930-N35"],"award-info":[{"award-number":["P30930-N35"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2021,1]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>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\u2014a central feature of many query languages\u2014was 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 {, }-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. For non-simple pattern trees the tractability criteria for simple pattern trees do not capture all tractable classes. We thus extend the characterization for the non-simple case in order to capture some additional tractable cases.<\/jats:p>","DOI":"10.1007\/s00224-020-10002-z","type":"journal-article","created":{"date-parts":[[2020,9,10]],"date-time":"2020-09-10T11:03:24Z","timestamp":1599735804000},"page":"3-41","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Characterizing Tractability of Simple Well-Designed Pattern Trees with Projection"],"prefix":"10.1007","volume":"65","author":[{"given":"Stefan","family":"Mengel","sequence":"first","affiliation":[]},{"given":"Sebastian","family":"Skritek","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2020,9,10]]},"reference":[{"key":"10002_CR1","doi-asserted-by":"crossref","unstructured":"Arenas, M., P\u00e9rez, J.: Querying semantic web data with SPARQL. In: Proceedings of the PODS 2011, pp. 305\u2013316. ACM (2011)","DOI":"10.1145\/1989284.1989312"},{"key":"10002_CR2","doi-asserted-by":"crossref","unstructured":"Arenas, M., Diaz, G.I., Kostylev, E.V.: Reverse engineering SPARQL queries. In: Proceedings of WWW 2016, pp. 239\u2013249. ACM (2016)","DOI":"10.1145\/2872427.2882989"},{"issue":"2","key":"10002_CR3","doi-asserted-by":"publisher","first-page":"8:1","DOI":"10.1145\/3233983","volume":"43","author":"P Barcel\u00f3","year":"2018","unstructured":"Barcel\u00f3, P., Kr\u00f6ll, M., Pichler, R., Skritek, S.: Efficient evaluation and static analysis for well-designed pattern trees with projection. ACM Trans. Database Syst. 43(2), 8:1\u20138:44 (2018)","journal-title":"ACM Trans. Database Syst."},{"key":"10002_CR4","doi-asserted-by":"crossref","unstructured":"Chen, H.: The tractability frontier of graph-like first-order query sets. In: Henzinger, TA, Miller, D (eds.) Proceedings of CSL-LICS 2014, pp. 31:1\u201331:9. ACM (2014)","DOI":"10.1145\/2603088.2603119"},{"key":"10002_CR5","doi-asserted-by":"crossref","unstructured":"Chen, H., Dalmau, V.: Decomposing quantified conjunctive (or disjunctive) formulas. In: Proceedings of LICS 2012, pp 205\u2013214. IEEE Computer Society (2012)","DOI":"10.1109\/LICS.2012.31"},{"key":"10002_CR6","doi-asserted-by":"crossref","unstructured":"Chen, H., Marx, D.: Block-sorted quantified conjunctive queries. In: Fomin, F.V., Freivalds, R., Kwiatkowska, M.Z., Peleg, D. (eds.) Proceedings of ICALP 2013. Lecture Notes in Computer Science, vol. 7966, pp. 125\u2013136. Springer (2013)","DOI":"10.1007\/978-3-642-39212-2_14"},{"key":"10002_CR7","doi-asserted-by":"crossref","unstructured":"Dalmau, V., Kolaitis, P., Vardi, M.: Constraint satisfaction, bounded treewidth, and finite-variable logics. In: International Conference on Principles and Practice of Constraint Programming, vol. 2002, pp. 310\u2013326 (2002)","DOI":"10.1007\/3-540-46135-3_21"},{"key":"10002_CR8","doi-asserted-by":"publisher","first-page":"1202","DOI":"10.1007\/s00224-014-9543-y","volume":"57","author":"A Durand","year":"2015","unstructured":"Durand, A., Mengel, S.: Structural tractability of counting of solutions to conjunctive queries. Theory Comput. Syst. 57, 1202\u20131249 (2015)","journal-title":"Theory Comput. Syst."},{"key":"10002_CR9","volume-title":"Parameterized Complexity Theory Texts in Theoretical Computer Science. An EATCS Series","author":"J Flum","year":"2006","unstructured":"Flum, J., Grohe, M.: Parameterized Complexity Theory Texts in Theoretical Computer Science. An EATCS Series. Springer, Berlin (2006)"},{"key":"10002_CR10","doi-asserted-by":"crossref","unstructured":"Grohe, M.: The parameterized complexity of database queries. In: Buneman, P. (ed.) Proceedings of PODS 2001, pp. 82\u201392. ACM (2001)","DOI":"10.1145\/375551.375564"},{"issue":"4","key":"10002_CR11","doi-asserted-by":"publisher","first-page":"86","DOI":"10.1145\/637411.637428","volume":"31","author":"M Grohe","year":"2002","unstructured":"Grohe, M.: Parameterized complexity for the database theorist. SIGMOD Record 31(4), 86\u201396 (2002)","journal-title":"SIGMOD Record"},{"issue":"1","key":"10002_CR12","doi-asserted-by":"publisher","first-page":"1:1","DOI":"10.1145\/1206035.1206036","volume":"54","author":"M Grohe","year":"2007","unstructured":"Grohe, M.: The complexity of homomorphism and constraint satisfaction problems seen from the other side. J. ACM 54(1), 1:1\u20131:24 (2007)","journal-title":"J. ACM"},{"key":"10002_CR13","doi-asserted-by":"crossref","unstructured":"Grohe, M., Schwentick, T., Segoufin, L.: When is the evaluation of conjunctive queries tractable? In: Vitter, J.S., Spirakis, P.G., Yannakakis, M. (eds.) Proceedings of STOC 2001, pp. 657\u2013666. ACM (2001)","DOI":"10.1145\/380752.380867"},{"key":"10002_CR14","unstructured":"Kaminski, M., Kostylev, E.V.: Beyond well-designed SPARQL. In: Proceedings of ICDT 2016. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, LIPIcs, vol 48, pp. 5:1\u20135:18 (2016)"},{"key":"10002_CR15","unstructured":"Kostylev, E.V., Reutter, J.L., Ugarte, M.: CONSTRUCT queries in SPARQL. In: Proceedings of ICDT 2015, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, LIPIcs, vol. 31, pp. 212\u2013229 (2015)"},{"key":"10002_CR16","unstructured":"Kr\u00f6ll, M., Pichler, R., Skritek, S.: On the complexity of enumerating the answers to well-designed pattern trees. In: Proceedings of ICDT 2016. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, LIPIcs, vol. 48, pp. 22:1\u201322:18 (2016)"},{"issue":"4","key":"10002_CR17","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1145\/2500130","volume":"38","author":"A Letelier","year":"2013","unstructured":"Letelier, A., P\u00e9rez, J., Pichler, R., Skritek, S.: Static analysis and optimization of semantic web queries. ACM Trans. Database Syst. 38 (4), 25 (2013)","journal-title":"ACM Trans. Database Syst."},{"key":"10002_CR18","doi-asserted-by":"crossref","unstructured":"Marx, D: Tractable hypergraph properties for constraint satisfaction and conjunctive queries. In: Schulman, L J (ed.) Proceedings of STOC 2010, pp 735\u2013744. ACM (2010)","DOI":"10.1145\/1806689.1806790"},{"key":"10002_CR19","unstructured":"Mengel, S., Skritek, S.: Characterizing tractability of simple well-designed pattern trees with projection. In: Proceedings of ICDT 2019, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, LIPIcs, vol. 127, pp 20:1\u201320:18 (2019)"},{"issue":"3","key":"10002_CR20","doi-asserted-by":"publisher","first-page":"407","DOI":"10.1006\/jcss.1999.1626","volume":"58","author":"CH Papadimitriou","year":"1999","unstructured":"Papadimitriou, C.H., Yannakakis, M.: On the complexity of database queries. J. Comput. Syst. Sci. 58(3), 407\u2013427 (1999)","journal-title":"J. Comput. Syst. Sci."},{"key":"10002_CR21","doi-asserted-by":"crossref","unstructured":"P\u00e9rez, J., Arenas, M., Gutierrez, C.: Semantics and complexity of SPARQL. ACM Trans. Database Syst. 34(3) (2009)","DOI":"10.1145\/1567274.1567278"},{"key":"10002_CR22","doi-asserted-by":"crossref","unstructured":"Picalausa, F., Vansummeren, S.: What are real SPARQL queries like?. In: Proceedings of SWIM 2011, p. 7. ACM (2011)","DOI":"10.1145\/1999299.1999306"},{"key":"10002_CR23","doi-asserted-by":"crossref","unstructured":"Pichler, R., Skritek, S.: Containment and equivalence of well-designed SPARQL. In: Proceedings of PODS 2014, pp. 39\u201350. ACM (2014)","DOI":"10.1145\/2594538.2594542"},{"key":"10002_CR24","doi-asserted-by":"crossref","unstructured":"Romero, M.: The tractability frontier of well-designed SPARQL queries. In: Proceedings of PODS 2018, pp 295\u2013306. ACM (2018)","DOI":"10.1145\/3196959.3196973"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-020-10002-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00224-020-10002-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-020-10002-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,9,10]],"date-time":"2021-09-10T00:06:22Z","timestamp":1631232382000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00224-020-10002-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,9,10]]},"references-count":24,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2021,1]]}},"alternative-id":["10002"],"URL":"https:\/\/doi.org\/10.1007\/s00224-020-10002-z","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,9,10]]},"assertion":[{"value":"10 September 2020","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}