The µ-RA System for Recursive Path Queries over Graphs
Pages 5041 - 5045
Abstract
We demonstrate a system for recursive query answering over graphs. The system is based on a complete implementation of the recursive relational algebra µ-RA, extended with parsers and compilers adapted for queries over knowledge and property graphs. Each component of the system comes with novelty for processing recursion. As a result, one can formulate, optimize and efficiently answer expressive queries that navigate recursively along paths in different types of graphs. We demonstrate the system on real datasets and show how it performs considering other state-of-the-art systems.
References
[1]
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. https://doi. org/10.5441/002/edbt.
[2]
Almond. 2023. Almond : A Scala kernel for Jupyter. https://almond.sh/.
[3]
Molham Aref, Balder ten Cate, Todd J. Green, Benny Kimelfeld, Dan Olteanu, Emir Pasalic, Todd L. Veldhuizen, and Geoffrey Washburn. 2015. Design and Implementation of the LogicBlox System. In Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data (Melbourne, Victoria, Australia) (SIGMOD '15). ACM, New York, NY, USA, 1371--1382. https://doi.org/10.1145/2723372.2742796
[4]
Sarah Chlyah. 2022. On Algebraic Foundations for the Optimization of Iterative Programming with Distributed Data Collections. (Fondements algé briques pour l'optimisation de la programmation ité rative avec des collections de donné es distribué es). Ph.,D. Dissertation. Grenoble Alpes University, France. https://tel.archives-ouvertes.fr/tel-03783672
[5]
Sarah Chlyah, Pierre Genevès, and Nabil Layaïda. 2021. Distributed Evaluation of Graph Queries using Recursive Relational Algebra. arxiv: 2111.12487 [cs.DB]
[6]
Amela Fejza. 2023 a. Accompanying video for the paper “The μ-RA System for Recursive Path Queries Over Graphs”. https://shorturl.at/AXZ23
[7]
Amela Fejza. 2023 b. On the Optimization of Recursive Plan Enumeration with an Application to Property Graph Queries. (Sur l'optimisation de l'é numé ration de plans ré cursifs avec une application aux requê tes de graphes de proprié té s). Ph.,D. Dissertation. Grenoble Alpes University, France. https://tel.archives-ouvertes.fr/tel-04128256
[8]
Amela Fejza, Pierre Genevès, and Nabil Layaïda. 2023. Efficient Enumeration of Recursive Plans in Transformation-based Query Optimizers. (Jan. 2023). https://hal.inria.fr/hal-03692274 preprint.
[9]
Michael Fire and Yuval Elovici. 2015. Data mining of online genealogy datasets for revealing lifespan patterns in human population. ACM Transactions on Intelligent Systems and Technology (TIST), Vol. 6, 2 (2015), 28.
[10]
Max Planck Institute for Informatics and Telecom ParisTech University. 2019. YAGO: A high-quality knowledge base. https://www.mpi-inf.mpg.de/yago-naga/yago/.
[11]
Nadime Francis, Alastair Green, Paolo Guagliardo, Leonid Libkin, Tobias Lindaaker, Victor Marsault, Stefan Plantikow, Mats Rydberg, Petra Selmer, and Andrés Taylor. 2018. Cypher: An Evolving Query Language for Property Graphs. In Proceedings of the 2018 International Conference on Management of Data (Houston, TX, USA) (SIGMOD '18). New York, NY, USA, 1433--1445. https://doi.org/10.1145/3183713.3190657
[12]
Louis Jachiet, Pierre Genevès, Nils Gesbert, and Nabil Layaïda. 2020. On the Optimization of Recursive Relational Queries: Application to Graph Queries. In Proceedings of the ACM SIGMOD International Conference on Management of Data. 681--697. https://doi.org/10.1145/3318464.3380567
[13]
Muideen Lawal. 2021. On Cost Estimation for the Recursive Relational Algebra. (Sur l'estimation des coû ts pour l'algè bre relationnelle ré cursive). Ph.,D. Dissertation. Grenoble Alpes University, France. https://tel.archives-ouvertes.fr/tel-03322720
[14]
Muideen Lawal, Pierre Genevès, and Nabil Layaïda. 2020. A Cost Estimation Technique for Recursive Relational Algebra. In CIKM 2020 - 29th ACM International Conference on Information and Knowledge Management. Virtual Event, France, 1--4. https://doi.org/10.1145/3340531.3417460
[15]
Wilco v. Leeuwen, Thomas Mulder, Bram van de Wall, George Fletcher, and Nikolay Yakovets. 2022. AvantGraph Query Processing Engine. Proc. VLDB Endow., Vol. 15, 12 (aug 2022), 3698--3701. https://doi.org/10.14778/3554821.3554878
[16]
Nicola Leone, Gerald Pfeifer, Wolfgang Faber, Thomas Eiter, Georg Gottlob, Simona Perri, and Francesco Scarcello. 2006. The DLV System for Knowledge Representation and Reasoning. ACM Trans. Comput. Logic, Vol. 7, 3 (July 2006), 499--562. https://doi.org/10.1145/1149114.1149117
[17]
John D. Ramsdell. 2004. Datalog version 2.2, a lightweight deductive database system. http://www.ccs.neu.edu/home/ramsdell/tools/datalog/datalog.html (retrieved in october 2019).
[18]
Fabian M. Suchanek, Gjergji Kasneci, and Gerhard Weikum. 2007. Yago: A Core of Semantic Knowledge. In Proceedings of the 16th International Conference on World Wide Web (Banff, Alberta, Canada) (WWW '07). ACM, New York, NY, USA, 697--706. https://doi.org/10.1145/1242572.1242667
[19]
Jacopo Urbani, Ceriel J. H. Jacobs, and Markus Krö tzsch. 2016. VLog: A Column-Oriented Datalog System for Large Knowledge Graphs. In Proceedings of the ISWC 2016 Posters & Demonstrations Track co-located with 15th International Semantic Web Conference (ISWC 2016), Kobe, Japan, October 19, 2016. http://ceur-ws.org/Vol-1690/paper113.pdf
[20]
Domagoj Vrgoc, Carlos Rojas, Renzo Angles, Marcelo Arenas, Diego Arroyuelo, Carlos Buil Aranda, Aidan Hogan, Gonzalo Navarro, Cristian Riveros, and Juan Romero. 2021. MillenniumDB: a persistent, open-source, graph database. arXiv preprint arXiv:2111.01540 (2021).
[21]
Nikolay Yakovets, Parke Godfrey, and Jarek Gryz. 2015. WAVEGUIDE: Evaluating SPARQL Property Path Queries. In EDBT, Vol. 2015. 525--528.
Index Terms
- The µ-RA System for Recursive Path Queries over Graphs
Recommendations
Weighted path queries on semistructured databases
Path queries have been extensively used to query semistructured data, such as the Web and XML documents. In this paper we introduce weighted path queries, an extension of path queries enabling several classes of optimization problems (such as the ...
Asymptotic Determinacy of Path Queries Using Union-of-Paths Views
We consider the view-based query determinacy problem over graph databases for queries defined as unions of path queries. These queries select pairs of nodes in a graph that are connected through a path whose length falls in a given set. A view ...
Equivalence and minimization of conjunctive queries under combined semantics
ICDT '12: Proceedings of the 15th International Conference on Database TheoryThe problems of query containment, equivalence, and minimization are fundamental problems in the context of query processing and optimization. In their classic work [2] published in 1977, Chandra and Merlin solved the three problems for the language of ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
October 2023
5508 pages
ISBN:9798400701245
DOI:10.1145/3583780
- General Chairs:
- Ingo Frommholz,
- Frank Hopfgartner,
- Mark Lee,
- Michael Oakes,
- Program Chairs:
- Mounia Lalmas,
- Min Zhang,
- Rodrygo Santos
Copyright © 2023 ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].
Sponsors
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 21 October 2023
Check for updates
Author Tags
Qualifiers
- Short-paper
Conference
CIKM '23: The 32nd ACM International Conference on Information and Knowledge Management
October 21 - 25, 2023
Birmingham, United Kingdom
Acceptance Rates
Overall Acceptance Rate 1,861 of 8,427 submissions, 22%
Upcoming Conference
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 79Total Downloads
- Downloads (Last 12 months)49
- Downloads (Last 6 weeks)4
Reflects downloads up to 16 Nov 2024
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in