Dear all,

the Research Unit "Databases and Artificial Intelligence"
cordially invites you to the following talk:

=============================================================================

Speaker: Prof. Dr. Francesco Scarcello

University of Calabria, Rende, Italy

http://si.deis.unical.it/~frank/

=============================================================================

DATE: Monday, January 21, 2019

TIME: 16:00 c.t.

VENUE: Seminarraum von Neumann, Favoritenstraße 9-11, 1040 Wien,
RoomNo.: HBEG16

(access from yard)

=============================================================================

TITLE:

Tree projection width and fixed-parameter tractable queries

=============================================================================

Abstract:

Identifying the frontier of tractability for conjunctive queries
is a long-standing question in database theory. Recent advances
in structural decomposition methods provide important answers
regarding the fixed-parameter tractability of conjunctive
queries, and efficient algorithms based on decomposition methods
have been implemented in database management systems. However,
for classes of instances where we have information on the data,
such as functional dependencies or the more general degree
constraints, there is still an important gap between the ideal
information-theoretic bound and the performances of the
available algorithms. Moreover, it was open whether the best
possible bound is computable or not.

In this work, we revisit and generalize purely structural and
degree-aware bounds, by using the classical and powerful notion
of tree projection, where the decompositions are based on the
solutions of sub-problems of the given instance. The new notions
are parameterized by a desired level of uniformity, where the
best width is obtained in the theoretical perfectly uniform
case. We thus get a finer hierarchy of bounds, which can be
tuned by acting on this parameter. The more powerful variant of
the tree-projection width, called full tree-projection width, is
computable and is at most the entropic degree-aware submodular
width. The two widths coincide asymptotically, that is, for
classes with unbounded values.

A crucial property of decomposition methods is to represent in a
compact way the query answers of a given instance, in the form
of an equivalent acyclic query. This way, query answers can be
computed easily from the decompositions, and can be enumerated
in linear time (with respect to the output size). We show that
the notion of full tree-projection width is tight with respect
to this acyclic-representation power. These results can be
easily combined with tools developed for structural
decomposition methods, in particular for enumerating answers of
queries with existential quantifiers.

=============================================================================

best regards

Reinhard Pichler