Decompose and Conquer: Fast Query Processing via Decomposition
(funded by the WWTF under grant ICT22-011)
Contents
Project team
PI
Co-PIs
- Shqiponja Ahmetaj
- Georg Gottlob (until December 2023)
- Matthias Lanzinger (starting January 2024)
Project staff
Local collaborators
Goal of the Project
A core task of database systems is to provide efficient querying facilities. As big queries (e.g., queries automatically generated by analytical tools) are becoming more and more common, new challenges arise for query optimization and evaluation. It has been observed that traditional cost-based query optimization reaches its limits: a significant shortcoming of this approach is that it does not pay sufficient attention to structural properties of the query.
Recently, considerable progress has been made in the area of (hyper-)graph based methods of decomposing queries. Here, the idea is to turn a query into an acyclic one by computing small joins involving only 2 or 3 relations. By a landmark result of Yannakakis, acyclic queries can be evaluated efficiently without the risk of any explosion of intermediate results. However, the big drawback of decomposition-based query answering is that it completely ignores relevant properties of the data such as statistics, dependencies, indexes, etc.
The goal of this project is to bring these two, so far isolated, paradigms together. The main research questions are concerned with (1) integrating cost-based optimization into query decompositions and (2) integrating query decompositions into today's query optimizers. By combining the strengths of the two approaches, we will pave the way for a new generation of query engines – leading to data management tools capable of dealing with "Big Data" and ‘Big Queries".
Duration
The project started on 01.03.2023 and is running until 31.08.2026.
Publications
- Building Bridges: Knowledge Graph Embeddings Respecting Logical Rules (short paper) In Proceedings of the 15th Alberto Mendelzon International Workshop on Foundations of Data Management (AMW 2023), Santiago de Chile, Chile, May 22-26, 2023, CEUR-WS.org, CEUR Workshop Proceedings 3409, 2023.
[ BibTeX ] - Diversity of Answers to Conjunctive Queries (short paper) In Proceedings of the 15th Alberto Mendelzon International Workshop on Foundations of Data Management (AMW 2023), Santiago de Chile, Chile, May 22-26, 2023, CEUR-WS.org, CEUR Workshop Proceedings 3409, 2023.
[ BibTeX ] - Temporal Datalog with Existential Quantification In Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence, IJCAI 2023, 19th-25th August 2023, Macao, SAR, China, pages 3277-3285, ijcai.org, 2023.
[ BibTeX ] - On the Power of the Weisfeiler-Leman Test for Graph Motif Parameters In CoRR, abs/2309.17053, 2023.
[ BibTeX | doi ] - FPT Approximation of Generalised Hypertree Width for Bounded Intersection Hypergraphs In 41st International Symposium on Theoretical Aspects of Computer Science, STACS 2024, March 12-14, 2024, Clermont-Ferrand, France, pages 48:1-48:17, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, LIPIcs 289, 2024.
[ BibTeX ] - Towards Efficient Annotation Databases (short paper) In Proceedings of the 15th Alberto Mendelzon International Workshop on Foundations of Data Management (AMW 2023), Santiago de Chile, Chile, May 22-26, 2023, CEUR-WS.org, CEUR Workshop Proceedings 3409, 2023.
[ BibTeX ] - Fractional covers of hypergraphs with bounded multi-intersection In Theor. Comput. Sci., 979: 114204, 2023.
[ BibTeX | doi ] - Reaching Back to Move Forward: Using Old Ideas to Achieve a New Level of Query Optimization (short paper) In Proceedings of the 15th Alberto Mendelzon International Workshop on Foundations of Data Management (AMW 2023), Santiago de Chile, Chile, May 22-26, 2023, CEUR-WS.org, CEUR Workshop Proceedings 3409, 2023.
[ BibTeX ] - Ontological Reasoning over Shy and Warded Datalog+/- for Streaming-Based Architectures In Practical Aspects of Declarative Languages - 26th International Symposium, PADL 2024, London, UK, January 15-16, 2024, Proceedings, pages 169-185, Springer, Lecture Notes in Computer Science 14512, 2024.
[ BibTeX ] - SparqLog: A System for Efficient Evaluation of SPARQL 1.1 Queries via Datalog In Proc. VLDB Endow., 16 (13): 4240-4253, 2023.
[ BibTeX ] - Convergence of Datalog over (Pre-) Semirings In SIGMOD Rec., 52 (1): 75-82, 2023.
[ BibTeX | doi ]