Efficient updates to independent schemes in the weak instance model

ABSTRACT

The weak instance model is a framework to consider the relations in a database as a whole, regardless of the way attributes are grouped in the individual relations. Queries and updates can be performed involving any set of attributes. The management of updates is based on a lattice structure on the set of legal states, and inconsistencies and ambiguities can arise In the general case, the test for inconsistency and determinism may involve the application of the chase algorithm to the whole database. In this paper it is shown how, for the highly significant class of independent schemes, updates can be handled efficiently, considering only the relevant portion of the database.

REFERENCES

• 1: S. Abiteboul, Updates, a new frontier, Lecture notes in computer science on ICDT '88, p.1-18, October 1988, Bruges, Belgium
• 2: A. V. Aho , Y. Sagiv , J. D. Ullman, Efficient optimization of a class of relational expressions, ACM Transactions on Database Systems (TODS), v.4 n.4, p.435-454, Dec. 1979 [doi>10.1145/320107.320112]
• 3: A V Aho, Y Saglv, and J D Ullman Equivalence of relational expressions SIAM Journal on Computzng, 8(2) 218-246, 1979
• 4: P Atzem and E P F Chan Efficient and optimal query answering on independent schemes Theoretical Computer Sczence, 71(2), March 1990 To appear
• 5: Paolo Atzeni , Edward P. F. Chan, Efficient optimization of simple chase join expressions, ACM Transactions on Database Systems (TODS), v.14 n.2, p.212-230, June 1989 [doi>10.1145/63500.63520]
• 6: 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]
• 7: P. Atzeni , M. C. De Bernardis, A new basis for the weak instance model, Proceedings of the sixth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.79-86, March 23-25, 1987, San Diego, California, United States [doi>10.1145/28659.28667]
• 8: P Atzem and R Torlone Efficient Updates to Independent Schemes zn the Weak Instance Model Rapporto R 281, IASI-CNR, Roma, 1989
• 9: P. Atzeni , R. Torlone, Updating databases in the weak instance model, Proceedings of the eighth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.101-109, March 1989, Philadelphia, Pennsylvania, United States [doi>10.1145/73721.73731]
• 10: G Blrkhoff Lattice Theory Colloquium Pubhcattons, Volume XXV, American Mathematical Society, third edition, 1967
• 11: Edward P. F. Chan, Optimal computation of total projections with unions of simple chase join expressions, Proceedings of the 1984 ACM SIGMOD international conference on Management of data, June 18-21, 1984, Boston, Massachusetts
• 12: M H Graham and M Yannakakls Independent database schemas Journal of Comp and System Sc, 28(1) 121-141, 1984
• 13: 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]
• 14: M Ito, M Iwasakl, and T Kasaml Some results on the representative instance m relatmnal databases SIAM journal on Computing, 14(2) 334-354, 1985
• 15: D Maler The Theory of Relatwnal Databases Computer Science Press, Potomac, Maryland, 1983
• 16: 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]
• 17: D Maler, D Rozenshtem, and D S Warren Wmdow functions In P C Kanellakls and F Preparata, editors, Advances zn Computzn!l Research, Vol 3, pages 213-246, JAI Press, 1986
• 18: 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]
• 19: 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]
• 20: 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]
• 21: 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]
• 22: Yehoshua Sagiv, On computing restricted projections of representative instances, Proceedings of the fourth ACM SIGACT-SIGMOD symposium on Principles of database systems, p.171-180, March 25-27, 1985, Portland, Oregon, United States [doi>10.1145/325405.325427]
• 23: J D Ullman Prmczple~ of Database Systems Computer Scmnce Press, Potomac, Maryland, second edition, 1982

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.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing

General Terms:
Algorithms, Design, Theory