Efficient checking of temporal integrity constraints using bounded history encoding

ABSTRACT

We present an efficient implementation method for temporal integrity constraints formulated in Past Temporal Logic. Although the constraints can refer to past states of the database, their checking does not require that the entire database history be stored. Instead, every database state is extended with auxiliary relations that contain the historical information necessary for checking constraints. Auxiliary relations can be implemented as materialized relational views.

REFERENCES

• 1: Serge Abiteboul , Richard Hull , Victor Vianu, Foundations of Databases: The Logical Level, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1995
• 2: I. Ahn , Richard Thomas Snodgrass, Partitioned storage for temporal databases, Information Systems, v.13 n.4, p.369-391, Oct. 1, 1988 [doi>10.1016/0306-4379(88)90004-X]
• 3: James F. Allen, Maintaining knowledge about temporal intervals, Communications of the ACM, v.26 n.11, p.832-843, Nov. 1983 [doi>10.1145/182.358434]
• 4: Rajeev Alur , Thomas A. Henzinger, Real-time logics: complexity and expressiveness, Information and Computation, v.104 n.1, p.35-77, May 1993 [doi>10.1006/inco.1993.1025]
• 5: Rajeev Alur , Thomas A. Henzinger, Logics and Models of Real Time: A Survey, Proceedings of the Real-Time: Theory in Practice, REX Workshop, p.74-106, June 03-07, 1991
• 6: K. R. Apt , H. A. Blair , A. Walker, Towards a theory of declarative knowledge, Foundations of deductive databases and logic programming, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1988
• 7: BAUDINET, M., CHOMICKI, O., AND WOLPER, F. 1992. Temporal deductive databases. In Temporal Databases: Theory. Design, and Implementation, Tansel et al., Eds. Benjamin-Cummings, Redwood City, Calif., 294-320.
• 8: BERNSTEIN, P., BLAUSTEIN, B., AND CLARKE, E. 1980. Fast maintenance of semantic integrity assertions using redundant aggregate data. In International Conference on Very Large Data Bases. (Montreal), VLDB Endowment, 126-136.
• 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: CHOMICKI, J. 1994a. Temporal integrity constraints in relational databases. IEEE Data Eng. Bull. 17, 2 (June), 33-37.
• 11: Jan Chomicki, Temporal Query Languages: A Survey, Proceedings of the First International Conference on Temporal Logic, p.506-534, July 11-14, 1994
• 12: Jan Chomicki, History-less Checking of Dynamic Integrity Constraints, Proceedings of the Eighth International Conference on Data Engineering, p.557-564, February 03-07, 1992
• 13: Jan Chomicki, Real-time integrity constraints, Proceedings of the eleventh ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.274-282, June 02-05, 1992, San Diego, California, United States [doi>10.1145/137097.137889]
• 14: Jan Chomicki , Tomasz Imieliński, Temporal deductive databases and infinite objects, Proceedings of the seventh ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.61-73, March 1988, Austin, Texas, United States [doi>10.1145/308386.308416]
• 15: Jan Chomicki , Damian Niwiński, On the feasibility of checking temporal integrity constraints, Proceedings of the twelfth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.202-213, May 25-28, 1993, Washington, D.C., United States [doi>10.1145/153850.153876]
• 16: Jan Chomicki , David Toman, Implementing Temporal Integrity Constraints Using an Active DBMS, IEEE Transactions on Knowledge and Data Engineering, v.7 n.4, p.566-582, August 1995 [doi>10.1109/69.404030]
• 17: James Clifford , Albert Croker , Alexander Tuzhilin, On completeness of historical relational query languages, ACM Transactions on Database Systems (TODS), v.19 n.1, p.64-116, March 1994 [doi>10.1145/174638.174642]
• 18: CLIFFORD, J., CRO~R, A., AND TUZHmIN, A. 1993. On the completeness of query languages for grouped and ungrouped historical data models. In Temporal Databases: Theory, Design, and ImplementatLon, Tansel et al, Eds Benjamin Cummings, Redwood City, Calif., 496 533.
• 19: U. Dayal , B. Blaustein , A. Buchmann , U. Chakravarthy , M. Hsu , R. Ledin , D. McCarthy , A. Rosenthal , S. Sarin , M. J. Carey , M. Livny , R. Jauhari, The HiPAC project: combining active databases and timing constraints, ACM SIGMOD Record, v.17 n.1, p.51-70, March, 1988 [doi>10.1145/44203.44208]
• 20: José Mauro V. de Castilho , Marco A. Casanova , Antonio L. Furtado, A Temporal Framework for Database Specifications, Proceedings of the 8th International Conference on Very Large Data Bases, p.280-291, September 08-10, 1982
• 21: Robert Demolombe, Syntactical characterization of a subset of domain-independent formulas, Journal of the ACM (JACM), v.39 n.1, p.71-94, Jan. 1992 [doi>10.1145/147508.147520]
• 22: Robert A. Di Paola, The Recursive Unsolvability of the Decision Problem for the Class of Definite Formulas, Journal of the ACM (JACM), v.16 n.2, p.324-327, April 1969 [doi>10.1145/321510.321524]
• 23: DUBOIS, E., HAGELSTEIN, J., AND RIFAUT, A. 1988. Formal reqmrements engineering with ERAE. Philips J Res. 43, 393 414.
• 24: E. Allen Emerson, Temporal and modal logic, Handbook of theoretical computer science (vol. B): formal models and semantics, MIT Press, Cambridge, MA, 1991
• 25: Dov M. Gabbay , Ian Hodkinson , Mark Reynolds, Temporal logic (vol. 1): mathematical foundations and computational aspects, Oxford University Press, Inc., New York, NY, 1994
• 26: Dov M. Gabbay , Peter McBrien, Temporal Logic & Historical Databases, Proceedings of the 17th International Conference on Very Large Data Bases, p.423-430, September 03-06, 1991
• 27: Dov Gabbay , Amir Pnueli , Saharon Shelah , Jonathan Stavi, On the temporal analysis of fairness, Proceedings of the 7th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.163-173, January 28-30, 1980, Las Vegas, Nevada [doi>10.1145/567446.567462]
• 28: Herve Gallaire , Jack Minker , Jean-Marie Nicolas, Logic and Databases: A Deductive Approach, ACM Computing Surveys (CSUR), v.16 n.2, p.153-185, June 1984 [doi>10.1145/356924.356929]
• 29: GARSON, J. 1984. Quantification in modal logic. In Handbook of Phtlosophical Logic, D. Gabbay and F. Guenthner, Eds D. Reldel, NorweI1, Mass 249-307
• 30: Narain H. Gehani , H. V. Jagadish , Oded Shmueli, Composite Event Specification in Active Databases: Model & Implementation, Proceedings of the 18th International Conference on Very Large Data Bases, p.327-338, August 23-27, 1992
• 31: N. H. Gehani , H. V. Jagadish , O. Shmueli, Event specification in an active object-oriented database, Proceedings of the 1992 ACM SIGMOD international conference on Management of data, p.81-90, June 02-05, 1992, San Diego, California, United States
• 32: Michael Gertz , Udo W. Lipeck, Deriving Integrity Maintaining Triggers from Transition Graphs, Proceedings of the Ninth International Conference on Data Engineering, p.22-29, April 19-23, 1993
• 33: HAREL, D. 1985 Recurring dominoes: Making the highly undecidable highly understandable. Ann. D~screte Math. 24, 51-71.
• 34: HAREL, E., L~CHTENSTEIN, O., AND PNUEH, A. 1990. Explicit clock temporal logic. In IEEE Sympos~ura on Logtc m Computer Science (Philadelphia, Pa)., IEEE Computer Society, Los Alam~tos, Calif., 402-443.
• 35: Arding Hsu , Tomasz Imielinski, Integrity checking for multiple updates, Proceedings of the 1985 ACM SIGMOD international conference on Management of data, p.152-168, May 1985, Austin, Texas, United States
• 36: K. Hülsmann , G. Saake, Theoretical foundations of handling large substitution sets in temporal integrity monitoring, Acta Informatica, v.28 n.4, p.365-407, April 1991 [doi>10.1007/BF01893887]
• 37: INTFmNATIONAL ORGANIZATION FOR STANDARmZAT~ON. 1992. Database Language SQL. ISO/IEC 9075:1992
• 38: KAMP, J. 1968. Tense logic and the theory of linear order. Ph.D. dissertation, University of California, Los Angeles.
• 39: Paris C. Kanellakis , Gabriel M. Kuper , Peter Z. Revesz, Constraint query languages (preliminary report), Proceedings of the ninth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.299-313, April 02-04, 1990, Nashville, Tennessee, United States [doi>10.1145/298514.298582]
• 40: Ron Koymans, Specifying real-time properties with metric temporal logic, Real-Time Systems, v.2 n.4, p.255-299, Nov. 1990 [doi>10.1007/BF01995674]
• 41: KOYMANS, R. 1989. Specifying message passing and time-critical systems with temporal logic. Ph.D. dissertation, Technische Universiteit Eindhoven.
• 42: C. H. Kung, On verification of database temporal constraints, Proceedings of the 1985 ACM SIGMOD international conference on Management of data, p.169-179, May 1985, Austin, Texas, United States
• 43: LIPECK, U., GERTZ, M., AND SAAKE, G. 1994. Transitional monitoring of dynamic integrity constraints. IEEE Data Eng. Bull. (June), 38-42.
• 44: U. W. Lipeck , G. Saake, Monitoring dynamic integrity constraints based on temporal logic, Information Systems, v.12 n.3, p.255-269, 1987 [doi>10.1016/0306-4379(87)90004-4]
• 45: Guy M. Lohman , Bruce Lindsay , Hamid Pirahesh , K. Bernhard Schiefer, Extensions to Starburst: objects, types, functions, and rules, Communications of the ACM, v.34 n.10, p.94-109, Oct. 1991 [doi>10.1145/125223.125266]
• 46: Zohar Manna , Amir Pnueli, The temporal logic of reactive and concurrent systems, Springer-Verlag New York, Inc., New York, NY, 1992
• 47: Zohar Manna , Amir Pnueli, The anchored version of the temporal framework, Linear Time, Branching Time and Partial Order in Logics and Models for Concurrency, School/Workshop, p.201-284, May 30-June 03, 1988
• 48: Angelo Morzenti , Dino Mandrioli , Carlo Ghezzi, A model parametric real-time logic, ACM Transactions on Programming Languages and Systems (TOPLAS), v.14 n.4, p.521-573, Oct. 1992 [doi>10.1145/133233.129397]
• 49: Eric Nassor , Guy Vidal-Naquet, Suitability of the Propositional Temporal Logic to Express Properties of Real-Time Systems, Proceedings of the 9th Annual Symposium on Theoretical Aspects of Computer Science, p.59-70, February 13-15, 1992
• 50: NICOLAS, J.-M. 1982. Logic for improving integrity checking in relational databases. Acta Inf. 18, 3, 227-253.
• 51: A Pnueli, Applications of temporal logic to the specification and verification of reactive systems: a survey of current trends, Current trends in concurrency. Overviews and tutorials, Springer-Verlag New York, Inc., New York, NY, 1986
• 52: Xiaolei Qian, An Effective Method for Integrity Constraint Simplification, Proceedings of the Fourth International Conference on Data Engineering, p.338-345, February 01-05, 1988
• 53: Xiaolei Qian , Douglas R. Smith, Integrity Constraint Reformulation for Efficient Validation, Proceedings of the 13th International Conference on Very Large Data Bases, p.417-425, September 01-04, 1987
• 54: Xiaolei Qian , Richard Waldinger, A transaction logic for database specification, Proceedings of the 1988 ACM SIGMOD international conference on Management of data, p.243-250, June 01-03, 1988, Chicago, Illinois, United States
• 55: Krithi Ramamritham, Real-time databases, Distributed and Parallel Databases, v.1 n.2, p.199-226, April 1993 [doi>10.1007/BF01264051]
• 56: Scarlet Schwiderski , Thorsten Hartmann , Gunter Saake, Monitoring temporal preconditions in a behaviour oriented object model, Data & Knowledge Engineering, v.14 n.2, p.143-186, Dec. 1994 [doi>10.1016/0169-023X(94)90042-6]
• 57: A. Prasad Sistla , Ouri Wolfson, Temporal Triggers in Active Databases, IEEE Transactions on Knowledge and Data Engineering, v.7 n.3, p.471-486, June 1995 [doi>10.1109/69.390251]
• 58: Richard Snodgrass, The temporal query language TQuel, ACM Transactions on Database Systems (TODS), v.12 n.2, p.247-298, June 1987 [doi>10.1145/22952.22956]
• 59: Richard Snodgrass , Ilsoo Ahn, Temporal databases, Computer, v.19 n.9, p.35-41, Sept. 1986 [doi>10.1109/MC.1986.1663327]
• 60: Abdullah Uz Tansel , James Clifford , Shashi Gadia , Sushil Jajodia , Arie Segev , Richard Snodgrass, Temporal databases: theory, design, and implementation, Benjamin-Cummings Publishing Co., Inc., Redwood City, CA, 1993
• 61: R. W. Topor, Domain-independent formulas and databases, Theoretical Computer Science, v.52 n.3, p.281-306, June 1987 [doi>10.1016/0304-3975(87)90113-7]
• 62: TUZHILIN, A. 1993. Applications of temporal databases to knowledge-based simulations. In Temporal Databases: Theory, Design and Implementation, Tansel et el., Eds. Benjamin-Cum mings, Redwood City, Cahf, 580-593
• 63: TUZHmIN, A 1991. Temporal logic as a simulation language. In International Conference on Artificial Intelltgence and Simulatzon.
• 64: Alexander Tuzhilin , James Clifford, A temporal relational algebra as a basis for temporal relational completeness, Proceedings of the sixteenth international conference on Very large databases, p.13-23, September 1990, Brisbane, Australia
• 65: Allen Van Gelder , Rodney W. Topor, Safety and translation of relational calculus, ACM Transactions on Database Systems (TODS), v.16 n.2, p.235-278, June 1991 [doi>10.1145/114325.103712]
• 66: VARDI, M. AND WOLPER, P 1986. An automata-theoretic approach to automatic program verification. In IEEE Symposium on Logic in Computer Science, IEEE Computer Science Press.
• 67: V^RDI, M.Y. 1992. Personal communication.
• 68: M. Y. Vardi, A temporal fixpoint calculus, Proceedings of the 15th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.250-259, January 10-13, 1988, San Diego, California, United States [doi>10.1145/73560.73582]
• 69: Jennifer Widom , Roberta Cochrane , Bruce G. Lindsay, Implementing Set-Oriented Production Rules as an Extension to Starburst, Proceedings of the 17th International Conference on Very Large Data Bases, p.275-285, September 03-06, 1991
• 70: WOLPER, P 1983. Temporallogic can be more expressive Inf Control 56, 72-99.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.0 General
          Subjects: Security, integrity, and protection**

Additional Classification:
  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES

  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.3 Languages
          Subjects: Data description languages (DDL)

General Terms:
Algorithms, Theory

Keywords:
active databases, database integrity, integrity constraints, real-time databases, temporal databases, temporal logic, triggers