{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,22]],"date-time":"2026-07-22T03:48:12Z","timestamp":1784692092424,"version":"3.55.0"},"reference-count":35,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2024,5,10]],"date-time":"2024-05-10T00:00:00Z","timestamp":1715299200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"NCN","award":["2018\/30\/E\/ST6\/00042"],"award-info":[{"award-number":["2018\/30\/E\/ST6\/00042"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2024,5,10]]},"abstract":"<jats:p>With multiple graph database systems on the market and a new Graph Query Language standard on the horizon, it is time to revisit some classic static analysis problems. Query containment, arguably the workhorse of static analysis, has already received a lot of attention in the context of graph databases, but not so in the presence of schemas. We aim to change this. Because there is no universal agreement yet on what graph schemas should be, we rely on an abstract formalism borrowed from the knowledge representation community: we assume that schemas are expressed in a description logic (DL). We identify a suitable DL that capture both basic constraints on the labels of incident nodes and edges, and more refined schema features such as participation, cardinality, and unary key constraints. Basing upon, and extending, the rich body of work on DLs, we solve the containment modulo schema problem for unions of conjunctive regular path queries (UCRPQs) and schemas whose descriptions do not mix inverses and counting. For two-way UCRPQs (UC2RPQs) we solve the problem under additional assumptions that tend to hold in practice: we restrict the use of concatenation in queries and participation constraints in schemas.<\/jats:p>","DOI":"10.1145\/3651140","type":"journal-article","created":{"date-parts":[[2024,5,14]],"date-time":"2024-05-14T08:32:13Z","timestamp":1715675533000},"page":"1-26","source":"Crossref","is-referenced-by-count":6,"title":["Containment of Graph Queries Modulo Schema"],"prefix":"10.1145","volume":"2","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6117-5459","authenticated-orcid":false,"given":"V\u00edctor","family":"Guti\u00e9rrez-Basulto","sequence":"first","affiliation":[{"name":"Cardiff University, Cardiff, United Kingdom"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7084-2965","authenticated-orcid":false,"given":"Albert","family":"Gutowski","sequence":"additional","affiliation":[{"name":"University of Warsaw, Warsaw, Poland"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1276-904X","authenticated-orcid":false,"given":"Yazmin A.","family":"Ib\u00e1\u00f1ez-Garc\u00eda","sequence":"additional","affiliation":[{"name":"Cardiff University, Cardiff, United Kingdom"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0989-3717","authenticated-orcid":false,"given":"Filip","family":"Murlak","sequence":"additional","affiliation":[{"name":"University of Warsaw, Warsaw, Poland"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2024,5,14]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/3104031"},{"key":"e_1_2_1_2_1","volume-title":"PG-Schema: Schemas for Property Graphs. CoRR","author":"Angles Renzo","year":"2022","unstructured":"Renzo Angles, Angela Bonifati, Stefania Dumbrava, George Fletcher, Alastair Green, Jan Hidders, Bei Li, Leonid Libkin, Victor Marsault, Wim Martens, Filip Murlak, Stefan Plantikow, Ognjen Savkovic, Michael Schmidt, Juan Sequeda, Slawek Staworko, Dominik Tomaszuk, Hannes Voigt, Domagoj Vrgoc, Mingxi Wu, and Dusan Zivkovic. 2022. PG-Schema: Schemas for Property Graphs. CoRR , Vol. abs\/2211.10962 (2022)."},{"key":"e_1_2_1_3_1","volume-title":"PG-Keys: Keys for Property Graphs. In SIGMOD Conference. ACM, 2423--2436","author":"Angles Renzo","year":"2021","unstructured":"Renzo Angles, Angela Bonifati, Stefania Dumbrava, George Fletcher, Keith W. Hare, Jan Hidders, Victor E. Lee, Bei Li, Leonid Libkin, Wim Martens, Filip Murlak, Josh Perryman, Ognjen Savkovic, Michael Schmidt, Juan F. Sequeda, Slawek Staworko, and Dominik Tomaszuk. 2021. PG-Keys: Keys for Property Graphs. In SIGMOD Conference. ACM, 2423--2436."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1613\/jair.2820"},{"key":"e_1_2_1_5_1","volume-title":"An Introduction to Description Logic","author":"Baader Franz","unstructured":"Franz Baader, Ian Horrocks, Carsten Lutz, and Ulrike Sattler. 2017. An Introduction to Description Logic. Cambridge University Press."},{"key":"e_1_2_1_6_1","doi-asserted-by":"crossref","unstructured":"Pablo Barcel\u00f3 Baeza. 2013. Querying graph databases. In PODS. ACM 175--188.","DOI":"10.1145\/2463664.2465216"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.5555\/1644522.1644713"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/3584372.3588654"},{"key":"e_1_2_1_9_1","doi-asserted-by":"crossref","unstructured":"Angela Bonifati Wim Martens and Thomas Timm. 2019. Navigating the Maze of Wikidata Query Logs. In WWW. ACM 127--138.","DOI":"10.1145\/3308558.3313472"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-019-00558-9"},{"key":"e_1_2_1_11_1","volume-title":"MMSNP, and Expressive Description Logics","author":"Bourhis Pierre","unstructured":"Pierre Bourhis and Carsten Lutz. 2016. Containment in Monadic Disjunctive Datalog, MMSNP, and Expressive Description Logics. In KR. AAAI Press, 207--216."},{"key":"e_1_2_1_12_1","volume-title":"Giuseppe De Giacomo, and Maurizio Lenzerini. 1998 a. On the Decidability of Query Containment under Constraints","author":"Calvanese Diego","unstructured":"Diego Calvanese, Giuseppe De Giacomo, and Maurizio Lenzerini. 1998 a. On the Decidability of Query Containment under Constraints. In PODS. ACM Press, 149--158."},{"key":"e_1_2_1_13_1","volume-title":"Maurizio Lenzerini, and Moshe Y. Vardi.","author":"Calvanese Diego","year":"2000","unstructured":"Diego Calvanese, Giuseppe De Giacomo, Maurizio Lenzerini, and Moshe Y. Vardi. 2000. Containment of Conjunctive Regular Path Queries with Inverse. In KR. Morgan Kaufmann, 176--185."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2001.1805"},{"key":"e_1_2_1_15_1","volume-title":"Logics for Databases and Information Systems","author":"Calvanese Diego","unstructured":"Diego Calvanese, Maurizio Lenzerini, and Daniele Nardi. 1998 b. Description Logics for Conceptual Data Modeling. In Logics for Databases and Information Systems. Kluwer, 229--263."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1613\/jair.548"},{"key":"e_1_2_1_17_1","unstructured":"Diego Calvanese Magdalena Ortiz and Mantas Simkus. 2011. Containment of Regular Path Queries under Description Logic Constraints. In IJCAI. IJCAI\/AAAI 805--812."},{"key":"e_1_2_1_18_1","volume-title":"MFCS (LIPIcs","volume":"15","author":"Danielski Daniel","year":"2019","unstructured":"Daniel Danielski and Emanuel Kieronski. 2019. Finite Satisfiability of Unary Negation Fragment with Transitivity. In MFCS (LIPIcs, Vol. 138). 17:1--17:15."},{"key":"e_1_2_1_19_1","volume-title":"Graph Pattern Matching in GQL and SQL\/PGQ. In SIGMOD Conference. ACM, 2246--2258","author":"Deutsch Alin","year":"2022","unstructured":"Alin Deutsch, Nadime Francis, Alastair Green, Keith Hare, Bei Li, Leonid Libkin, Tobias Lindaaker, Victor Marsault, Wim Martens, Jan Michels, Filip Murlak, Stefan Plantikow, Petra Selmer, Oskar van Rest, Hannes Voigt, Domagoj Vrgoc, Mingxi Wu, and Fred Zemke. 2022. Graph Pattern Matching in GQL and SQL\/PGQ. In SIGMOD Conference. ACM, 2246--2258."},{"key":"e_1_2_1_20_1","volume-title":"DBPL (Lecture Notes in Computer Science","volume":"39","author":"Deutsch Alin","year":"2001","unstructured":"Alin Deutsch and Val Tannen. 2001. Optimization Properties for Classes of Conjunctive Regular Path Queries. In DBPL (Lecture Notes in Computer Science, Vol. 2397). Springer, 21--39."},{"key":"e_1_2_1_21_1","volume-title":"ICDT (LIPIcs","volume":"18","author":"Figueira Diego","year":"2020","unstructured":"Diego Figueira. 2020. Containment of UC2RPQ: The Hard and Easy Cases. In ICDT (LIPIcs, Vol. 155). Schloss Dagstuhl - Leibniz-Zentrum f\u00fc r Informatik, 9:1--9:18."},{"key":"e_1_2_1_22_1","volume-title":"Wim Martens, Matthias Niewerth, and Tina Trautner.","author":"Figueira Diego","year":"2020","unstructured":"Diego Figueira, Adwait Godbole, Shankara Narayanan Krishna, Wim Martens, Matthias Niewerth, and Tina Trautner. 2020. Containment of Simple Conjunctive Regular Path Queries. In KR. 371--380."},{"key":"e_1_2_1_23_1","volume-title":"Query Containment for Conjunctive Queries with Regular Expressions","author":"Florescu Daniela","unstructured":"Daniela Florescu, Alon Y. Levy, and Dan Suciu. 1998. Query Containment for Conjunctive Queries with Regular Expressions. In PODS. ACM Press, 139--148."},{"key":"e_1_2_1_24_1","volume-title":"Paolo Guagliardo, Leonid Libkin, Victor Marsault, Wim Martens, Filip Murlak, Liat Peterfreund, Alexandra Rogova, and Domagoj Vrgoc.","author":"Francis Nadime","year":"2023","unstructured":"Nadime Francis, Am\u00e9 lie Gheerbrant, Paolo Guagliardo, Leonid Libkin, Victor Marsault, Wim Martens, Filip Murlak, Liat Peterfreund, Alexandra Rogova, and Domagoj Vrgoc. 2023. A Researcher's Digest of GQL (Invited Talk). In ICDT (LIPIcs, Vol. 255). Schloss Dagstuhl - Leibniz-Zentrum f\u00fc r Informatik, 1:1--1:22."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1186\/s13321-016-0144--4"},{"key":"e_1_2_1_26_1","volume-title":"Algebraic Theory of Automata","author":"Ginzburg Abraham","unstructured":"Abraham Ginzburg. 1968. Algebraic Theory of Automata. Academic Press."},{"key":"e_1_2_1_27_1","volume-title":"Albert Gutowski, Yazm'i n Ib\u00e1 n ez-Garc'i a, and Filip Murlak.","author":"Gogacz Tomasz","year":"2020","unstructured":"Tomasz Gogacz, V'i ctor Guti\u00e9 rrez-Basulto, Albert Gutowski, Yazm'i n Ib\u00e1 n ez-Garc'i a, and Filip Murlak. 2020. On Finite Entailment of Non-Local Queries in Description Logics. In KR. 424--433."},{"key":"e_1_2_1_28_1","volume-title":"Proceedings of the 19th International Conference on Principles of Knowledge Representation and Reasoning, KR 2022","author":"Basulto V'i","year":"2022","unstructured":"V'i ctor Guti\u00e9 rrez-Basulto, Albert Gutowski, Yazm'i n Ib\u00e1 n ez-Garc'i a, and Filip Murlak. 2022. Finite Entailment of UCRPQs over ALC Ontologies. In Proceedings of the 19th International Conference on Principles of Knowledge Representation and Reasoning, KR 2022, Haifa, Israel. July 31 - August 5, 2022, , Gabriele Kern-Isberner, Gerhard Lakemeyer, and Thomas Meyer (Eds.). https:\/\/proceedings.kr.org\/2022\/19\/"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2022.103808"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.5555\/557365"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2007.07.104"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1186\/s13040-016-0102-8"},{"key":"e_1_2_1_33_1","volume-title":"Highly Acyclic Groups, Hypergraph Covers and the Guarded Fragment","author":"Otto Martin","unstructured":"Martin Otto. 2010. Highly Acyclic Groups, Hypergraph Covers and the Guarded Fragment. In LICS. IEEE Computer Society, 11--20."},{"key":"e_1_2_1_34_1","volume-title":"Models of Program Logics","author":"Pratt Vaughan R.","unstructured":"Vaughan R. Pratt. 1979. Models of Program Logics. In FOCS. IEEE Computer Society, 115--122."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/3434642"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3651140","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3651140","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,22]],"date-time":"2025-08-22T21:39:51Z","timestamp":1755898791000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3651140"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,5,10]]},"references-count":35,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2024,5,10]]}},"alternative-id":["10.1145\/3651140"],"URL":"https:\/\/doi.org\/10.1145\/3651140","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,5,10]]}}}