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 > FAIR

Tools: Print

Project: HyperTrac: Hypergraph Decompositions and Tractability

(funded by the Austrian Science Fund (FWF) under grant P30930)

Contents

Top

Project team

Project leader

Project staff

Project partners

Top

Goal of the Project

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.

Duration

The project started on 2018-06-01 and ended on 2022-11-30.

Top

Publications

2023

  1. 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  ]
  2. Timo Camillo Merkl, Reinhard Pichler, and Sebastian Skritek: Diversity of Answers to Conjunctive Queries. ICDT: 9:1-9:18, 2023.
    [ BibTeX | PDF  ]
  3. Lukas Grasmann, Reinhard Pichler, and Alexander Selzer: Integration of Skyline Queries into Spark SQL. EDBT: 337-350, 2023.
    [ BibTeX | PDF  ]
  4. Matthias Lanzinger: Tractability beyond β-acyclicity for conjunctive queries with negation and SAT. Theor. Comput. Sci., 942: 276-296, 2023.
    [ BibTeX | PDF  ]

2022

  1. 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  ]
  2. 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  ]
  3. Marta Bernardini, Matthias Lanzinger, Rosario Laurendi, and Stefano Sferrazza: Family Link Detection in Uncertain Settings with MV-Datalog±. EDBT/ICDT Workshops, 2022.
    [ BibTeX | PDF  ]
  4. 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  ]
  5. Georg Gottlob, Matthias Lanzinger, Cem Okulmus, and Reinhard Pichler: Fast Parallel Hypertree Decompositions in Logarithmic Recursion Depth. PODS: 325-336, 2022.
    [ BibTeX | PDF  ]
  6. 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  ]
  7. Matthias Lanzinger, Stefano Sferrazza, and Georg Gottlob: New Perspectives for Fuzzy Datalog (Extended Abstract). Datalog: 42-47, 2022.
    [ BibTeX | PDF  ]
  8. 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

  1. 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  ]
  2. 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  ]
  3. 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  ]
  4. Matthias Lanzinger: Tractability Beyond β-Acyclicity for Conjunctive Queries with Negation. PODS: 355-369, 2021.
    [ BibTeX | PDF  ]
  5. 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

  1. 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  ]
  2. 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  ]
  3. 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  ]
  4. 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  ]
  5. 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  ]
  6. Georg Gottlob, Cem Okulmus, and Reinhard Pichler: Fast and Parallel Decomposition of Constraint Satisfaction Problems. IJCAI: 1155-1162, 2020.
    [ BibTeX | PDF  ]

2019

  1. Leopoldo E. Bertossi, Georg Gottlob, and Reinhard Pichler: Datalog: Bag Semantics via Set Semantics. ICDT: 16:1-16:19, 2019.
    [ BibTeX | PDF  ]
  2. Nofar Carmeli, and Markus Kröll: On the Enumeration Complexity of Unions of Conjunctive Queries. PODS: 134-148, 2019.
    [ BibTeX | PDF  ]
  3. 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  ]
  4. Wolfgang Fischl, Georg Gottlob, Davide Mario Longo, and Reinhard Pichler: HyperBench: A Benchmark and Tool for Hypergraphs and Empirical Findings. AMW, 2019.
    [ BibTeX | PDF  ]
  5. 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  ]
  6. Georg Gottlob, Matthias Lanzinger, and Reinhard Pichler: Semantic Width Revisited (Extended Abstract). AMW, 2019.
    [ BibTeX | PDF  ]
  7. Georg Gottlob, Cem Okulmus, and Reinhard Pichler: Parallel Computation of Generalized Hypertree Decompositions. AMW, 2019.
    [ BibTeX | PDF  ]
  8. Stefan Mengel, and Sebastian Skritek: Characterizing Tractability of Simple Well-Designed Pattern Trees with Projection. ICDT: 20:1-20:18, 2019.
    [ BibTeX | PDF  ]
  9. 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  ]
  10. Sebastian Skritek: Towards Reconciling Certain Answers and SPARQL: Bag Semantics to the Rescue?. AMW, 2019.
    [ BibTeX | PDF  ]

2018

  1. Theresa Csar, Martin Lackner, and Reinhard Pichler: Computing the Schulze Method for Large-Scale Preference Data Sets. IJCAI: 180-187, 2018.
    [ BibTeX | PDF  ]
  2. Wolfgang Fischl, Georg Gottlob, and Reinhard Pichler: General and Fractional Hypertree Decompositions: Hard and Easy Cases (extended abstract). AMW, 2018.
    [ BibTeX | PDF  ]
  3. Wolfgang Fischl, Georg Gottlob, and Reinhard Pichler: General and Fractional Hypertree Decompositions: Hard and Easy Cases. PODS: 17-32, 2018.
    [ BibTeX | PDF  ]
  4. 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: 2023-03-13 21:01

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