Updating relational databases through weak instance interfaces

ABSTRACT

The problem of updating databases through interfaces based on the weak instance model is studied, thus extending previous proposals that considered them only from the query point of view. Insertions and deletions of tuples are considered. As a preliminary tool, a lattice on states is defined, based on the information content of the various states. Potential results of an insertion are states that contain at least the information in the original state and that in the new tuple. Sometimes there is no potential result, and in the other cases there may be many of them. We argue that the insertion is deterministic if the state that contains the information common to all the potential results (the greatest lower bound, in the lattice framework) is a potential result itself. Effective characterizations for the various cases exist. A symmetric approach is followed for deletions, with fewer cases, since there are always potential results; determinism is characterized as a consequence.

REFERENCES

• 1: 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]
• 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: AHo, A V., SAGIV, Y., AND ULLMAN, d. D. Equivalence of relational expressions. SIAM d. Comput. 8, 2 (1979), 218-246.
• 4: 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]
• 5: Paolo Atzeni , Maria Cristina de Bernardis, A new interpretation for Null values in the weak instance model, Journal of Computer and System Sciences, v.41 n.1, p.25-43, August 1990 [doi>10.1016/0022-0000(90)90032-G]
• 6: P. Atzeni , R. Torlone, Approaches to updates over weak instances, Proceedings of the second symposium on Mathematical fundamentals of database systems, p.12-23, June 1989, Visegrád, Hungary
• 7: Paolo Atzeni , Riccardo Torlone, Efficient updates to independent schemes in the weak instance model, Proceedings of the 1990 ACM SIGMOD international conference on Management of data, p.84-93, May 23-26, 1990, Atlantic City, New Jersey, United States
• 8: Paolo Atzeni , Riccardo Torlone, Updating intensional predicates in Datalog, Data & Knowledge Engineering, v.8 n.1, p.1-17, April 1992 [doi>10.1016/0169-023X(92)90002-S]
• 9: F. Bancilhon , N. Spyratos, Update semantics of relational views, ACM Transactions on Database Systems (TODS), v.6 n.4, p.557-575, Dec. 1981 [doi>10.1145/319628.319634]
• 10: 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]
• 11: BmKHOF~~, G. Lattice Theory. Colloquium Pubhcations, Volume XXV. third ed., American Mathematical Society, 1967.
• 12: Volkert Brosda , Gottfried Vossen, Update and retrieval in a relational database through a universal schema interface, ACM Transactions on Database Systems (TODS), v.13 n.4, p.449-485, Dec. 1988 [doi>10.1145/49346.49884]
• 13: 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
• 14: Edward P. F. Chan , Alberto O. Mendelzon, Answering queries on embedded-complete database schemes, Journal of the ACM (JACM), v.34 n.2, p.349-375, April 1987 [doi>10.1145/23005.23007]
• 15: IEEE Software Staff, 'Universal' Relation Fails to Replace Relational Model, IEEE Software, v.5 n.4, p.4-6, July 1988
• 16: Stavros S Cosmadakis , Paris C Kanellakis , Nicolas Spyratos, Partition semantics for relations, Journal of Computer and System Sciences, v.33 n.2, p.203-233, Oct. 1986 [doi>10.1016/0022-0000(86)90019-X]
• 17: Stavros S. Cosmadakis , Christos H. Papadimitriou, Updates of Relational Views, Journal of the ACM (JACM), v.31 n.4, p.742-760, Oct. 1984 [doi>10.1145/1634.1887]
• 18: Umeshwar Dayal , Philip A. Bernstein, On the correct translation of update operations on relational views, ACM Transactions on Database Systems (TODS), v.7 n.3, p.381-416, Sept. 1982 [doi>10.1145/319732.319740]
• 19: FAGIN, R., KUPER, G. M., ULLMAN, J. D., AND VARDI, M.Y. Updating logical databases. In Advances zn Computing Research, Vol 3, P C. Kanellakis and F. P. Preparata, Eds., JAI Press, 1986, pp. 1-18.
• 20: Ronald Fagin , Jeffrey D. Ullman , Moshe Y. Vardi, On the semantics of updates in databases, Proceedings of the 2nd ACM SIGACT-SIGMOD symposium on Principles of database systems, March 21-23, 1983, Atlanta, Georgia [doi>10.1145/588058.588100]
• 21: FU~TAr)O, A., SEVmK, K., Am} Dos SANTOS, C. S Permitting updates through wews of databases. Inf. ,~vst. 4, 4 (1979), 269-283.
• 22: Georg Gottlob , Paolo Paolini , Roberto Zicari, Properties and update semantics of consistent views, ACM Transactions on Database Systems (TODS), v.13 n.4, p.486-524, Dec. 1988 [doi>10.1145/49346.50068]
• 23: GnAHA,X~, M H A~D YANNAKAIqS, M. Independent database schemas d. Comut. Sys Scl 28, I (1984), 121-141.
• 24: 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]
• 25: Arthur M. Keller, Algorithms for translating view updates to database updates for views involving selections, projections, and joins, Proceedings of the fourth ACM SIGACT-SIGMOD symposium on Principles of database systems, p.154-163, March 25-27, 1985, Portland, Oregon, United States [doi>10.1145/325405.325423]
• 26: Arthur M Keller , Jeffrey D Ullman, On complementary and independent mappings on databases, Proceedings of the 1984 ACM SIGMOD international conference on Management of data, June 18-21, 1984, Boston, Massachusetts
• 27: Rom Langerak, View updates in relational databases with an independent scheme, ACM Transactions on Database Systems (TODS), v.15 n.1, p.40-66, March 1990 [doi>10.1145/77643.77645]
• 28: Christophe Lécluse , Nicolas Spyratos, Implementing Queries and Updates on Universal Scheme Interfaces, Proceedings of the 14th International Conference on Very Large Data Bases, p.62-75, August 29-September 01, 1988
• 29: MAmR, D The Theory af Relatmnal Databases Computer Science Press, Rockville, Md, 1983.
• 30: 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]
• 31: MAIER, D, ROZENSHTEIN, D , AND WARREN, D S. Window functions. In Advances m Comput- Ln~ Research, Vol 3, P. C. Kanellakis and F. P Preparata, Eds., JAI Press, 1986, pp. 213 246
• 32: 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]
• 33: 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]
• 34: 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]
• 35: 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]
• 36: Nicolas Spyratos, The partition model: a deductive database model, ACM Transactions on Database Systems (TODS), v.12 n.1, p.1-37, March 1987 [doi>10.1145/12047.22718]
• 37: UI,LMAN, J.D. Principles of Database Systems. 2nd ed., Computer Science Press, Rockwlle, Md., 1982.
• 38: ULLMAN, J. D. Universal relation interfaces for database systems In Proceedzngs of IFIP Congress (1983), pp. 243 252.
• 39: Moshe Y. Vardi, The Universal-Relation Data Model for Logical Independence, IEEE Software, v.5 n.2, p.80-85, March 1988 [doi>10.1109/52.2015]
• 40: Moshe Y. Vardi, The Universal-Relation Data Model for Logical Independence, IEEE Software, v.5 n.2, p.80-85, March 1988 [doi>10.1109/52.2015]

INDEX TERMS

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

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.1 Logical Design
          Subjects: Schema and subschema
  H.5 INFORMATION INTERFACES AND PRESENTATION (I.7)
      H.5.2 User Interfaces (D.2.2, H.1.2, I.3.6)
          Subjects: Theory and methods

General Terms:
Algorithms, Theory