Schema-Based Query Optimisation for Graph Databases

Chandan Sharma; Pierre Genevès; Nils Gesbert; Nabil Layaïda

doi:10.1145/3709722

journal article Feb 10, 2025

Schema-Based Query Optimisation for Graph Databases

Chandan Sharma

Pierre Genevès

Nils Gesbert

Nabil Layaïda

Proceedings of the ACM on Management of Data Vol. 3 No. 1 pp. 1-29 · Association for Computing Machinery (ACM)

View at Publisher Save 10.1145/3709722

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.

[2]

10.1145/263661.263676

[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.

[4]

10.1109/32.42731

[5]

10.1109/icde51399.2021.00085

[6]

10.1145/3183713.3190654

[7]

10.1145/3104031

[8]

10.1145/3589778

[9]

10.1145/3448016.3457561

[10]

10.1109/access.2020.2993117

[11]

10.1145/2723372.2742796

[12]

10.1145/6012.15399

[13]

10.1145/3424908

[14]

10.1145/2448496.2448520

[15]

10.1137/s0097539798337716

[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.

[18]

10.1145/1346330.1346333

[19]

Véronique Benzaken, Giuseppe Castagna, Dario Colazzo, and Kim Nguyen. 2006. Type-Based XML Projection.. In VLDB, Vol. 6. 271--282.

[20]

10.1145/1055558.1055600

[21]

10.1145/3461837.3464687

[22]

10.1145/3604437.3604452

[23]

10.14778/3554821.3554867

[24]

Angela Bonifati, Stefania Dumbrava, Emile Martinez, and Nicolas Mir. 2023. The Quest for Schemas in Graph Databases. Looking Ahead 4 (2023), 5.

[25]

10.1007/978-3-031-01864-0

[26]

10.1007/978-3-030-33223-5_37

[27]

10.1007/s00778-019-00558-9

[28]

10.1145/3318464.3384684

[29]

10.1007/s00778-022-00732-6

[30]

10.1145/2463676.2463718

[31]

10.1016/j.datak.2004.12.003

[32]

10.1007/3-540-62222-5_55

[33]

10.1145/275487.275502

[34]

10.1006/jcss.2000.1710

[35]

10.1007/3-540-44543-9_13

[36]

10.1145/275487.275504

[37]

10.1145/303976.303996

[38]

10.1016/j.tcs.2004.10.031

[39]

10.1145/78922.78924

[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.

[41]

10.1007/s13740-018-0087-1

[42]

10.1145/2815072.2815082

[43]

10.1145/2745754.2745766

[44]

10.1145/1376916.1376957

[45]

10.1145/3514221.3526057

[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.

[47]

10.1016/s0743-1066(99)00025-4

[48]

10.1145/2723372.2742786

[49]

10.1145/3583780.3614756

[50]

10.1109/icde.1998.655753

Showing 50 of 112 references

Metrics

2

Citations

112

References

Details

Published: Feb 10, 2025
Vol/Issue: 3(1)
Pages: 1-29
License: View

Authors

C

Chandan Sharma

Tyrex team, Univ. Grenoble Alpes, CNRS, Inria, Grenoble INP, LIG, Grenoble, France

P

Pierre Genevès

Tyrex team, Univ. Grenoble Alpes, CNRS, Inria, Grenoble INP, LIG, Grenoble, France

N

Nils Gesbert

Tyrex team, Univ. Grenoble Alpes, CNRS, Inria, Grenoble INP, LIG, Grenoble, France

N

Nabil Layaïda

Tyrex team, Univ. Grenoble Alpes, CNRS, Inria, Grenoble INP, LIG, Grenoble, France

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

Schema-Based Query Optimisation for Graph Databases

You May Also Like