More Web Proxy on the site http://driver.im/

Article

Free access

On the feasibility of checking temporal integrity constraints

Authors:

Damian NiwińskiAuthors Info & Claims

PODS '93: Proceedings of the twelfth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems

Pages 202 - 213

https://doi.org/10.1145/153850.153876

Published: 01 August 1993 Publication History

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]

CHOMICKI, J. History-less Checking of Dynamic Integrity Constraints. In IEEE International Conference on Data Engineering (Phoenix, Arizona, February 1992).

Digital Library

[2]

CHOMICKI,J. Real-Time Integrity Constraints.In A CM SIGA CT-SIGMOD- SIGART Symposium on Principles of Database Systems (San Diego, California, June 1992).

Digital Library

[3]

DAYAL, U., AND AL. The HiPAC Project: Combining Active Databases and Timing Constraints. SIGMOD Record 17, 1 (March 198S), 51-70.

Digital Library

[4]

DE CASTILHO, J., CASANOVA, M., AND Fua- TADO, A. A Temporal Framework for Database Specifications. In international Conference on Very Large Data Bases (1982), pp. 280-291.

Digital Library

[5]

EMERSON, E. Temporal and Modal Logic. In Handbook of Theoretical Computer Science, J. van Leeuwen, Ed., vol. B. Elsevier/MIT Press, 1990, ch. 16, pp. 995-1072.

Digital Library

[6]

FINGER, M., AND GABSAY, D. Adding a temporal dimension to a logic system. Journal o} Logic, Language and Information (1992).

[7]

GEHANI, N., JAGADISH, H., AND SHMUELI, O. Event Specification in an Active Object- Oriented Database. In A CM SIGMOD International Conference on Management of Data (1992), pp. 81-90.

Digital Library

[8]

GEaTZ, M., AND LmWCK, U. Deriving Integrity Maintaining Triggers from Transition Graphs. In IEEE International Conference on Data Engineering (1993).

Digital Library

[9]

HOLSMANN, K., AND SAAKE, G. Theoretical Foundations of Handfing Large Substitution Sets in Temporal Integrity Monitoring. Acta Informatica 28, 4 (1991).

Digital Library

[10]

LIPECK, U., AND SAAKE, G. Monitoring Dynamic Integrity Constraints Based on Temporal Logic. In.formation Systems 12, 3 (1987), 255-269.

Digital Library

[11]

PNUELI, A. Applications of Temporal Logic to the Specification and Verification of Reactive Systems: a Survey of Current Trends. In Current Trends in Concurrency. Springer-Verlag, LNCS 224, 1986.

Digital Library

[12]

QIAN, X., AND WALDINGER, R,. A Transaction Logic for Database Specification. In A CM SIGMOD International Conference on Management o.f Data (1988), pp. 243-250.

Digital Library

[13]

SISTLA, A. On Characterization of Safety and Liveness Properties in Temporal Logic. In A CM Symposium on Principles of Distributed Computing (1985), pp. 39-48.

Digital Library

[14]

SISTLA, A., AND CLARKE, E. The Complexity of Propositional Linear Temporal Logics. Journal o} the ACM 32, 3 (July 1985), 733- 749.

Digital Library

[15]

SISTLA, A., AND WOLFSON, O. Temporal Triggers in Active Databases. IEEE Transactions on Knowledge and Data Engineering (1993). To appear.

Digital Library

[16]

SNODGRASS, R. Temporal Databases. In Theories and Methods of Spatio-Temporal Rea- I. Campari, and U. Formentini, Eds., Springer- Verlag, LNCS 639, pp. 22-64.

Digital Library

Cited By

Chowdhury OJia LGarg DDatta A(2014)Temporal Mode-Checking for Runtime Monitoring of Privacy PoliciesProceedings of the 16th International Conference on Computer Aided Verification - Volume 855910.1007/978-3-319-08867-9_9(131-149)Online publication date: 18-Jul-2014
https://dl.acm.org/doi/10.1007/978-3-319-08867-9_9
Calvanese DDe Giacomo GMontali MHull RFan W(2013)Foundations of data-aware process analysisProceedings of the 32nd ACM SIGMOD-SIGACT-SIGAI symposium on Principles of database systems10.1145/2463664.2467796(1-12)Online publication date: 22-Jun-2013
https://dl.acm.org/doi/10.1145/2463664.2467796
Toman DNiwiński D(2005)First-order queries over temporal databases inexpressible in temporal logicAdvances in Database Technology — EDBT '9610.1007/BFb0014160(305-324)Online publication date: 10-Jun-2005
https://doi.org/10.1007/BFb0014160
Show More Cited By

Index Terms

On the feasibility of checking temporal integrity constraints
1. Information systems
  1. Data management systems
    1. Query languages
2. Theory of computation

Recommendations

Model checking discounted temporal properties
Tools and algorithms for the construction and analysis of systems (TACAS 2004)

Temporal logic is two-valued: formulas are interpreted as either true or false. When applied to the analysis of stochastic systems, or systems with imprecise formal models, temporal logic is therefore fragile: even small changes in the model can lead to ...
Integrity Constraints in Temporal Relational Databases
ITCC '04: Proceedings of the International Conference on Information Technology: Coding and Computing (ITCC'04) Volume 2 - Volume 2

The article addresses the key issues of integrity constraints intemporal data within the relational framework. These issues includerepresentation of temporal data, temporal grouping identifiers,primary keys of temporal relations and other forms of ...
Interval vs. Point Temporal Logic Model Checking: An Expressiveness Comparison

In recent years, model checking with interval temporal logics is emerging as a viable alternative to model checking with standard point-based temporal logics, such as LTL, CTL, CTL*, and the like. The behavior of the system is modeled by means of (...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

PODS '93: Proceedings of the twelfth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems

August 1993

312 pages

ISBN:0897915933

DOI:10.1145/153850

Chairman:
Catriel Beeri

Copyright © 1993 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 August 1993

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

SIGMOD/PODS93

Sponsor:

SIGMOD/PODS93: Joint ACM SIGMOD International Conference on Management of Data and ACM SIGMOD

May 25 - 28, 1993

D.C., Washington, USA

Acceptance Rates

PODS '93 Paper Acceptance Rate 26 of 115 submissions, 23%;

Overall Acceptance Rate 642 of 2,707 submissions, 24%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

6
Total Citations
View Citations
281
Total Downloads

Downloads (Last 12 months)10
Downloads (Last 6 weeks)1

Reflects downloads up to 12 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Chowdhury OJia LGarg DDatta A(2014)Temporal Mode-Checking for Runtime Monitoring of Privacy PoliciesProceedings of the 16th International Conference on Computer Aided Verification - Volume 855910.1007/978-3-319-08867-9_9(131-149)Online publication date: 18-Jul-2014
https://dl.acm.org/doi/10.1007/978-3-319-08867-9_9
Calvanese DDe Giacomo GMontali MHull RFan W(2013)Foundations of data-aware process analysisProceedings of the 32nd ACM SIGMOD-SIGACT-SIGAI symposium on Principles of database systems10.1145/2463664.2467796(1-12)Online publication date: 22-Jun-2013
https://dl.acm.org/doi/10.1145/2463664.2467796
Toman DNiwiński D(2005)First-order queries over temporal databases inexpressible in temporal logicAdvances in Database Technology — EDBT '9610.1007/BFb0014160(305-324)Online publication date: 10-Jun-2005
https://doi.org/10.1007/BFb0014160
Gançarski S(2002)Database Versions to Represent Bitemporal DatabasesDatabase and Expert Systems Applications10.1007/3-540-48309-8_78(832-841)Online publication date: 18-Jun-2002
https://doi.org/10.1007/3-540-48309-8_78
Bidoit NDe Amo S(1998)A first step towards implementing dynamic algebraic dependencesTheoretical Computer Science10.1016/S0304-3975(97)00088-1190:2(115-149)Online publication date: Jan-1998
https://doi.org/10.1016/S0304-3975(97)00088-1
Chomicki J(1995)Efficient checking of temporal integrity constraints using bounded history encodingACM Transactions on Database Systems10.1145/210197.21020020:2(149-186)Online publication date: 1-Jun-1995
https://dl.acm.org/doi/10.1145/210197.210200

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents