Yannakakis algorithm

The Yannakakis algorithm is an algorithm in database theory for computing the output of an (alpha-)acyclic conjunctive query. The algorithm is named after Mihalis Yannakakis.^[1]

High-level description

The algorithm relies on a join tree of the query, which is guaranteed to exist and can be computed in linear time for any acyclic query. The join tree is a tree structure that contains the query atoms as nodes and has the connectedness (or running intersection) property which states that for every query variable, the tree nodes that contain that variable form a connected subgraph. The tree can be rooted arbitrarily.

The algorithm materializes a relation for each query atom (this is necessary because the same input relation may be referenced by multiple query atoms) and performs two sweeps, one bottom-up in join tree order (from the leaves to the root), and one top-down (from the root to the leaves). In each node visited, it performs a semi-join between the corresponding relation and its parent or children (depending on the sweep phase). After these two sweeps, all spurious tuples that do not participate in producing any query answer are guaranteed to be removed from the relations. A final pass over the relations, performing joins and early projections, produces the query output.

Complexity

Let $|D|$ be the size of the database (i.e., the total number of tuples across all input relations), $|Q|$ the size of the query, and $|OUT|$ the number of tuples in the query output.

If the query does not project out any variables (referred to as a full conjunctive query or a join query or a conjunctive query with no existential quantifiers), then the complexity of the algorithm is $O(|Q|(|D|+|OUT|)$ . Assuming a fixed query $Q$ (a setting referred to as data complexity), this means that the algorithm's worst-case running time is asymptotically the same as reading the input and writing the output, which is a natural lower bound.

If some variables are projected out in the query, then there is an additional $|D|$ factor, making the complexity $O(|Q||D||OUT|)$ .

Connections to other problems

The algorithm has been influential in database theory and its core ideas are found in algorithms for other tasks such as enumeration^[2]^[3]^[4] and aggregate computation.^[5] An important realization is that the algorithm implicitly operates on the Boolean semiring (the elimination of a tuple corresponds to a False value in the semiring), but its correctness is maintained if we use any other semiring. For example, using the natural numbers semiring, where the operations are addition and multiplication, the same algorithm computes the total number of query answers.

References

^ Yannakakis, Mihalis (1981-09-09). "Algorithms for acyclic database schemes". Proceedings of the Seventh International Conference on Very Large Data Bases - Volume 7. VLDB '81. Cannes, France: VLDB Endowment: 82–94.
^ Bagan, Guillaume; Durand, Arnaud; Grandjean, Etienne (2007). "On Acyclic Conjunctive Queries and Constant Delay Enumeration". In Duparc, Jacques; Henzinger, Thomas A. (eds.). Computer Science Logic. Lecture Notes in Computer Science. Berlin, Heidelberg: Springer. pp. 208–222. doi:10.1007/978-3-540-74915-8_18. ISBN 978-3-540-74915-8.
^ Berkholz, Christoph; Gerhardt, Fabian; Schweikardt, Nicole (2020-02-24). "Constant delay enumeration for conjunctive queries: a tutorial". ACM SIGLOG News. 7 (1): 4–33. doi:10.1145/3385634.3385636. S2CID 211521785.
^ Tziavelis, Gatterbauer, Riedewald. Toward Responsive DBMS: Optimal Join Algorithms, Enumeration, Factorization, Ranking, and Dynamic Programming. Tutorial at ICDE 2022. https://doi.org/10.1109/ICDE53745.2022.00299. Part 3: Acyclic queries & Enumeration. Slides, 20-min video
^ Abo Khamis, Mahmoud; Ngo, Hung Q.; Rudra, Atri (2016-06-15). "FAQ: Questions Asked Frequently". Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems. PODS '16. New York, NY, USA: Association for Computing Machinery. pp. 13–28. doi:10.1145/2902251.2902280. ISBN 978-1-4503-4191-2.

[1] Yannakakis, Mihalis (1981-09-09). "Algorithms for acyclic database schemes". Proceedings of the Seventh International Conference on Very Large Data Bases - Volume 7. VLDB '81. Cannes, France: VLDB Endowment: 82–94.

[2] Bagan, Guillaume; Durand, Arnaud; Grandjean, Etienne (2007). "On Acyclic Conjunctive Queries and Constant Delay Enumeration". In Duparc, Jacques; Henzinger, Thomas A. (eds.). Computer Science Logic. Lecture Notes in Computer Science. Berlin, Heidelberg: Springer. pp. 208–222. doi:10.1007/978-3-540-74915-8_18. ISBN 978-3-540-74915-8.

[3] Berkholz, Christoph; Gerhardt, Fabian; Schweikardt, Nicole (2020-02-24). "Constant delay enumeration for conjunctive queries: a tutorial". ACM SIGLOG News. 7 (1): 4–33. doi:10.1145/3385634.3385636. S2CID 211521785.

[Tziavelis-4] Tziavelis, Gatterbauer, Riedewald. Toward Responsive DBMS: Optimal Join Algorithms, Enumeration, Factorization, Ranking, and Dynamic Programming. Tutorial at ICDE 2022. https://doi.org/10.1109/ICDE53745.2022.00299. Part 3: Acyclic queries & Enumeration. Slides, 20-min video

[5] Abo Khamis, Mahmoud; Ngo, Hung Q.; Rudra, Atri (2016-06-15). "FAQ: Questions Asked Frequently". Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems. PODS '16. New York, NY, USA: Association for Computing Machinery. pp. 13–28. doi:10.1145/2902251.2902280. ISBN 978-1-4503-4191-2.

[1]

[2]

[3]

[4]

[5]