Algorithms Seminar: Rasums Pagh (ITU Copenhagen)
Date: June 01, 2006 (Thursday) at 14:00
Computing joins—databases meet graph algorithms
Joint work with Anna Pagh. To appear at PODS 2006.
Abstract:
The natural join operation of relational algebra is a cornerstone of relational database systems. Computing a join of k relations can be phrased as the problem of finding all subgraphs of a certain form in a k-partite graph. Not surprisingly, the general problem is NP-hard (reduction to CLIQUE), but special (and typical) cases are tractable.
We consider "acyclic joins", for which the subgraphs to be found are trees with k vertices and show that:
- Previous algorithms have a complexity that grows (at least) linearly with kn (where n is the input size), and
- It is possible to eliminate the dependence on k in most cases, achieving essentially optimal complexity.
Finally, we consider the cyclic case for k<=4 in the I/O model, leaving improvement of the naive approach for k>4 as an intersting open problem.
Room: E:2405
Last modified Dec 9, 2011 12:59 pm
0713