Temporal Deductive Databases and Infinite Objects
Summary: Temporal deductive DBs with one monadic successor per predicate to model recurring events, yielding infinite least fixpoints and answers; introduce “infinite objects” to make some infinite fixpoints finitely computable. Prove query processing is data‑PSPACE complete, give exponential iterative (bottom‑up) bounds driven by non‑temporal components (temporal part linear), show fixpoints are periodic, provide safety/infinite‑fixpoint detection algorithms, and contrast decidability with systems with unrestricted function symbols. (summarized by gpt-5-mini on Feb 09 2026)
Incoming Non-self Citations Over Time
Authors
- 1. Jan Chomicki (Rutgers University)
- 2. Tomasz Imielinski (Rutgers University)
BibTeX Citation
@inproceedings{chomicki_pods88,
address = {New York, NY, USA},
series = {{PODS} '88},
title = {{Temporal Deductive Databases and Infinite Objects}},
url = {https://dl.acm.org/doi/10.1145/308386.308416},
doi = {10.1145/308386.308416},
booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
publisher = {Association for Computing Machinery},
author = {Chomicki, Jan and Imielinski, Tomasz},
year = {1988}
}Incoming Citations (Sorted by Pagerank)
Showing 5 of 5 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 |
| 4,235 | Relational Specifications of Infinite Query Answers | 1989 | SIGMOD | 6.8167527e-05 |
| 4,238 | Polynomial Time Query Processing in Temporal Deductive Databases | 1990 | PODS | 6.8109945e-05 |
| 4,348 | Handling Infinite Temporal Data | 1990 | PODS | 6.7507186e-05 |
| 4,536 | On the Representation of Infinite Temporal Data and Queries (Extended Abstract) | 1991 | PODS | 6.641885e-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 |
|---|---|---|---|---|
| 1,498 | Safety of Recursive Horn Clauses With Infinite Relations | 1987 | PODS | 0.00010567892 |
| 4,793 | Time Modeling in Office Information Systems | 1985 | SIGMOD | 6.504062e-05 |
Semantically Similar Papers
| # | Overall Rank | Paper | Year | Venue |
|---|---|---|---|---|
| 1 | 4,353 | Chase Termination for Guarded Existential Rules | 2015 | PODS |
| 2 | 5,523 | Dense-Order Constraint Databases (Extended Abstract) | 1995 | PODS |
| 3 | 4,242 | Specification, Semantics, and Enforcement of Dynamic Database Constraints | 1984 | VLDB |
| 4 | 633 | The Complexity of Querying Indefinite Data about Linearly Ordered Domains (Preliminary Version) | 1992 | PODS |
| 5 | 3,171 | Temporal versus First-Order Logic to Query Temporal Databases | 1996 | PODS |
| 6 | 6,077 | Safety of Datalog Queries over Infinite Databases | 1989 | PODS |
| 7 | 4,235 | Relational Specifications of Infinite Query Answers | 1989 | SIGMOD |
| 8 | 4,348 | Handling Infinite Temporal Data | 1990 | PODS |
| 9 | 4,536 | On the Representation of Infinite Temporal Data and Queries (Extended Abstract) | 1991 | PODS |
| 10 | 4,238 | Polynomial Time Query Processing in Temporal Deductive Databases | 1990 | PODS |