EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Containment of Graph Queries Modulo Schema

Víctor Gutiérrez-Basulto, Albert Gutowski, Yazmin A. Ibáñez-García, Filip Murlak

Proceedings of the ACM on Management of Data · 10.05.2024 · 2 (2) · 1-26

DOI: 10.1145/3651140 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Proceedings of the ACM on Management of Data, online erschienen am 14.05.2024. Verfasst von Víctor Gutiérrez-Basulto und 3 weiteren Autor:innen. Die Arbeit wurde bisher 7-mal zitiert (Crossref) und nennt 35 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: NCN.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

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.

Förderung

  • NCN

Zitieren

APA

Gutiérrez-Basulto, V., Gutowski, A., Ibáñez-García, Y. A., & Murlak, F. (2024). Containment of Graph Queries Modulo Schema. Proceedings of the ACM on Management of Data, 2(2), 1-26. https://doi.org/10.1145/3651140

Vancouver

Gutiérrez-Basulto V, Gutowski A, Ibáñez-García YA, Murlak F. Containment of Graph Queries Modulo Schema. Proceedings of the ACM on Management of Data. 2024;2(2):1-26. doi:10.1145/3651140

BibTeX
@article{GutirrezBasulto2024,
  author = {Gutiérrez-Basulto, Víctor and Gutowski, Albert and Ibáñez-García, Yazmin A. and Murlak, Filip},
  title = {Containment of Graph Queries Modulo Schema},
  journal = {Proceedings of the ACM on Management of Data},
  year = {2024},
  volume = {2},
  number = {2},
  pages = {1--26},
  doi = {10.1145/3651140}
}
Kostenlos starten →