Monday, April 28, 2008
Humboldt-Universität zu Berlin
Institut für Informatik
Rudower Chaussee 25
Attention: different location: room 4.112.
Lecture - 14:15
Abstract:
Relational joins are at the core of relational algebra, which in
turn is the core of the standard database query language SQL. As their
evaluation is expensive and very often dominated by the output size, it is
an important task for database query optimisers to compute estimates on the
size of joins and to find good execution plans for sequences of joins. We
study these problems from a theoretical perspective, both in the worst-case
model, and in an average-case model where the database is chosen according
to a known probability distribution. Our key observation is that
the size of a sequence of joins is tightly linked to two combinatorial
parameters of the underlying database schema, the fractional edge cover
number in the worst case scenario, and the maximum density in the average
case.
We obtain almost matching upper and lower bounds on the size of the joins in
the worst case scenario and a concentration result in the average case. Then
we study algorithms for computing joins and, in particular, investigate
execution strategies that appear in database systems.
Remarkably, our analysis uses a number of different combinatorial tools,
such as entropy arguments, LP duality, expander graphs, and various
probabilistic techniques.
(This is joint work with Albert Atserias and Daniel Marx.)
Colloquium - 16:00
Abstract:
We prove that the weighted monotone circuit satisfiability problem has
no fixed-parameter tractable approximation algorithm with constant or
polylogarithmic approximation ratio unless FPT = W[P]. The parameterized
complexity class FPT consists of all fixed-parameter tractable problems,
and the class W[P] may be viewed as an analogue of the class NP in the
world of parameterized complexity theory. Our result answers a question
of Alekhnovich and Razborov, who proved that the weighted monotone
circuit satisfiability problem has no fixed-parameter tractable
2-approximation algorithm unless every problem in the parameterized
complexity class W[P] can be solved by a randomized fpt algorithm and
asked whether their result can be derandomized.
The decision version of the monotone circuit satisfiability problem is
known to be complete for the class W[P]. By reducing them to the
monotone circuit satisfiability problem with suitable approximation
preserving reductions, we prove similar inapproximability results for
all other natural minimisation problems known to be W[P]-complete.