Tractable database design through bounded treewidth

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, which frequently occur in practice, 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.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 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 case where the primal graph is considered. However, we also show that the tractability results still hold when the incidence graph is considered instead.

REFERENCES

• 1: W. Armstrong. "Dependency Structures of Data Base Relationships". In IFIP Congress, pages 580--583, 1974.
• 2: Catriel Beeri , Philip A. Bernstein, Computational problems related to the design of normal form relational schemas, ACM Transactions on Database Systems (TODS), v.4 n.1, p.30-59, March 1979 [doi>10.1145/320064.320066]
• 3: C. Beeri and P. Honeyman. "Preserving Functional Dependencies". SIAM J. Comput., 10(3):647--656, 1981.
• 4: C. Berge. Hypergraphs. North Holland, Amsterdam, 1989.
• 5: Philip A. Bernstein, Synthesizing third normal form relations from functional dependencies, ACM Transactions on Database Systems (TODS), v.1 n.4, p.277-298, Dec. 1976 [doi>10.1145/320493.320489]
• 6: Hans L. Bodlaender, A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth, SIAM Journal on Computing, v.25 n.6, p.1305-1317, Dec. 1996 [doi>10.1137/S0097539793251219]
• 7: A. Borodin , S. A. Cook , P. W. Dymond , W. L. Ruzzo , M. Tompa, Two applications of inductive counting for complementation problems, SIAM Journal on Computing, v.18 n.3, p.559-578, June 1989 [doi>10.1137/0218038]
• 8: Brouno Courcelle, Graph rewriting: an algebraic and logic approach, Handbook of theoretical computer science (vol. B): formal models and semantics, MIT Press, Cambridge, MA, 1991
• 9: J. Demetrovics and V. D. Thi. "Keys, Antikeys and Prime Attributes". Annales Univ. Sci. Budapest, Sect. Comp.(8):35--52, 1987.
• 10: Thomas Eiter , Georg Gottlob, The complexity of logic-based abduction, Journal of the ACM (JACM), v.42 n.1, p.3-42, Jan. 1995 [doi>10.1145/200836.200838]
• 11: Thomas Eiter , Georg Gottlob, Identifying the Minimal Transversals of a Hypergraph and Related Problems, SIAM Journal on Computing, v.24 n.6, p.1278-1304, Dec. 1995 [doi>10.1137/S0097539793250299]
• 12: Thomas Eiter , Georg Gottlob , Kazuhisa Makino, New results on monotone dualization and generating hypergraph transversals, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.509912]
• 13: Jörg Flum , Markus Frick , Martin Grohe, Query evaluation via tree-decompositions, Journal of the ACM (JACM), v.49 n.6, p.716-752, November 2002 [doi>10.1145/602220.602222]
• 14: Michael L. Fredman , Leonid Khachiyan, On the complexity of dualization of monotone disjunctive normal forms, Journal of Algorithms, v.21 n.3, p.618-628, Nov. 1996 [doi>10.1006/jagm.1996.0062]
• 15: Georg Gottlob , Nicola Leone , Francesco Scarcello, Computing LOGCFL certificates, Theoretical Computer Science, v.270 n.1-2, p.761-777, January [doi>10.1016/S0304-3975(01)00108-6]
• 16: G. Gottlob, N. Leone, and F. Scarcello. "Hypertree Decompositions and Tractable Queries". J. Comput. Syst. Sci., 64(3):579--627, 2002.
• 17: C. L. Lucchesi and S. L. Osborn. "Candidate Keys for Relations". J. Comput. Syst. Sci., 17 (2):270--279, 1978.
• 18: Heikki Mannila , Kari-Jouko Räihä, The design of relational databases, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1992
• 19: K. K. Nambiar, B. Gopinath, T. Nagaraj, and Manjunath. "Boyce-Codd Normal Form Decomposition". J. Comp. and Math. with Appl., 33(4), 1997.
• 20: S. L. Osborn. "Testing for Existence of a Covering Boyce-Codd Normal Form". Inf. Process. Lett., 8(1):11--14, 1979.
• 21: W. L. Ruzzo. "Tree-size Bounded Alternation". J. Comput. Syst. Sci., 21(2):218--235, 1980.
• 22: R. Tarjan. "Depth-first Search and Linear Graph Algorithms". SIAM Journal on Computing, 1 (2):146--160, June 1972.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.1 Logical Design
          Subjects: Data models

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Parallelism and concurrency; Alternation and nondeterminism
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Complexity of proof procedures; Computations on discrete structures

  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.1 Logical Design
          Subjects: Normal forms; Schema and subschema

General Terms:
Algorithms, Design, Theory

Keywords:
bounded treewidth, database design, fixed-parameter tractability, normal forms, tree decomposition