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: h1fe51ce8fe23ee4f
Venue: PODS
Year: 1993
Pagerank: 5.0806471e-05
Overall Rank: 10,092 | 32.15%
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,711	Foundations of Data-Aware Process Analysis: A Database Theory Perspective	2013	PODS	8.1038896e-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
930	A Temporal Framework for Database Specifications	1982	VLDB	0.00013011733
1,491	Event Specification in an Active Object-Oriented Database	1992	SIGMOD	0.00010508893
6,976	Real-Time Integrity Constraints (extended abstract)	1992	PODS	5.6299711e-05
7,595	A Transaction Logic for Database Specification	1988	SIGMOD	5.4874132e-05

Semantically Similar Papers

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