On the feasibility of checking temporal integrity constraints

ABSTRACT

We analyze the computational feasibility of checking temporal integrity constraints formulated in some sublanguages of first-order temporal logic. Our results illustrate the impact of the quantification on the complexity of this problem. The presence of a single quantifier in the scope of a temporal operator makes the problem undecidable. On the other hand, if no quantifiers are in the scope of a temporal operator and all the quantifiers are universal, temporal integrity checking can be done in exponential time.

REFERENCES

• 1: 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
• 2: 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]
• 3: 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]
• 4: 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
• 5: E. Allen Emerson, Temporal and modal logic, Handbook of theoretical computer science (vol. B): formal models and semantics, MIT Press, Cambridge, MA, 1991
• 6: FINGER, M., AND GABSAY, D. Adding a temporal dimension to a logic system. Journal o} Logic, Language and Information (1992).
• 7: 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
• 8: 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
• 9: 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]
• 10: 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]
• 11: 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
• 12: 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
• 13: A. P. Sistla, On characterization of safety and liveness properties in temporal logic, Proceedings of the fourth annual ACM symposium on Principles of distributed computing, p.39-48, August 1985, Minaki, Ontario, Canada [doi>10.1145/323596.323600]
• 14: A. P. Sistla , E. M. Clarke, The complexity of propositional linear temporal logics, Journal of the ACM (JACM), v.32 n.3, p.733-749, July 1985 [doi>10.1145/3828.3837]
• 15: 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]
• 16: Richard Thomas Snodgrass, Temporal Databases, Proceedings of the International Conference GIS - From Space to Territory: Theories and Methods of Spatio-Temporal Reasoning on Theories and Methods of Spatio-Temporal Reasoning in Geographic Space, p.22-64, September 21-23, 1992

INDEX TERMS

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

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT

General Terms:
Languages, Security