Temporal versus First-Order Logic to Query Temporal Databases

Summary: Shows that for temporal databases modeled via timestamped relations, first-order logic on the timestamp representation strictly subsumes (extended) temporal logic in the predicate/relational case, unlike the propositional setting. Novel proof via a communication-complexity argument constructing FO queries on timestamps that are not definable in temporal logic. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1075
Venue: PODS
Year: 1996
Pagerank: 7.6691319e-05
Overall Rank: 3,171 | 78.25%
DOI: 10.1145/237661.237674

Incoming Non-self Citations Over Time

Authors

1. Serge Abiteboul (INRIA; Stanford University)
2. Laurent Herr (INRIA)
3. Jan Van den Bussche (INRIA; University of Antwerp)

BibTeX Citation

@inproceedings{abiteboul_pods96,
        address = {New York, NY, USA},
        series = {{PODS} '96},
        title = {{Temporal versus First-Order Logic to Query Temporal Databases}},
        url = {https://dl.acm.org/doi/10.1145/237661.237674},
        doi = {10.1145/237661.237674},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Abiteboul, Serge and Herr, Laurent and Van den Bussche, Jan},
        year = {1996}
}

Incoming Citations (Sorted by Pagerank)

Showing 5 of 5 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
2,125	Verification of Communicating Data-Driven Web Services	2006	PODS	9.1334411e-05
2,653	Foundations of Data-Aware Process Analysis: A Database Theory Perspective	2013	PODS	8.2898925e-05
4,080	Specification and Verification of Data-driven Web Services	2004	PODS	6.9165722e-05
6,805	Temporal Alignment	2012	SIGMOD	5.7678408e-05
9,178	Verification of Relational Transducers for Electronic Commerce	2000	PODS	5.3077309e-05

Outgoing Citations (Sorted by Pagerank)

Showing 2 of 2 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
2,304	Temporal Logic & Historical Databases	1991	VLDB	8.7769303e-05
2,999	A Temporal Relational Algebra as a Basis for Temporal Relational Completeness	1990	VLDB	7.8712594e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	4,242	Specification, Semantics, and Enforcement of Dynamic Database Constraints	1984	VLDB
2	4,439	Temporal Deductive Databases and Infinite Objects	1988	PODS
3	9,905	On the Feasibility of Checking Temporal Integrity Constraints	1993	PODS
4	2,999	A Temporal Relational Algebra as a Basis for Temporal Relational Completeness	1990	VLDB
5	13,162	Temporal Relationships in Databases	1988	VLDB
6	709	Logical Modeling Of Temporal Data	1987	SIGMOD
7	13,163	A logical framework for temporal deductive databases	1988	VLDB
8	2,304	Temporal Logic & Historical Databases	1991	VLDB
9	5,941	Point vs. Interval-based Query Languages for Temporal Databases (Extended Abstract)	1996	PODS
10	4,536	On the Representation of Infinite Temporal Data and Queries (Extended Abstract)	1991	PODS