An execution model for limited ambiguity rules and its application to derived data update

ABSTRACT

A novel execution model for rule application in active databases is developed and applied to the problem of updating derived data in a database represented using a semantic, object-based database model. The execution model is based on the use of “limited ambiguity rules” (LARs), which permit disjunction in rule actions. The execution model essentially performs a breadth-first exploration of alternative extensions of a user-requested update. Given an object-based database schema, both integrity constraints and specifications of derived classes and attributes are compiled into a family of limited ambiguity rules. A theoretical analysis shows that the approach is sound: the execution model returns all valid “completions” of a user-requested update, or terminates with an appropriate error notification. The complexity of the approach in connection with derived data update is considered.

REFERENCES

• 1: Serge Abiteboul , Richard Hull, IFO: a formal semantic database model, ACM Transactions on Database Systems (TODS), v.12 n.4, p.525-565, Dec. 1987 [doi>10.1145/32204.32205]
• 2: Serge Abiteboul , Richard Hull , Victor Vianu, Foundations of Databases: The Logical Level, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1995
• 3: Serge Abiteboul , Victor Vianu, Datalog extensions for database queries and updates, Journal of Computer and System Sciences, v.43 n.1, p.62-124, Aug. 1991 [doi>10.1016/0022-0000(91)90032-Z]
• 4: Hamideh Afsarmanesh , Dennis McLeod, The 3DIS: an extensible object-oriented information management environment, ACM Transactions on Information Systems (TOIS), v.7 n.4, p.339-377, Oct. 1989 [doi>10.1145/76158.76892]
• 5: 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]
• 6: Thierry Barsalou , Niki Siambela , Arthur M. Keller , Gio Wiederhold, Updating relational databases through object-based views, Proceedings of the 1991 ACM SIGMOD international conference on Management of data, p.248-257, May 29-31, 1991, Denver, Colorado, United States
• 7: François Bry, Intensional updates: abduction via deduction, Logic programming, MIT Press, Cambridge, MA, 1990
• 8: F. Cacace , S. Ceri , S. Crespi-Reghizzi , L. Tanca , R. Zicari, Integrating object-oriented data modelling with a rule-based programming paradigm, Proceedings of the 1990 ACM SIGMOD international conference on Management of data, p.225-236, May 23-26, 1990, Atlantic City, New Jersey, United States
• 9: Stefano Ceri , Jennifer Widom, Deriving Production Rules for Incremental View Maintenance, Proceedings of the 17th International Conference on Very Large Data Bases, p.577-589, September 03-06, 1991
• 10: Stefano Ceri , Jennifer Widom, Deriving production rules for constraint maintenance, Proceedings of the sixteenth international conference on Very large databases, p.566-577, September 1990, Brisbane, Australia
• 11: Stefano Ceri , Piero Fraternali , Stefano Paraboschi , Letizia Tanca, Automatic generation of production rules for integrity maintenance, ACM Transactions on Database Systems (TODS), v.19 n.3, p.367-422, Sept. 1994 [doi>10.1145/185827.185828]
• 12: I. A. Chen , D. McLeod, Derived data update in semantic databases, Proceedings of the 15th international conference on Very large data bases, p.225-235, July 1989, Amsterdam, The Netherlands
• 13: CHIN, I. A., HULL, R., AND McLEOD, D.1993. On using ambiguous rules to update derived data. USC Tech. Rep. USC-CS-93-535.
• 14: Laurence Cholvy, Update semantics under the domain closure assumption, Proceedings on International conference on database theory, p.123-140, December 1986, Rome, Italy
• 15: D. Cohen, Compiling complex database transition triggers, Proceedings of the 1989 ACM SIGMOD international conference on Management of data, p.225-234, June 1989, Portland, Oregon, United States
• 16: COHEN, D. 1986. Programming by specification and annotation. In Proceedings of AAAI, (Aug.), 20-25.
• 17: 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]
• 18: 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]
• 19: FURTADO, A. L., SEVCIK, K. C., ANn Dos SANTOS, C.S. 1979. Permitting updates through views of data bases. Inf. Syst. 4, 269-283.
• 20: GHANDEHARIZADEH, S., HULL, R., AND JACOBS, D. 1994. Heraclitus{Alg, C}: Elevating deltas to be first-class citizens in a database programming language. Tech. Rep. USC-CS-94-583, Computer Science Dept., Umversity of Southern California, Sept.
• 21: Shahram Ghandeharizadeh , Richard Hull , Dean Jacobs , Jaime Castillo , Martha Escobar-Molano , Shih-Hui Lu , Junhui Luo , Chiu Tsang , Gang Zhou, On Implementing a Language for Specifying Active Database Execution Models, Proceedings of the 19th International Conference on Very Large Data Bases, p.441-454, August 24-27, 1993
• 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: Michael Hammer , Dennis Mc Leod, Database description with SDM: a semantic database model, ACM Transactions on Database Systems (TODS), v.6 n.3, p.351-386, Sept. 1981 [doi>10.1145/319587.319588]
• 24: George Heineman , Gail E. Kaiser , Naser S. Barghouti , Israel Ben-Shaul, Rule Chaining in Marvel: Dynamic Binding of Parameters, IEEE Expert: Intelligent Systems and Their Applications, v.7 n.6, p.26-33, December 1992 [doi>10.1109/64.180406]
• 25: Richard Hull , Dean Jacobs, Language Constructs for Programming Active Databases, Proceedings of the 17th International Conference on Very Large Data Bases, p.455-467, September 03-06, 1991
• 26: Richard Hull , Roger King, Semantic database modeling: survey, applications, and research issues, ACM Computing Surveys (CSUR), v.19 n.3, p.201-260, Sept. 1987 [doi>10.1145/45072.45073]
• 27: Tomasz Imielinski , Shamim Naqvi , Kumar Vadaparty, Incomplete object—a data model for design and planning applications, Proceedings of the 1991 ACM SIGMOD international conference on Management of data, p.288-297, May 29-31, 1991, Denver, Colorado, United States
• 28: Dean Jacobs , Richard Hull, Database programming with delayed updates, Proceedings of the third international workshop on Database programming languages : bulk types & persistent data: bulk types & persistent data, p.416-428, April 1992, Nafplion, Greece
• 29: KATSUNO, H., AND MENDELZON, A.O. 1991. On the difference between updating and knowledge base and revising it. In Proceedings of the 2nd International Conference on Principles of Knowledge Representation and Reasomng.
• 30: Arthur M. Keller, Choosing a View Update Translator by Dialog at View Definition Time, Proceedings of the 12th International Conference on Very Large Data Bases, p.467-474, August 25-28, 1986
• 31: Gabriel M. Kuper , Jeffrey D. Ullman , Moshe Y. Vardi, On the equivalence of logical databases, Proceedings of the 3rd ACM SIGACT-SIGMOD symposium on Principles of database systems, April 02-04, 1984, Waterloo, Ontario, Canada [doi>10.1145/588011.588044]
• 32: Witold Lipski, Jr., On semantic issues connected with incomplete information databases, ACM Transactions on Database Systems (TODS), v.4 n.3, p.262-296, Sept. 1979 [doi>10.1145/320083.320088]
• 33: Jorge Lobo , Jack Minker , Arcot Rajasekar, Foundations of disjunctive logic programming, MIT Press, Cambridge, MA, 1992
• 34: Christophe de Maindreville , Eric Simon, Modelling Non Deterministic Queries and Updates in Deductive Databases, Proceedings of the 14th International Conference on Very Large Data Bases, p.395-406, August 29-September 01, 1988
• 35: Yoshifumi Masunaga, A Relational Database View Update Translation Mechanism, Proceedings of the 10th International Conference on Very Large Data Bases, p.309-320, August 27-31, 1984
• 36: Dennis McCarthy , Umeshwar Dayal, The architecture of an active database management system, Proceedings of the 1989 ACM SIGMOD international conference on Management of data, p.215-224, June 1989, Portland, Oregon, United States
• 37: Matthew Morgenstern, Active Databases as a Paradigm for Enhanced Computing Environments, Proceedings of the 9th International Conference on Very Large Data Bases, p.34-42, October 31-November 02, 1983
• 38: Amit P. Sheth , James A. Larson , Evan Watkins, TAILOR, A Tool for Updating Views, Proceedings of the International Conference on Extending Database Technology: Advances in Database Technology, p.190-213, March 14-18, 1988
• 39: M. Stonebraker, The Integration of Rule Systems and Database Systems, IEEE Transactions on Knowledge and Data Engineering, v.4 n.5, p.415-423, October 1992 [doi>10.1109/69.166984]
• 40: Michael Stonebraker , Anant Jhingran , Jeffrey Goh , Spyros Potamianos, On rules, procedure, caching and views in data base systems, Proceedings of the 1990 ACM SIGMOD international conference on Management of data, p.281-290, May 23-26, 1990, Atlantic City, New Jersey, United States
• 41: SYBASE Open Client DB-Library/C Reference Manual. 1992. Release 4.6.1, Document ID: 32600-01-0461-01, Aug. 1.
• 42: Yuli Zhou , Meichun Hsu, A theory for rule triggering systems, Proceedings of the international conference on extending database technology on Advances in database technology, p.407-421, March 1990, Venice, Italy

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.4 Systems
          Subjects: Query processing

General Terms:
Algorithms, Design, Languages, Performance, Theory

Keywords:
active database systems, deltas on database states, derived data, limited ambiguity rules, semantic data models, update propagation