For the first time in PODS, there was a session devoted to some papers that were published in this conference and have been very influential. In PODS 2016 this session included two talks:

• Optimal Score Aggregation Algorithms by Ron Fagin
• Hypertree Decompositions: Question and Answers by Georg Gottlob

The first talk was about the paper [1] published in PODS 2001, while the second one was about the paper [2] published in PODS 1999. It is well worth reading both articles! You can find the presentations of both talks at the Gems of PODS page.

In this post I would to give some more details about [2], which I know better and have used in my own research.

Consider the following evaluation problem: given a Boolean conjunctive query Q and a database instance I, decide whether Q holds in I. This problem is known to be NP-complete, which motivated Gottlob, Leone and Scarcello to look for natural restrictions on conjunctive queries that could lead to tractability. In particular, motivated by this issue they introduced in [2] the notions of hypertree decomposition and hypertree width of a conjunctive query. The hypertree width of a conjunctive query Q is a natural number greater than or equal to 1 that essentially measures how acyclic Q is, the lower this value the more acyclic the query is. In fact, the hypertree width of a conjunctive query Q is 1 if and only if Q is acyclic in the usual sense studied in the database literature since the early 80s (see [3] for a definition of this notion). The notion of hypertree width helps in solving the intractability issue of the evaluation problem; for the class of conjunctive queries whose hypertree width is bounded by a fixed constant k the evaluation problem can be solved in polynomial time. Moreover, it can be verified in polynomial time whether the hypertree width of a conjunctive query is bounded by a fixed constant k.

It is important to notice that the notions of hypertree decomposition and hypertree width can also be used for the more general case of non-Boolean conjunctive queries, but the size of the output needs to be taken into consideration in this context. A more detailed discussion about this and many more details about these two notions can be found in the article accompanying the invited talk by Georg [4], including some more recent results concerning them and a section discussing the applicability of these techniques in real-world applications.

References

1. Ronald Fagin, Amnon Lotem, Moni Naor: Optimal Aggregation Algorithms for Middleware. PODS 2001: 102-113.
2. Georg Gottlob, Nicola Leone, Francesco Scarcello: Hypertree Decompositions and Tractable Queries. PODS 1999: 21-32.
3. Mihalis Yannakakis: Algorithms for Acyclic Database Schemes. VLDB 1981: 82-94.
4. Georg Gottlob, Gianluigi Greco, Nicola Leone, Francesco Scarcello: Hypertree Decompositions: Questions and Answers. PODS 2016: 57-74.