Containment of graph queries modulo schema

Gutierrez Basulto, Victor ORCID: https://orcid.org/0000-0002-6117-5459, Gutowski, Albert, Ibanez Garcia, Yazmin A. ORCID: https://orcid.org/0000-0002-1276-904X and Murlak, Filip 2024. Containment of graph queries modulo schema. Presented at: 2024 ACM SIGMOD/PODS International Conference on Management of Data, Santiago, Chile, 9-14 June 2024. Published in: Agrawal, Divyakant ed. Proceedings of the ACM on Management of Data. Association for Computing Machinery, pp. 1-26. 10.1145/3651140

Preview

PDF - Published Version Available under License Creative Commons Attribution. Download (694kB) | Preview

Abstract

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.

Item Type:	Conference or Workshop Item (Paper)
Date Type:	Completion
Status:	Published
Schools:	Computer Science & Informatics
Publisher:	Association for Computing Machinery
ISSN:	2836-6573
Date of First Compliant Deposit:	3 April 2024
Date of Acceptance:	9 September 2023
Last Modified:	05 Jul 2024 11:46
URI:	https://orca.cardiff.ac.uk/id/eprint/167697

Actions (repository staff only)

Edit Item