Yannakakis algorithm
 | This article, Yannakakis algorithm, has recently been created via the Articles for creation process. Please check to see if the reviewer has accidentally left this template after accepting the draft and take appropriate action as necessary.
Reviewer tools: Preload talk Inform author |
The Yannakakis algorithm is an algorithm in database theory for computing the output of an acyclic conjunctive query. The algorithm is named after Mihalis YannakakisCite error: There are <ref> tags on this page without content in them (see the help page)..
Complexity
Let be the size of the database (i.e., the total number of tuples across all input relations), the size of the query, and 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 . Assuming a fixed query , this means that the algorithm's running time is asymptotically the same as reading the input and writing the output, which is a natural lower bound.
Projections in the query result in an additional $D$ factor, making the complexity O(|Q||D||OUT|).