[Back]


Publications in Scientific Journals:

G. Gottlob, R. Pichler, F. Wei:
"Tractable database design and datalog abduction through bounded treewidth";
Information Systems, 35 (2010), 3; 278 - 298.



English abstract:
Given that most elementary problems in database design are NP-hard, the currently used database design algorithms produce suboptimal results. For example, the current 3NF decomposition algorithms may continue further decomposing a relation even though it is already in 3NF. In this paper we study database design problems whose sets of functional dependencies have bounded treewidth. For such sets, we develop polynomial-time and highly parallelizable algorithms for a number of central database design problems such as:

. primality of an attribute;

. 3NF-test for a relational schema or subschema;

. BCNF-test for a subschema.

In order to define the treewidth of a relational schema, we shall associate a hypergraph with it. Note that there are two main possibilities of defining the treewidth of a hypergraph View the MathML source: One is via the primal graph of View the MathML source and one is via the incidence graph of View the MathML source. Our algorithms apply to the case where the primal graph is considered. However, we also show that the tractability results still hold when the incidence graph is considered instead.

It turns out that our results have interesting applications to logic-based abduction. By the well-known relationship with the primality problem in database design and the relevance problem in propositional abduction, our new algorithms and tractability results can be easily carried over from the former field to the latter. Moreover, we show how these tractability results can be further extended from propositional abduction to abductive diagnosis based on non-ground datalog.

Keywords:
Normal forms; Database design; Tree decomposition; Bounded treewidth; Fixed-parameter tractability; Datalog abduction


"Official" electronic version of the publication (accessed through its Digital Object Identifier - DOI)
http://dx.doi.org/10.1016/j.is.2009.09.003

Electronic version of the publication:
http://publik.tuwien.ac.at/files/PubDat_186193.pdf


Created from the Publication Database of the Vienna University of Technology.