On the Feasibility of Checking Temporal Integrity Constraints

Summary: Analyzes feasibility of checking temporal integrity constraints in first-order temporal logic fragments, focusing on where quantifiers occur relative to temporal operators. Key findings: a single quantifier under a temporal operator causes undecidability; if no quantifiers lie inside temporal scope and all quantifiers are universal, checking is EXPTIME decidable. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 999
Venue: PODS
Year: 1993
Pagerank: 5.1972596e-05
Overall Rank: 9,905 | 32.05%
DOI: 10.1145/153850.153876

Incoming Non-self Citations Over Time

Authors

1. Jan Chomicki (Kansas State University)
2. Damian Niwiński (University of Warsaw)

BibTeX Citation

@inproceedings{chomicki_pods93,
        address = {New York, NY, USA},
        series = {{PODS} '93},
        title = {{On the Feasibility of Checking Temporal Integrity Constraints}},
        url = {https://dl.acm.org/doi/10.1145/153850.153876},
        doi = {10.1145/153850.153876},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Chomicki, Jan and Niwiński, Damian},
        year = {1993}
}

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
2,653	Foundations of Data-Aware Process Analysis: A Database Theory Perspective	2013	PODS	8.2898925e-05

Outgoing Citations (Sorted by Pagerank)

Showing 4 of 4 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
906	A Temporal Framework for Database Specifications	1982	VLDB	0.00013310115
1,451	Event Specification in an Active Object-Oriented Database	1992	SIGMOD	0.00010745897
6,836	Real-Time Integrity Constraints (extended abstract)	1992	PODS	5.7580859e-05
7,452	A Transaction Logic for Database Specification	1988	SIGMOD	5.6133619e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	633	The Complexity of Querying Indefinite Data about Linearly Ordered Domains (Preliminary Version)	1992	PODS
2	2,999	A Temporal Relational Algebra as a Basis for Temporal Relational Completeness	1990	VLDB
3	13,063	Integrity Constraint and Rule Maintenance in Temporal Deductive Knowledge Bases	1993	VLDB
4	4,238	Polynomial Time Query Processing in Temporal Deductive Databases	1990	PODS
5	4,439	Temporal Deductive Databases and Infinite Objects	1988	PODS
6	6,836	Real-Time Integrity Constraints (extended abstract)	1992	PODS
7	4,536	On the Representation of Infinite Temporal Data and Queries (Extended Abstract)	1991	PODS
8	4,242	Specification, Semantics, and Enforcement of Dynamic Database Constraints	1984	VLDB
9	14,099	Temporal Integrity Constraints with Indeterminacy	2000	VLDB
10	3,171	Temporal versus First-Order Logic to Query Temporal Databases	1996	PODS