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

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