{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:34:14Z","timestamp":1750221254433,"version":"3.41.0"},"reference-count":44,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2018,6,30]],"date-time":"2018-06-30T00:00:00Z","timestamp":1530316800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"FWF project","award":["W1255-N23"],"award-info":[{"award-number":["W1255-N23"]}]},{"name":"Fondecyt","award":["1170109"],"award-info":[{"award-number":["1170109"]}]},{"DOI":"10.13039\/501100001821","name":"Vienna Science and Technology Fund","doi-asserted-by":"crossref","award":["ICT12-015"],"award-info":[{"award-number":["ICT12-015"]}],"id":[{"id":"10.13039\/501100001821","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Millenium Institute for Foundational Research on Data"},{"name":"Austrian Science Fund","award":["P25207-N23 and P30930-N35"],"award-info":[{"award-number":["P25207-N23 and P30930-N35"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Database Syst."],"published-print":{"date-parts":[[2018,6,30]]},"abstract":"<jats:p>\n            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\u2014known as\n            <jats:italic>(projected) well-designed pattern trees<\/jats:italic>\n            (pWDPTs)\u2014that 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.\n          <\/jats:p>","DOI":"10.1145\/3233983","type":"journal-article","created":{"date-parts":[[2018,8,21]],"date-time":"2018-08-21T12:09:47Z","timestamp":1534853387000},"page":"1-44","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5,"title":["Efficient Evaluation and Static Analysis for Well-Designed Pattern Trees with Projection"],"prefix":"10.1145","volume":"43","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2293-2653","authenticated-orcid":false,"given":"Pablo","family":"Barcel\u00f3","sequence":"first","affiliation":[{"name":"Dept. of Comp. Science, Univ. of Chile and IMFD Chile, Chile"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Markus","family":"Kr\u00f6ll","sequence":"additional","affiliation":[{"name":"TU Wien, Austria"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Reinhard","family":"Pichler","sequence":"additional","affiliation":[{"name":"TU Wien, Austria"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sebastian","family":"Skritek","sequence":"additional","affiliation":[{"name":"TU Wien, Austria"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2018,8,21]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2007.04.013"},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2736277.2741636"},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2872427.2882989"},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989284.1989312"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/2902251.2902298"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1137\/130911731"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2745754.2745767"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/3137586.3137588"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/2594538.2594553"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/15M1034714"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.14778\/3167892.3167895"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-92800-3_5"},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/800105.803397"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(99)00220-0"},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(87)90018-6"},{"key":"e_1_2_2_16_1","series-title":"Lecture Notes in Computer Science","volume-title":"Vardi","author":"Dalmau V\u00edctor","year":"2002","unstructured":"V\u00edctor 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\u201902), Lecture Notes in Computer Science , Vol. 2470 . Springer , 310--326. V\u00edctor 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\u201902), Lecture Notes in Computer Science, Vol. 2470. Springer, 310--326."},{"key":"e_1_2_2_17_1","volume-title":"Fellows","author":"Downey Rodney G.","year":"1999","unstructured":"Rodney G. Downey and Michael R . Fellows . 1999 . Parameterized Complexity. Springer , Berlin. Rodney G. Downey and Michael R. Fellows. 1999. Parameterized Complexity. Springer, Berlin."},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/2402.322390"},{"key":"e_1_2_2_19_1","volume-title":"General and fractional hypertree decompositions: Hard and easy cases. CoRR abs\/1611.01090","author":"Fischl Wolfgang","year":"2016","unstructured":"Wolfgang Fischl , Georg Gottlob , and Reinhard Pichler . 2016. General and fractional hypertree decompositions: Hard and easy cases. CoRR abs\/1611.01090 ( 2016 ). Wolfgang Fischl, Georg Gottlob, and Reinhard Pichler. 2016. General and fractional hypertree decompositions: Hard and easy cases. CoRR abs\/1611.01090 (2016)."},{"key":"e_1_2_2_20_1","series-title":"An EATCS Series","volume-title":"Parameterized Complexity Theory. Texts in Theoretical Computer Science","author":"Flum J\u00f6rg","unstructured":"J\u00f6rg Flum and Martin Grohe . 2010. Parameterized Complexity Theory. Texts in Theoretical Computer Science . An EATCS Series . Springer , 1--495. J\u00f6rg Flum and Martin Grohe. 2010. Parameterized Complexity Theory. Texts in Theoretical Computer Science. An EATCS Series. Springer, 1--495."},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/2902251.2902309"},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/382780.382783"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2001.1809"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/1568318.1568320"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539701396807"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/1206035.1206036"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/2636918"},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/380752.380867"},{"key":"e_1_2_2_29_1","volume-title":"Proceedings of the 19th International Conference on Database Theory (ICDT\u201916)","volume":"48","author":"Kaminski Mark","unstructured":"Mark Kaminski and Egor V. Kostylev . 2016. Beyond well-designed SPARQL . In Proceedings of the 19th International Conference on Database Theory (ICDT\u201916) (LIPIcs), Vol. 48 . Schloss Dagstuhl\u2014Leibniz-Zentrum fuer Informatik, 5:1--5:18. Mark Kaminski and Egor V. Kostylev. 2016. Beyond well-designed SPARQL. In Proceedings of the 19th International Conference on Database Theory (ICDT\u201916) (LIPIcs), Vol. 48. Schloss Dagstuhl\u2014Leibniz-Zentrum fuer Informatik, 5:1--5:18."},{"key":"e_1_2_2_30_1","volume-title":"Proceedings of the19th International Conference on Database Theory (ICDT\u201916)","volume":"48","author":"Kr\u00f6ll Markus","year":"2016","unstructured":"Markus Kr\u00f6ll , 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\u201916) (LIPIcs), Vol. 48 . 22:1--22:18. Markus Kr\u00f6ll, 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\u201916) (LIPIcs), Vol. 48. 22:1--22:18."},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/2500130"},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/2535926"},{"key":"e_1_2_2_33_1","volume-title":"Retrieved","author":"DB.","year":"2017","unstructured":"Mongo DB. 2017 . MongoDB . Retrieved August 07, 2018 from https:\/\/www.mongodb.com\/. MongoDB. 2017. MongoDB. Retrieved August 07, 2018 from https:\/\/www.mongodb.com\/."},{"volume-title":"Retrieved","year":"2017","key":"e_1_2_2_34_1","unstructured":"Neo4j. 2017 . Cypher - Graph Query Language . Retrieved August 07, 2018 from http:\/\/neo4j.com\/developer\/cypher-query-language\/. Neo4j. 2017. Cypher - Graph Query Language. Retrieved August 07, 2018 from http:\/\/neo4j.com\/developer\/cypher-query-language\/."},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1999.1626"},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/1567274.1567278"},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/1999299.1999306"},{"key":"e_1_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/2594538.2594542"},{"key":"e_1_2_2_39_1","volume-title":"Retrieved","author":"Prud\u2032hommeaux Eric","year":"2008","unstructured":"Eric Prud\u2032hommeaux 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. Eric Prud\u2032hommeaux 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."},{"key":"e_1_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/3196959.3196973"},{"key":"e_1_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-08353-7_172"},{"key":"e_1_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/322077.322083"},{"key":"e_1_2_2_43_1","volume-title":"Proceedings of the 7th International Conference on Very Large Data Bases VLDB","author":"Yannakakis Mihalis","year":"1981","unstructured":"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. 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."},{"key":"e_1_2_2_44_1","doi-asserted-by":"publisher","DOI":"10.5555\/3013589.3013600"}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3233983","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3233983","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T02:08:01Z","timestamp":1750212481000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3233983"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,6,30]]},"references-count":44,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2018,6,30]]}},"alternative-id":["10.1145\/3233983"],"URL":"https:\/\/doi.org\/10.1145\/3233983","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"type":"print","value":"0362-5915"},{"type":"electronic","value":"1557-4644"}],"subject":[],"published":{"date-parts":[[2018,6,30]]},"assertion":[{"value":"2016-12-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-06-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-08-21","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}