Abstract
Recursive graph queries are increasingly popular for extracting information from interconnected data found in various domains such as social networks, life sciences, and business analytics. Graph data often come with schema information that describe how nodes and edges are organized. We propose a type inference mechanism that enriches recursive graph queries with relevant structural information contained in a graph schema. We show that this schema information can be useful in order to improve the performance when evaluating recursive graph queries. Furthermore, we prove that the proposed method is sound and complete, ensuring that the semantics of the query is preserved during the schema-enrichment process.
Topics

No keywords indexed for this article. Browse by subject →

References
112
[1]
Abdullah Abbas, Pierre Genevès, Cécile Roisin, and Nabil Layaïda. 2017. Optimising SPARQL query evaluation in the presence of shex constraints. In BDA 2017--33ème conférence sur la «Gestion de Données-Principes, Technologies et Applications». 1--12.
[3]
Zahid Abul-Basher, Nikolay Yakovets, Parke Godfrey, Shadi Ghajar-Khosravi, and Mark H Chignell. 2017. Tasweet: optimizing disjunctive regular path queries in graph databases. In EDBT/ICDT 2017 Joint Conference 20th International Conference on Extending Database Technology. 470--473.
[16]
Gordon Bell, Tony Hey, and Alex Szalay. 2009. Beyond the data deluge. Science 323, 5919 (2009), 1297--1298.
[17]
Luigi Bellomarini Andrea Gentili Eleonora Laurenza and Emanuel Sallinger. 2022. Model-Independent Design of Knowledge Graphs-Lessons Learnt From Complex Financial Graphs.. In EDBT. 2--524.
[19]
Véronique Benzaken, Giuseppe Castagna, Dario Colazzo, and Kim Nguyen. 2006. Type-Based XML Projection.. In VLDB, Vol. 6. 271--282.
[24]
Angela Bonifati, Stefania Dumbrava, Emile Martinez, and Nicolas Mir. 2023. The Quest for Schemas in Graph Databases. Looking Ahead 4 (2023), 5.
[40]
Melisachew Wudage Chekol, Jérôme Euzenat, Pierre Genevès, and Nabil Layaïda. 2012. SPARQL query containment under SHI axioms. In Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 26. 10--16.
[46]
Alin Deutsch and Val Tannen. 2001. Optimization properties for classes of conjunctive regular path queries. In International Workshop on Database Programming Languages. Springer, 21--39.

Showing 50 of 112 references

Metrics
2
Citations
112
References
Details
Published
Feb 10, 2025
Vol/Issue
3(1)
Pages
1-29
License
View
Funding
ANR Award: ANR-23-CE23-0010
Cite This Article
Chandan Sharma, Pierre Genevès, Nils Gesbert, et al. (2025). Schema-Based Query Optimisation for Graph Databases. Proceedings of the ACM on Management of Data, 3(1), 1-29. https://doi.org/10.1145/3709722