ACM SIGMOD Anthology ACM SIGMOD dblp.uni-trier.de

On the Feasibility of Checking Temporal Integrity Constraints.

Jan Chomicki, Damian Niwinski: On the Feasibility of Checking Temporal Integrity Constraints. PODS 1993: 202-213
@inproceedings{DBLP:conf/pods/ChomickiN93,
  author    = {Jan Chomicki and
               Damian Niwinski},
  title     = {On the Feasibility of Checking Temporal Integrity Constraints},
  booktitle = {Proceedings of the Twelfth ACM SIGACT-SIGMOD-SIGART Symposium
               on Principles of Database Systems, May 25-28, 1993, Washington,
               DC},
  publisher = {ACM Press},
  year      = {1993},
  isbn      = {0-89791-593-3},
  pages     = {202-213},
  ee        = {http://doi.acm.org/10.1145/153850.153876, db/conf/pods/ChomickiN93.html},
  crossref  = {DBLP:conf/pods/93},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

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.

Copyright © 1993 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.


Load The ACM SIGMOD Anthology, CDROM Edition, Volume 1-3, PODS '82-'98. and ... Load The ACM SIGMOD Anthology, Silver Edition, DVD 1, Proceedings. and ... BibTeX

Printed Edition

Proceedings of the Twelfth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, May 25-28, 1993, Washington, DC. ACM Press 1993, ISBN 0-89791-593-3
Contents BibTeX

Online Edition: ACM Digital Library

[Abstract and Index Terms]
[Full Text in PDF Format, 976 KB]

References

[1]
Jan Chomicki: History-less Checking of Dynamic Integrity Constraints. ICDE 1992: 557-564 BibTeX
[2]
Jan Chomicki: Real-Time Integrity Constraints. PODS 1992: 274-282 BibTeX
[3]
Umeshwar Dayal, Barbara T. Blaustein, Alejandro P. Buchmann, Upen S. Chakravarthy, Meichun Hsu, R. Ledin, Dennis R. McCarthy, Arnon Rosenthal, Sunil K. Sarin, Michael J. Carey, Miron Livny, Rajiv Jauhari: The HiPAC Project: Combining Active Databases and Timing Constraints. SIGMOD Record 17(1): 51-70(1988) BibTeX
[4]
José Mauro Volkmer de Castilho, Marco A. Casanova, Antonio L. Furtado: A Temporal Framework for Database Specifications. VLDB 1982: 280-291 BibTeX
[5]
...
[6]
...
[7]
Narain H. Gehani, H. V. Jagadish, Oded Shmueli: Event Specification in an Active Object-Oriented Database. SIGMOD Conference 1992: 81-90 BibTeX
[8]
Michael Gertz, Udo W. Lipeck: Deriving Integrity Maintaining Triggers from Transition Graphs. ICDE 1993: 22-29 BibTeX
[9]
Klaus Hülsmann, Gunter Saake: Theoretical Foundations of Handling Large Substitution Sets in Temporal Integrity Monitoring. Acta Inf. 28(4): 365-407(1991) BibTeX
[10]
Udo W. Lipeck, Gunter Saake: Monitoring dynamic integrity constraints based on temporal logic. Inf. Syst. 12(3): 255-269(1987) BibTeX
[11]
...
[12]
Xiaolei Qian, Richard J. Waldinger: A Transaction Logic for Database Specification. SIGMOD Conference 1988: 243-250 BibTeX
[13]
A. Prasad Sistla: On Characterization of Safety and Liveness Properties in Temporal Logic. PODC 1985: 39-48 BibTeX
[14]
A. Prasad Sistla, Edmund M. Clarke: The Complexity of Propositional Linear Temporal Logics. J. ACM 32(3): 733-749(1985) BibTeX
[15]
A. Prasad Sistla, Ouri Wolfson: Temporal Triggers in Active Databases. IEEE Trans. Knowl. Data Eng. 7(3): 471-486(1995) BibTeX
[16]
...

Referenced by

  1. David Toman, Damian Niwinski: First-Order Queries over Temporal Databases Inexpressible in Temporal Logic. EDBT 1996: 307-324
  2. Nicole Bidoit, Sandra de Amo: A First Step Towards Implementing Dynamic Algebraic Dependencies. ICDT 1995: 308-321
  3. Jan Chomicki: Temporal Inegrity Constraints in Relational Databases. IEEE Data Eng. Bull. 17(2): 33-37(1994)
BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Sat May 16 23:34:08 2009