Project: HyperTrac: Hypergraph Decompositions and Tractability
(funded by the Austrian Science Fund (FWF) under grant P30930)
Project leader
Project staff
Project partners
Answering Conjunctive Queries (CQs) as well as solving Constraint
Satisfaction Problems (CSPs) are fundamental tasks in Computer
Science. Due to their inherent complexity (they are classical
NP-complete problems), the search for tractable fragments of these
problems has been an active research area for many years. Hypertree
decompositions (HDs) and their generalizations to generalized
hypertree decompositions (GHDs) and fractional hypertree
decompositions (FHDs) allow us to define the widest tractable classes
of CQs and CSPs known to date. These techniques have been successfully
applied to CSP solving and have meanwhile also been integrated into
commercial database systems.
However, the computation of an appropriate HD, GHD, or FHD is itself a
demanding problem. Algorithms for this task exist, but they do not
scale: The complexity of computing an optimal HD or deciding if an HD
of a given width exists increases exponentially with the width of the
given CQ or CSP. We have recently shown that the problems of deciding
if a GHD or FHD of a given width exists are NP-complete even for width
2. Therefore, intensive further research on algorithms for computing
HDs, GHDs, and FHDs is required.
In this project, we will tackle the problem of computing HDs, GHDs, and FHDs both from a theoretical
and practical point of view. For HDs, we aim at new algorithmic approaches to reduce the exponential
dependency on the width. For GHDs and FHDs, we aim at identifying natural classes of CQs and CSPs for
which the computation of a GHD or FHD of desired width is tractable. From a theoretical perspective, our
goal is thus an improvement of worst-case complexity bounds. From a practical perspective, our goal is the
development and implementation of algorithms that work well on real-world problem instances.
The project started on 2018-06-01 and ended on 2022-11-30.
2023
-
Georg Gottlob, Matthias Lanzinger, Davide Mario Longo, and Cem Okulmus: Incremental Updates of Generalized Hypertree Decompositions. ACM J. Exp. Algorithmics, 27(1.16): 1-28, 2023.
[ BibTeX | PDF ] -
Timo Camillo Merkl, Reinhard Pichler, and Sebastian Skritek: Diversity of Answers to Conjunctive Queries. ICDT: 9:1-9:18, 2023.
[ BibTeX | PDF ] -
Lukas Grasmann, Reinhard Pichler, and Alexander Selzer: Integration of Skyline Queries into Spark SQL. EDBT: 337-350, 2023.
[ BibTeX | PDF ] -
Matthias Lanzinger: Tractability beyond β-acyclicity for conjunctive queries with negation and SAT. Theor. Comput. Sci., 942: 276-296, 2023.
[ BibTeX | PDF ]
2022
-
Mahmoud Abo Khamis, Hung Q. Ngo, Reinhard Pichler, Dan Suciu, and Yisu Remy Wang: Datalog in Wonderland. SIGMOD Rec., 51 (2): 6-17, 2022.
[ BibTeX | PDF ] -
Mahmoud Abo Khamis, Hung Q. Ngo, Reinhard Pichler, Dan Suciu, and Yisu Remy Wang: Convergence of Datalog over (Pre-) Semirings. PODS: 105-117, 2022.
[ BibTeX | PDF ] -
Marta Bernardini, Matthias Lanzinger, Rosario Laurendi, and Stefano Sferrazza: Family Link Detection in Uncertain Settings with MV-Datalog±. EDBT/ICDT Workshops, 2022.
[ BibTeX | PDF ] -
Georg Gottlob, Cem Okulmus, and Reinhard Pichler: Fast and parallel decomposition of constraint satisfaction problems. Constraints An Int. J., 27 (3): 284-326, 2022.
[ BibTeX | PDF ] -
Georg Gottlob, Matthias Lanzinger, Cem Okulmus, and Reinhard Pichler: Fast Parallel Hypertree Decompositions in Logarithmic Recursion Depth. PODS: 325-336, 2022.
[ BibTeX | PDF ] -
Matthias Lanzinger, Stefano Sferrazza, and Georg Gottlob: MV-Datalog+-: Effective Rule-based Reasoning with Uncertain Observations. Theory Pract. Log. Program., 22 (5): 678-692, 2022.
[ BibTeX | PDF ] -
Matthias Lanzinger, Stefano Sferrazza, and Georg Gottlob: New Perspectives for Fuzzy Datalog (Extended Abstract). Datalog: 42-47, 2022.
[ BibTeX | PDF ] -
Yisu Remy Wang, Mahmoud Abo Khamis, Hung Q. Ngo, Reinhard Pichler, and Dan Suciu: Optimizing Recursive Queries with Progam Synthesis. SIGMOD: 79-93, 2022.
[ BibTeX | PDF ]
2021
-
Nofar Carmeli, and Markus Kröll: On the Enumeration Complexity of Unions of Conjunctive Queries. ACM Trans. Database Syst., 46 (2): 5:1-5:41, 2021.
[ BibTeX | PDF ] -
Wolfgang Fischl, Georg Gottlob, Davide Mario Longo, and Reinhard Pichler: HyperBench: A Benchmark and Tool for Hypergraphs and Empirical Findings. ACM J. Exp. Algorithmics, 26(1.6): 1-40, 2021.
[ BibTeX | PDF ] -
Georg Gottlob, Matthias Lanzinger, Reinhard Pichler, and Igor Razgon: Complexity Analysis of Generalized and Fractional Hypertree Decompositions. J. ACM, 68 (5): 38:1-38:50, 2021.
[ BibTeX | PDF ] -
Matthias Lanzinger: Tractability Beyond β-Acyclicity for Conjunctive Queries with Negation. PODS: 355-369, 2021.
[ BibTeX | PDF ] -
Stefan Mengel, and Sebastian Skritek: Characterizing Tractability of Simple Well-Designed Pattern Trees with Projection. Theory Comput. Syst., 65 (1): 3-41, 2021.
[ BibTeX | PDF ]
2020
-
Manuel Bichler, Michael Morak, and Stefan Woltran: selp: A Single-Shot Epistemic Logic Program Solver. Theory Pract. Log. Program., 20 (4): 435-455, 2020.
[ BibTeX | PDF ] -
Bernhard Bliem, Michael Morak, Marius Moldovan, and Stefan Woltran: The Impact of Treewidth on Grounding and Solving of Answer Set Programs. J. Artif. Intell. Res., 67: 35-80, 2020.
[ BibTeX | PDF ] -
Hubie Chen, Georg Gottlob, Matthias Lanzinger, and Reinhard Pichler: Semantic Width and the Fixed-Parameter Tractability of Constraint Satisfaction Problems. IJCAI: 1726-1733, 2020.
[ BibTeX | PDF ] -
Georg Gottlob, Matthias Lanzinger, Davide Mario Longo, Cem Okulmus, and Reinhard Pichler: The HyperTrac Project: Recent Progress and Future Research Directions on Hypergraph Decompositions. CPAIOR: 3-21, 2020.
[ BibTeX | PDF ] -
Georg Gottlob, Matthias Lanzinger, Reinhard Pichler, and Igor Razgon: Fractional Covers of Hypergraphs with Bounded Multi-Intersection. MFCS: 41:1-41:14, 2020.
[ BibTeX | PDF ] -
Georg Gottlob, Cem Okulmus, and Reinhard Pichler: Fast and Parallel Decomposition of Constraint Satisfaction Problems. IJCAI: 1155-1162, 2020.
[ BibTeX | PDF ]
2019
-
Leopoldo E. Bertossi, Georg Gottlob, and Reinhard Pichler: Datalog: Bag Semantics via Set Semantics. ICDT: 16:1-16:19, 2019.
[ BibTeX | PDF ] -
Nofar Carmeli, and Markus Kröll: On the Enumeration Complexity of Unions of Conjunctive Queries. PODS: 134-148, 2019.
[ BibTeX | PDF ] -
Nadia Creignou, Markus Kröll, Reinhard Pichler, Sebastian Skritek, and Heribert Vollmer: A complexity theory for hard enumeration problems. Discret. Appl. Math., 268: 191-209, 2019.
[ BibTeX | PDF ] -
Wolfgang Fischl, Georg Gottlob, Davide Mario Longo, and Reinhard Pichler: HyperBench: A Benchmark and Tool for Hypergraphs and Empirical Findings. AMW, 2019.
[ BibTeX | PDF ] -
Wolfgang Fischl, Georg Gottlob, Davide Mario Longo, and Reinhard Pichler: HyperBench: A Benchmark and Tool for Hypergraphs and Empirical Findings. PODS: 464-480, 2019.
[ BibTeX | PDF ] -
Georg Gottlob, Matthias Lanzinger, and Reinhard Pichler: Semantic Width Revisited (Extended Abstract). AMW, 2019.
[ BibTeX | PDF ] -
Georg Gottlob, Cem Okulmus, and Reinhard Pichler: Parallel Computation of Generalized Hypertree Decompositions. AMW, 2019.
[ BibTeX | PDF ] -
Stefan Mengel, and Sebastian Skritek: Characterizing Tractability of Simple Well-Designed Pattern Trees with Projection. ICDT: 20:1-20:18, 2019.
[ BibTeX | PDF ] -
Liat Peterfreund, Dominik D. Freydenberger, Benny Kimelfeld, and Markus Kröll: Complexity Bounds for Relational Algebra over Document Spanners. PODS: 320-334, 2019.
[ BibTeX | PDF ] -
Sebastian Skritek: Towards Reconciling Certain Answers and SPARQL: Bag Semantics to the Rescue?. AMW, 2019.
[ BibTeX | PDF ]
2018
-
Theresa Csar, Martin Lackner, and Reinhard Pichler: Computing the Schulze Method for Large-Scale Preference Data Sets. IJCAI: 180-187, 2018.
[ BibTeX | PDF ] -
Wolfgang Fischl, Georg Gottlob, and Reinhard Pichler: General and Fractional Hypertree Decompositions: Hard and Easy Cases (extended abstract). AMW, 2018.
[ BibTeX | PDF ] -
Wolfgang Fischl, Georg Gottlob, and Reinhard Pichler: General and Fractional Hypertree Decompositions: Hard and Easy Cases. PODS: 17-32, 2018.
[ BibTeX | PDF ] -
Pablo Barceló, Markus Kröll, Reinhard Pichler, and Sebastian Skritek: Efficient Evaluation and Static Analysis for Well-Designed Pattern Trees with Projection. ACM Trans. Database Syst., 43 (2): 8:1-8:44, 2018.
[ BibTeX | PDF ]
Top
Last updated: 2024-03-26 10:31