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 has officially started on 2018-06-01 and has a duration of four years.

Top

Publications

  1. Georg Gottlob, Matthias Lanzinger, Davide Mario Longo, Cem Okulmus and Reinhard Pichler The HyperTrac Project: Recent Progress and Future Research Directions on Hypergraph Decompositions In CPAIOR, pages 3-21, Springer, Lecture Notes in Computer Science 12296, 2020.
    [ BibTeX ]
  2. Hubie Chen, Georg Gottlob, Matthias Lanzinger and Reinhard Pichler Semantic Width and the Fixed-Parameter Tractability of Constraint Satisfaction Problems In IJCAI, pages 1726-1733, ijcai.org, 2020.
    [ BibTeX ]
  3. Georg Gottlob, Matthias Lanzinger and Reinhard Pichler Semantic Width Revisited (Extended Abstract) In AMW, CEUR-WS.org, CEUR Workshop Proceedings 2369, 2019.
    [ BibTeX ]
  4. Georg Gottlob, Cem Okulmus and Reinhard Pichler Fast and Parallel Decomposition of Constraint Satisfaction Problems In IJCAI, pages 1155-1162, ijcai.org, 2020.
    [ BibTeX ]
  5. Georg Gottlob, Cem Okulmus and Reinhard Pichler Parallel Computation of Generalized Hypertree Decompositions In AMW, CEUR-WS.org, CEUR Workshop Proceedings 2369, 2019.
    [ BibTeX ]
  6. Wolfgang Fischl, Georg Gottlob, Davide Mario Longo and Reinhard Pichler HyperBench: A Benchmark and Tool for Hypergraphs and Empirical Findings In PODS, pages 464-480, ACM, 2019.
    [ BibTeX ]
  7. Wolfgang Fischl, Georg Gottlob, Davide M. Longo and Reinhard Pichler HyperBench: A Benchmark and Tool for Hypergraphs and Empirical Findings In AMW, CEUR-WS.org, CEUR Workshop Proceedings 2369, 2019.
    [ BibTeX ]
  8. Nofar Carmeli and Markus Kröll On the Enumeration Complexity of Unions of Conjunctive Queries In PODS, pages 134-148, ACM, 2019.
    [ BibTeX ]
  9. Nadia Creignou, Markus Kröll, Reinhard Pichler, Sebastian Skritek and Heribert Vollmer A complexity theory for hard enumeration problems In Discret. Appl. Math., 268: 191-209, 2019.
    [ BibTeX ]
  10. Liat Peterfreund, Dominik D. Freydenberger, Benny Kimelfeld and Markus Kröll Complexity Bounds for Relational Algebra over Document Spanners In PODS, pages 320-334, ACM, 2019.
    [ BibTeX ]
  11. Stefan Mengel and Sebastian Skritek Characterizing Tractability of Simple Well-Designed Pattern Trees with Projection In Theory Comput. Syst., 65 (1): 3-41, 2021.
    [ BibTeX ]
  12. Sebastian Skritek Towards Reconciling Certain Answers and SPARQL: Bag Semantics to the Rescue? In AMW, CEUR-WS.org, CEUR Workshop Proceedings 2369, 2019.
    [ BibTeX ]
  13. Phokion G. Kolaitis, Reinhard Pichler, Emanuel Sallinger and Vadim Savenkov On the Language of Nested Tuple Generating Dependencies In ACM Trans. Database Syst., 45 (2): 8:1-8:59, 2020.
    [ BibTeX ]
  14. Leopoldo E. Bertossi, Georg Gottlob and Reinhard Pichler Datalog: Bag Semantics via Set Semantics In ICDT, pages 16:1-16:19, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, LIPIcs 127, 2019.
    [ BibTeX ]
Top
Last updated: 2021-03-18 15:30

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