Fwd: Mini-Workshop on Hypertree Decompositions

From: Eva Nedoma <sek@dbai.tuwien.ac.at>
Date: Fri, 24 Jun 2005 13:51:36 +0200

Mini-Symposium
(Sponsored by Wolfgang Pauli Instiute, Austria)

Place: Seminarroom 184-3 (KBS), Favoritenstraße 9-11 / 184-3, staircase 1, 3rd floor (when you leave the elevator turn right)

Date: Wednesday, 29th June 2005, 10:30 - 12:30

Talks:

10:30 - 11:30
Data, Schema, Ontology and Logic Integration
Joseph Goguen, University of California at San Diego, USA

11:45 - 12:30
Computer Core for Data Exchange: New Algorithms and Practical Solutions
Georg Gottlob, Vienna University of Technology, Austria

Abstracts:

Data, Schema, Ontology and Logic Integration:
This paper gives a general definition of a ``kind of schema'' (often called a ``meta-model'' in the literature, but here called a ``species'') along with general definitions for the schemas of a species, and for the databases, constraints, and queries over a given schema of a species. This leads naturally to a general theory of data translation and integration over arbitrary schemas of arbitrary species, based on schema morphisms, and to a similar general theory of ontology translation and integration over arbitrary logics. Institutions provide a general notion of logic, and Grothendieck flattening provides a general tool for integrating heterogeneous schema species and logics, which in turn enables integration of theories, such as ontologies, over different logics.

Computer Core for Data Exchange: New Algorithms and Practical Solutions:
Data Exchange is the problem of inserting data structured under a source schema into a target schema of different structure (possibly with integrity constraints), while reflecting the source data as accurately as possible. We study computational issues related to data exchange in the setting ofFagin, Kolaitis, and Popa (PODS´03). We use the technique of hypertree decompositions to derive improved algorithms for computing the core of a relational instance with labeled nulls, a problem we show to be fixed-parameter intractable with respect to the block size of the input instances. We show that computing the core of a data exchange problem is tractable for two large and useful classes of target constraints. The first class includes functional dependencies and weakly acyclic inclusion dependencies. The second class consists of full tuple generating dependencies and arbitrary equation generating dependencies. Finally, we show that computing cores is NP-hard in presence of a system-predicate NULL(x), which is true if x is a null value.