DBScholar

Back to papers

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
hfbd56b29fd74abcb
Venue
PODS
Year
1996
Pagerank
7.5126678e-05
Overall Rank
3,223 | 78.34%
DOI
10.1145/237661.237674

Incoming Non-self Citations Over Time

Authors

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,164 Verification of Communicating Data-Driven Web Services 2006 PODS 8.9346715e-05
2,711 Foundations of Data-Aware Process Analysis: A Database Theory Perspective 2013 PODS 8.1038896e-05
4,170 Specification and Verification of Data-driven Web Services 2004 PODS 6.7615597e-05
6,426 Temporal Alignment 2012 SIGMOD 5.7891979e-05
9,353 Verification of Relational Transducers for Electronic Commerce 2000 PODS 5.1886678e-05
Previous Page 1 / 1 Next

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,344 Temporal Logic & Historical Databases 1991 VLDB 8.603615e-05
3,054 A Temporal Relational Algebra as a Basis for Temporal Relational Completeness 1990 VLDB 7.6997974e-05
Previous Page 1 / 1 Next

Semantically Similar Papers