Polynomial time designs toward both BCNF and efficient data manipulation

ABSTRACT

We define the independence-reducibility based on a modification of key dependencies, which has better computational properties and is more practically useful than the original one based on key dependencies. Using this modification as a tool, we design BCNF databases that are highly desirable with respect to updates and/or query answering. In particular, given a set U of attributes and a set F of functional dependencies over U, we characterize when F can be embedded in a database scheme over U that is independent and is BCNF with respect to F, a polynomial time algorithm that tests this characterization and produces such a database scheme whenever possible is presented. The produced database scheme contains the fewest possible number of relation schemes. Then we show that designs of embedding constant-time-maintainable BCNF schemes and of embedding independence-reducible schemes share exactly the same method with the above design. Finally, a simple modification of this method yields a polynomial time algorithm for designing embedding separable BCNF schemes.

REFERENCES

• A: W W Armstrong, "Dependency structures of data base relatlonslups," IFIP Congress. 1974, pp 580-583
• ABU: A. V. Aho , C. Beeri , J. D. Ullman, The theory of joins in relational databases, ACM Transactions on Database Systems (TODS), v.4 n.3, p.297-314, Sept. 1979 [doi>10.1145/320083.320091]
• AC: Paolo Atzeni , Edward P. F. Chan, Efficient query answering in the representative instance approach, Proceedings of the fourth ACM SIGACT-SIGMOD symposium on Principles of database systems, p.181-188, March 25-27, 1985, Portland, Oregon, United States [doi>10.1145/325405.325429]
• B: 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]
• BB: 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]
• BBG: C Been. P A Berstem and N Goodman, "Soptusucate's mtroducuon to database normahzat~on theory," VLDB 1978, pp 113-124
• BH: C Been and P Honeyman, "Preserving funcuonal dependencies." SIAM J Comput . Vol I0. No 3.1981, pp 647-656
• BS: F Bancflhon and N Spyratos, "Independent components of data bases," VLDB 1981, pp 398-408
• CH: Edward P. F. Chan , Hector J. Hernandez, Independence-reducible database schemes, Proceedings of the seventh ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.163-173, March 1988, Austin, Texas, United States [doi>10.1145/308386.308431]
• CM: Edward P. F. Chan , Alberto O. Mendelzon, Independent and separable database schemes, SIAM Journal on Computing, v.16 n.5, p.841-851, Oct. 1987 [doi>10.1137/0216055]
• Co: E F Codd, "Recent mvestlgataon m relatmnal systems," IFIP 1987, pp 1017-1021
• GMV: Marc H. Graham , Alberto O. Mendelzon , Moshe Y. Vardi, Notions of dependency satisfaction, Journal of the ACM (JACM), v.33 n.1, p.105-129, Jan. 1986 [doi>10.1145/4904.4798]
• GW: Marc H. Graham , Ke Wang, Constant time maintenance or the triumph of the FD., Proceedings of the fifth ACM SIGACT-SIGMOD symposium on Principles of database systems, p.202-216, March 24-26, 1986, Cambridge, Massachusetts, United States [doi>10.1145/6012.6017]
• GY: M H Graham and M Yannakakas, "Independent database schemes," JCSS, Vol 28, No I. 1984, pp 121- 141
• H: Peter Honeyman, Testing satisfaction of functional dependencies, Journal of the ACM (JACM), v.29 n.3, p.668-677, July 1982 [doi>10.1145/322326.322330]
• HC: Héctor J. Hernández , Edward P. F. Chan, A characterization of constant-time maintainability for BCNF database schemes, Proceedings of the 1988 ACM SIGMOD international conference on Management of data, p.209-217, June 01-03, 1988, Chicago, Illinois, United States
• HW: H J Hemandez and K Wang, "On the boundedness of comtant-umo-mamtamable database schemes," subnutted to pubhcauon, 1989
• IIK: M Ito, M Iwasakl and T Kasam, "Some results on the representative instances m relatmnal databases," SlAM J Comps, Vol 14, No 2, May, 1985. pp 334- 353
• M: Alberto O. Mendelzon, Database states and their tableaux, ACM Transactions on Database Systems (TODS), v.9 n.2, p.264-282, June 1984 [doi>10.1145/329.318579]
• Ma: D Maler, The theory of relatwnal databases, CSP Inc, 1983
• MMS: David Maier , Alberto O. Mendelzon , Yehoshua Sagiv, Testing implications of data dependencies, ACM Transactions on Database Systems (TODS), v.4 n.4, p.455-469, Dec. 1979 [doi>10.1145/320107.320115]
• MUV: David Maier , Jeffrey D. Ullman , Moshe Y. Vardi, On the foundations of the universal relation model, ACM Transactions on Database Systems (TODS), v.9 n.2, p.283-308, June 1984 [doi>10.1145/329.318580]
• S1: Yehoshua Sagiv, Can we use the universal instance assumption without using nulls?, Proceedings of the 1981 ACM SIGMOD international conference on Management of data, April 29-May 01, 1981, Ann Arbor, Michigan [doi>10.1145/582318.582336]
• S2: Yehoshua Sagiv, A characterization of globally consistent databases and their correct access paths, ACM Transactions on Database Systems (TODS), v.8 n.2, p.266-286, June 1983 [doi>10.1145/319983.319988]
• S3: Yehoshua Sagiv, Evaluation of queries in independent database schemes, Journal of the ACM (JACM), v.38 n.1, p.120-161, Jan. 1991 [doi>10.1145/102782.102787]
• U: Jeffrey D. Ullman, Principles of Database Systems, W. H. Freeman & Co., New York, NY, 1983
• V: Yannis Vassiliou, A formal treatment of imperfect information in database management, 1980
• W: K. Wang, Can constant-time-maintainability be more practical?, Proceedings of the eighth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.120-127, March 1989, Philadelphia, Pennsylvania, United States [doi>10.1145/73721.73733]
• WG: K Wang and MH Graham, "Constant-tlrnemamtamabdlty a 8enerahzatlon of independence," submitted to pubhcatlon, 1988 (See {GW} for an extended abstract)
• Y: M Yannakakas, "Algorithms for acychc database schemes," VLDB 1981

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.3 Complexity Measures and Classes
          Subjects: Reducibility and completeness

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.1 Logical Design
          Subjects: Normal forms
      H.2.4 Systems
          Subjects: Query processing

General Terms:
Algorithms, Design, Theory