G. Gottlob,R. Pichler, F. Wei:

"Tractable Database Design through Bounded Treewidth";

Talk: PODS 2006, Chicago, USA; 2006-06-26 - 2006-06-28; in: "Proceedings of the Twenty-Fifth ACM SIGMOND-SIGACT-SIGART Symposium on Principles of Database Systems", ACM Press, (2006), ISBN: 1-59593-318-2; 124 - 133.

Given tha almost elementaey problems in dtabase design are NP-hard, the currently used database design algorithms produce suboptimal results. For wxample, the current 3NF decomposition algorithms may continue further decomposing a relation even though itis already in 3NF. In this paper we study database design problems whose sets of functional dependencies have bounded treewidth. For such sets, which frequently occur in practice, we develop polynominal-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

For establishing these results, we propose a new characterization for keys and for the primality of a single attribute.

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

http://aleph.ub.tuwien.ac.at/F?base=tuw01&func=find-c&ccl_term=AC06586788

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