Skip to Content

TU Wien Fakultät für Informatik DBAI Database and Artificial Intelligence Group
Top-level Navigation: Current-level Navigation:

Path: DBAI > Research > Projects > DeConquer

Tools: Print

Decompose and Conquer: Fast Query Processing via Decomposition

(funded by the WWTF under grant ICT22-011)

Contents

Project team

PI

Co-PIs

Current project staff

Former 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 March 01, 2023 and is running until August 31, 2027.

Publications

  1. Aleksandar Pavlovic and Emanuel Sallinger. 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 | Paper]
  2. Timo Camillo Merkl, Reinhard Pichler and Sebastian Skritek. 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 | Paper ]
  3. Matthias Lanzinger, Markus Nissl, Emanuel Sallinger and Przemyslaw Andrzej Walega. 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: 3277-3285, ijcai.org, 2023.
    [ BibTeX | Paper ]
  4. René Heinzl, Markus Nissl and Emanuel Sallinger. 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 | Paper ]
  5. Georg Gottlob, Matthias Lanzinger, Reinhard Pichler and Igor Razgon. Fractional covers of hypergraphs with bounded multi-intersection. In Theor. Comput. Sci. 979: 114204, 2023.
    [ BibTeX | Paper ]
  6. Georg Gottlob, Matthias Lanzinger, Davide Mario Longo, Cem Okulmus, Reinhard Pichler and Alexander Selzer. 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 | Paper ]
  7. Renzo Angles, Georg Gottlob, Aleksandar Pavlovic, Reinhard Pichler and Emanuel Sallinger. SparqLog: A System for Efficient Evaluation of SPARQL 1.1 Queries via Datalog. In Proc. VLDB Endow., 16 (13): 4240-4253, 2023.
    [ BibTeX | Paper]
  8. Mahmoud Abo Khamis, Hung Q. Ngo, Reinhard Pichler, Dan Suciu and Yisu Remy Wang. Convergence of Datalog over (Pre-) Semirings. In SIGMOD Rec., 52 (1): 75-82, 2023.
    [ BibTeX | Paper ]
  9. Matthias Lanzinger and Igor Razgon. 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: 48:1-48:17.
    [ BibTeX | Paper ]
  10. Teodoro Baldazzi, Luigi Bellomarini, Marco Favorito and Emanuel Sallinger. 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: 169-185, Springer, Lecture Notes in Computer Science 14512, 2024.
    [ BibTeX | Paper ]
  11. Shqiponja Ahmetaj, Timo Merkl and Reinhard Pichler. Consistent Query Answering over SHACL Constraints (Extended Abstract). In Proceedings of the 16th Alberto Mendelzon International Workshop on Foundations of Data Management (AMW 2024), Mexico City, Mexico, October 2-4, 2024.
    [ BibTeX | Paper ]
  12. Shqiponja Ahmetaj, Timo Merkl and Reinhard Pichler. Consistent Query Answering over SHACL Constraints. In Proceedings of the 21st International Conference on Principles of Knowledge Representation and Reasoning, KR 2024, Hanoi, Vietnam. November 2-8, 2024.
    [ BibTeX | Paper ]
  13. Marcelo Arenas, Timo Camillo Merkl, Reinhard Pichler and Cristian Riveros. Towards Tractability of the Diversity of Query Answers: Ultrametrics to the Rescue. In Proc. ACM Manag. Data 2(5): 215:1-215:26, 2024.
    [ BibTeX | Paper ]
  14. Teodoro Baldazzi, Luigi Bellomarini, Stefano Ceri, Andrea Colombo, Andrea Gentili and Emanuel Sallinger. "Please, Vadalog, tell me why": Interactive Explanation of Datalog-based Reasoning. In Proceedings 27th International Conference on Extending Database Technology, EDBT 2024, Paestum, Italy, March 25 - March 28: 834-837.
    [ BibTeX | Paper ]
  15. Teodoro Baldazzi, Luigi Bellomarini, Stefano Ceri, Andrea Colombo, Andrea Gentili, Emanuel Sallinger and Paolo Atenzi. Explaining Enterprise Knowledge Graphs with Large Language Models and Ontological Reasoning. In The Provenance of Elegance in Computation - Essays Dedicated to Val Tannen, Tannen's Festschrift, University of Pennsylvania, Philadelphia, PA, USA, May 24-25, 2024: 1:1-1:20.
    [ BibTeX | Paper ]
  16. Teodoro Baldazzi, Luigi Bellomarini, Marco Favorito and Emanuel Sallinger. 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: 169-185.
    [ BibTeX | Paper ]
  17. Luigi Bellomarini, Davide Benedetto, Matteo Brandetti, Emanuel Sallinger and Adriano Vlad. The Vadalog Parallel System: Distributed Reasoning with Datalog+/-. In Proc. VLDB Endow. 17(13), 2024: 4614-4626.
    [ BibTeX | Paper ]
  18. Andrea Colombo, Teodoro Baldazzi, Luigi Bellomarini, Andrea Gentili and Emanuel Sallinger. LLM-based DatalogMTL Modelling of MiCAR-compliant Crypto-Assets Markets. In Proceedings 5th International Workshop on the Resurgence of Datalog in Academia and Industry (Datalog-2.0 2024) co-located with the 17th International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR 2024), Dallas, Texas, USA, October 11, 2024: 17-22.
    [ BibTeX | Paper ]
  19. Georg Gottlob, Matthias Lanzinger, Cem Okulmus and Reinhard Pichler. Fast Parallel Hypertree Decompositions in Logarithmic Recursion Depth. In ACM Trans. Database Syst. 49(1): 1:1-1:43, 2024.
    [ BibTeX | Paper ]
  20. Matthias Lanzinger and Igor Razgon. 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: 48:1-48:17, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, LIPIcs 289, 2024.
    [ BibTeX | Paper ]
  21. Emily Jin, Michael M. Bronstein, Ismail Ilkan Ceylan and Matthias Lanzinger. Homomorphism Counts for Graph Neural Networks: All About That Basis. In Forty-first International Conference on Machine Learning, ICML 2024, Vienna, Austria, July 21-27, 2024: 22075-22098.
    [ BibTeX | Paper ]
  22. Mahmoud Abo Khamis, Hung Q. Ngo, Reinhard Pichler, Dan Suciu and Yisu Remy Wang. Convergence of datalog over (Pre-) Semirings. In J. ACM 71(2) 8:1-8:55, 2024.
    [ BibTeX | Paper ]
  23. Matthias Lanzinger and Pablo Barceló. On the Power of the Weisfeiler-Leman Test for Graph Motif Parameters. In The Twelfth International Conference on Learning Representations, ICLR 2024, Vienna, Austria, May 7-11, 2024.
    [ BibTeX | Paper ]
  24. Matthias Lanzinger, Reinhard Pichler and Alexander Selzer. Avoiding Materialisation for Guarded Aggregate Queries. In Proceedings of the 16th Alberto Mendelzon International Workshop on Foundations of Data Management (AMW 2024), Mexico City, Mexico, October 2-4, 2024.
    [ BibTeX | Paper ]
  25. Matthias Lanzinger, Stefano Sferrazza, Przemyslaw Andrzej Walega and Georg Gottlob. Fuzzy Datalog over Arbitrary t-Norms. In LPAR 2024: Proceedings of 25th Conference on Logic for Programming, Artificial Intelligence and Reasoning, Port Louis, Mauritius, May 26-31, 2024: 426-444.
    [ BibTeX | Paper ]
  26. Aleksandar Pavlovic and Emanuel Sallinger. SpeedE: Euclidean Geometric Knowledge Graph Embedding Strikes Back. In Findings of the Association for Computational Linguistics: NAACL 2024, Mexico City, Mexico, June 16-21, 2024: 69-92.
    [ BibTeX | Paper ]
  27. Andrea Colombo, Teodoro Baldazzi, Luigi Bellomarini, Emanuel Sallinger and Stefano Ceri. Template-based Explainable Inference over High-Stakes Financial Knowledge Graphs. In Proceedings 28th International Conference on Extending Database Technology, EDBT 2025, Barcelona, Spain, March 25-28, 2025: 503-515.
    [ BibTeX | Paper ]
  28. Matthias Lanzinger, Cem Okulmus, Reinhard Pichler, Alexander Selzer and Georg Gottlob. Soft and Constrained Hypertree Width. In Proc. ACM Manag. Data 3(2): 114:1-114:25, 2025.
    [ BibTeX | Paper ]
  29. Matthias Lanzinger, Reinhard Pichler and Alexander Selzer. Avoiding Materialisation for Guarded Aggregate Queries. In Proc. VLDB Endow. 18(5): 1398-1411, 2025.
    [ BibTeX | Paper ]
  30. David Lobo, Jesús Medina, Timo Camillo Merkl and Reinhard Pichler. Minimal solutions of fuzzy relation equations via maximal independent elements. In Inf. Sci. 690: 121558, 2025.
    [ BibTeX | Paper ]
  31. Timo Camillo Merkl, Reinhard Pichler and Sebastian Skritek. Diversity of Answers to Conjunctive Queries. In Log. Methods Comput. Sci. 21(1), 2025.
    [ BibTeX | Paper ]
  32. Shqiponja Ahmetaj, Robert David, Axel Polleres and Mantas Simkus. A Logic Programming Approach to Repairing SHACL Constraint Violations. In TGDK 3(3): 1:1-1:36, 2025.
    [ BibTeX | Paper ]
  33. Marcelo Arenas, Timo Camillo Merkl, Reinhard Pichler and Cristian Riveros. Query Answering Under Volume-Based Diversity Functions. In Proc. ACM Manag. Data 3(5): 281:1-281:18, 2025.
    [ BibTeX | Paper ]
  34. Linus Bao, Emily Jin, Michael M. Bronstein, Ismail Ilkan Ceylan and Matthias Lanzinger. Homomorphism Counts as Structural Encodings for Graph Learning. In The Thirteenth International Conference on Learning Representations, ICLR 2025, Singapore, April 24-28, 2025.
    [ BibTeX | Paper ]
  35. Luigi Bellomarini, Livia Blasi, Andrea Gentili, Rosario Laurendi, Eleonora Laurenza and Emanuel Sallinger. The Joint Knowledge Graph Labs: Neuro-Symbolic Reasoning in Action. In Companion Proceedings of the 9th International Joint Conference on Rules and Reasoning, RuleML+RR 2025, also co-located with 21th Reasoning Web Summer School, RW 2025, and 17th DecisionCAMP 2025 as part of Declarative AI 2025, Istanbul, Türkiye, September 22-24, 2025.
    [ BibTeX | Paper ]
  36. Luigi Bellomarini, Livia Blasi, Markus Nissl and Emanuel Sallinger. The Temporal Vadalog System: Temporal Datalog-Based Reasoning. In Theory Pract. Log. Program. 25(2): 168-196, 2025.
    [ BibTeX | Paper ]
  37. Luigi Bellomarini, Andrea Gentili, Davide Magnanimi and Emanuel Sallinger. Vadacode: A Logician-friendly IDE for Datalog+/-. In Proc. VLDB Endow. 18(12): 5411-5414, 2025.
    [ BibTeX | Paper ]
  38. Davide Benedetto, Marco Calautti, Hebatalla Hammad, Emanuel Sallinger and Adriano Vlad-Starrabba. A Datalog Rewriting Algorithm for Warded Ontologies. In Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence, IJCAI 2025, Montreal, Canada, August 16-22, 2025: 4356-4364.
    [ BibTeX | Paper ]
  39. Andrea Colombo, Teodoro Baldazzi, Luigi Bellomarini, Emanuel Sallinger and Stefano Ceri. Template-based Explainable Inference over High-Stakes Financial Knowledge Graphs. In Proceedings 28th International Conference on Extending Database Technology, EDBT 2025, Barcelona, Spain, March 25-28, 2025: 503-515.
    [ BibTeX | Paper ]
  40. Kyle Deeds and Timo Camillo Merkl. Partition Constraints for Conjunctive Queries: Bounds and Worst-Case Optimal Joins. In 28th International Conference on Database Theory, ICDT 2025, Barcelona, Spain, March 25-28, 2025: 17:1-17:18.
    [ BibTeX | Paper ]
  41. Kyle Deeds, Timo Camillo Merkl, Reinhard Pichler and Dan Suciu. The Space-Time Complexity of Sum-Product Queries. In Proc. ACM Manag. Data 3(5): 283:1-283:21, 2025.
    [ BibTeX | Paper ]
  42. Jinghao Hu, Jinsong Guo, Chen Luo, Yang Hu, Matthias Lanzinger and Zhanshan Li. Enabling Generalized Zero-Shot Vulnerability Classification. In IEEE Trans. Dependable Secur. Comput. 22(4): 3465-3482, 2025.
    [ BibTeX | Paper ]
  43. Matthias Lanzinger, Cem Okulmus, Reinhard Pichler, Alexander Selzer and Georg Gottlob. Soft and Constrained Hypertree Width. In Proc. ACM Manag. Data 3(2): 114:1-114:25, 2025.
    [ BibTeX | Paper ]
  44. Aleksandar Pavlovic, Emanuel Sallinger and Steven Schockaert. Faithful Differentiable Reasoning with Reshuffled Region-based Embeddings. In Proceedings of the 22nd International Conference on Principles of Knowledge Representation and Reasoning, KR 2025, Melbourne, Australia, November 1-17, 2025.
    [ BibTeX | Paper ]
  45. Pablo Barceló, Floris Geerts, Matthias Lanzinger, Klara Pakhomenko and Jan Van den Bussche. A Logical View of GNN-Style Computation and the Role of Activation Functions. Accepted for publication at PODS 2026.
    [ BibTeX | Paper ]
  46. Christian Fattebert, Zhekai Jiang, Christoph Koch, Reinhard Pichler and Qichen Wang. Size Bound-Adorned Datalog. Accepted for publication at PODS 2026.
    [ BibTeX | Paper ]
  47. Matthias Lanzinger and Igor Razgon. FPT Approximation of Generalised Hypertree Width for Bounded Intersection Hypergraphs. In ACM Trans. Comput. Theory 18(2): 12:1-12:34, 2026.
    [ BibTeX | Paper ]
  48. Matthias Lanzinger, Igor Razgon and Daniel Unterberger. FPT Parameterisations of Fractional and Generalised Hypertree Width. Accepted for publication at PODS 2026.
    [ BibTeX | Paper ]
  49. Daniela Böhm, Georg Gottlob, Matthias Lanzinger, Davide Mario Longo, Cem Okulmus, Reinhard Pichler and Alexander Selzer. Selective Use of Yannakakis' Algorithm for Consistent Performance Gains. In DOLAP 2026, 18-33.
    [ BibTeX | Paper ]
  50. Nadia Creignou, Timo Camillo Merkl, Reinhard Pichler and Daniel Unterberger. From FPT Decision to FPT Enumeration. In FoIKS 2026: 213-231.
    [ BibTeX | Paper ]
  51. Kyle Deeds, Timo Camillo Merkl, Reinhard Pichler and Dan Suciu. Query Decompositions and All That (Invited Talk). In ICDT 2026, 1:1-1:20.
    [ BibTeX | Paper ]
  52. Matthias Lanzinger, Reinhard Pichler and Alexander Selzer. Database Theory in Action: Evaluation of Aggregate Queries Without Materialisation. In ICDT 2026, 24:1-24:5.
    [ BibTeX | Paper ]
 Top
Last updated: 2024-03-24 14:16

Home / Kontakt / Webmaster / Offenlegung gemäß § 25 Mediengesetz: Inhaber der Website ist das Institut für Logic and Computation an der Technischen Universität Wien, 1040 Wien. Die TU Wien distanziert sich von den Inhalten aller extern gelinkten Seiten und übernimmt diesbezüglich keine Haftung. Disclaimer / Datenschutzerklärung