Real event records rarely share one clock. One source logs the day an event happened, another logs only the month, and an archive gives only the year. Today's systems quietly pretend every timestamp is precise. A year-stamped fact becomes "January 1st" or "all year long," and the query runs as if nothing were lost. For questions about order, such as "who visited X first after Y did?", that pretence produces confident answers that are not supported by the data. We propose to treat a coarse timestamp as incomplete information: the event happened at some unknown point inside its month or year. Under this reading, a query has certain answers (true however the unknowns are filled in) and possible answers (true for some filling). We then compile queries under this semantics into ordinary SQL over the endpoints of each timestamp's calendar unit, so that a stock relational database does the reasoning.
This connects two literatures that have not met. One is temporal query rewriting, which compiles queries posed against a rule base or ontology (formal definitions of domain concepts, such as "a hostile episode is three consecutive days of threats") into database queries. The other is multi-scale temporal reasoning, which studies how relations like "before" change when you zoom out and an interval shrinks to an indivisible point. The idea borrows its semantics from the first field and its phenomenon from the second. It asks one question: when can certain answers over mixed-precision time be computed by a first-order (plain SQL) query, and when does granularity make this intractable?
Core Claim
Model each fact $f$ as carrying a calendar unit (its granule) $[\ell_f, u_f]$ on a fine day-level timeline. A completion assigns each fact a day $t_f \in [\ell_f, u_f]$. This is Allen and Hayes's notion of a moment, an interval that behaves like a point at coarse observation (A Common-Sense Theory of Time, Short Time Periods). Given rules $\mathcal{O}$ written in a Horn fragment of metric temporal logic and a query $q$, the certain and possible answers are
$$\mathrm{cert}(q) = \bigcap_{c} \mathrm{ans}(q, \mathcal{O}, c), \qquad \mathrm{poss}(q) = \bigcup_{c} \mathrm{ans}(q, \mathcal{O}, c),$$
where $c$ ranges over all completions and $\mathrm{ans}$ is ordinary query answering on the precise timeline $c$.
We make three claims. First, for queries built from before, after, during, and first/last, over rules in which each rule body mentions at most one imprecise fact, both sets are first-order rewritable into SQL range joins over the endpoints $\ell_f, u_f$. For example, "certainly before" becomes $u_{f} < \ell_{g}$ and "possibly before" becomes $\ell_f < u_g$. Second, once a rule combines two imprecise premises, a derived fact inherits a disjunction over their relative order. We conjecture this makes certain-answer evaluation coNP-hard. This mirrors the NP-completeness that disjunctive ambiguity causes in the granular algebra of An Algebra of Granular Temporal Relations for Qualitative Reasoning. Third, outside the exact fragment, the same compiler still yields a sound under-approximation of the certain answers and a sound over-approximation of the possible answers. It can also flag at query time which answers fall in the gap.
Where This Sits
The rewriting side supplies the method but assumes one precise timeline. On the First-Order Rewritability of Ontology-Mediated Queries in Linear Temporal Logic classifies which linear-temporal-logic ontologies admit first-order rewritings over the integers. Its result that some Horn cases are already NC¹-hard constrains our fragment choice. Temporal Conjunctive Query Answering via Rewriting rewrites temporal conjunctive queries into a normal form and reports a 19.09x average speedup over automata on the Traffic Ontology Benchmark. However, it supports no past operators and has no notion of granularity. Ontology-Based Data Access with a Horn Fragment of Metric Temporal Logic compiles non-recursive metric rules to SQL window functions, and we reuse that translation for the fine-timeline part of the rules. Computing Compact Answers to Temporal Path Queries Using SQL shows that coalescing intervals inside SQL is what keeps results from exploding (up to 22x compression; without coalescing, queries fail). We reuse its coalescing so that answer sets come back as compact granule ranges. None of these four papers treats a timestamp as uncertain; all assume the data's time is exact.
The multi-scale side supplies the phenomenon but no database path. The granular algebra of Cohen-Solal et al. and the abstraction operators of Scalable Temporal Reasoning show that relations change under zoom and that coarse reasoning can be sound. Both are constraint networks over a handful of entities, not queries over millions of rows.
Question-answering systems handle granularity in a different way. Multi-granularity Temporal Question Answering over Knowledge Graphs pools day facts into month and year embeddings. Time-aware ReAct Agent for Temporal Knowledge Graph Question Answering (TempAgent) calls day, month, and year filter tools from GPT-4. Self-Improvement Programming for Temporal Knowledge Graph Question Answering (Prog-TQA) has a language model write programs with operators like GetYear and admits to "spurious programs." All three treat granularity as a property of the question over precise data. None distinguishes certain from possible answers when the data is coarse. That distinction, and its compilation, is what is new here.
Research Program
The theory strand fixes the query language and rules, then proves three things: first-order rewritability for the single-imprecise-premise fragment, the hardness conjecture for two imprecise premises, and soundness of the under- and over-approximations in general. We will also characterize a syntactic test for when the two bounds provably coincide, so that an answer can be certified exact.
The systems strand builds a compiler. It takes a formal query plus Horn metric rules and emits PostgreSQL. Granule endpoints become columns, certain and possible predicates become range joins, first/last become anti-joins against possibly-earlier competitors, and answers are coalesced with the window-function method of Adnan et al. For rules, we use temporal rules learned from ICEWS14 by MTLearn, so the rule base is realistic rather than hand-crafted.
The natural-language front end is held fixed and is not a contribution. A single language-model parser maps MultiTQ questions to our formal query language. Every execution back end receives the same parse, which isolates execution semantics from parsing quality.
Baselines
The naive reference point is precise-pretend normalization. Each coarse timestamp is replaced by a point (the start of its granule, or its midpoint) or by the full granule read as "held throughout." The same parsed query is then run with the existing metric-rules-to-SQL translation. This is exactly the skeptic's "just use epochs" position. It uses the same database, parses, and hardware, and we report each variant separately. Beating it means strictly higher precision on certain answers at matched recall, on data with coarse timestamps. On fully precise data we expect a tie, and a tie there is a sanity requirement rather than a loss.
A stronger normalization baseline is probabilistic imputation: sample completions uniformly within granules, answer each sample, and rank answers by frequency. We give it the same wall-clock budget as our compiler and a generous sample count. Beating it means matching its ranking quality while returning exact certainty labels at a fraction of the runtime.
The strongest existing question-answering system is TempAgent, which reports 70.2% Hits@1 on MultiTQ with GPT-4, a 41.3% improvement over MultiQA (0.293 Hits@1). Prog-TQA reports only relative gains over MultiQA; no absolute MultiTQ number was found on Lacuna. On original MultiTQ, we aim to match TempAgent's 70.2% and do not claim to exceed it, since parsing dominates there. On the coarsened benchmark below, no reported result was found on Lacuna for any system. We will rerun TempAgent's tool design against the coarsened graph, with the same underlying language model where feasible. Beating it means higher precision of the answers it asserts, measured against the gold certain set.
Two ablations isolate the key ingredient. The first keeps our compiler but replaces certain-answer predicates with possible-answer predicates everywhere. The second keeps certain semantics but drops the two-premise flagging, which shows how often the approximation gap actually arises.
Why not just…?
Why not just normalize every timestamp to the finest unit and run standard metric rewriting? This is the real threat, and on today's MultiTQ it probably ties. The ICEWS facts underneath are day-level, and month- or year-level questions can be answered by truncating dates. The proposal stands or falls on data whose timestamps are themselves coarse. There, "first after Y" among several events stamped with the same year has no supported answer, yet normalization emits one. Experiment two measures exactly how often this happens as coarsening grows. If normalization's certain-answer precision stays within a point or two of ours at 30% coarsening, we will report that the problem is marginal in practice.
Why not just let a tool-calling agent or program generator handle granularity? TempAgent reports that coarse year-level questions degrade because of the volume of day facts to aggregate. Prog-TQA admits that generated programs can be spuriously right. Neither can say that an answer is unsupported, because neither reasons over completions. Our fixed-parse design makes this testable: any agent failure we report is a failure of execution semantics, not of parsing.
Why not just hand-write the endpoint SQL, without a rewriting theory? For bare before/after queries, hand-written endpoint comparisons are correct, and our compiler should reproduce them. The difference appears with rules. A derived concept, such as an MTLearn-learned "sustained escalation" window over two coarse premises, inherits ordering disjunctions that hand-written SQL silently gets wrong. The theory says exactly where that happens and certifies when the SQL is still exact. Experiment three counts how often learned rules fall outside the exact fragment.
Proposed Experiments and Decisive Checks
The first experiment is a sanity check on original MultiTQ. All back ends share one parse, and we report Hits@1 overall and by granularity against TempAgent's 70.2%. Our compiler should equal normalization here.
The second experiment is the decisive one: Coarsened MultiTQ. We coarsen a fraction $p \in \{0.1, 0.3, 0.5\}$ of ICEWS05-15 facts to month or year granularity and keep the MultiTQ questions. Gold certain and possible sets are computed by exhaustive completion on sampled subgraphs small enough to enumerate. We report precision and recall of asserted answers against gold certain sets, the fraction of questions whose certain set is empty, and Hits@1 against the hidden original day truth. The idea is supported if normalization's precision falls steeply with $p$ while ours stays at 1.0 by construction with competitive recall.
The third experiment runs the same questions over derived concepts from MTLearn rules. It measures how often queries leave the exact fragment and how wide the gap between the certain and possible bounds becomes.
The fourth experiment measures cost. We compare PostgreSQL runtime and answer compaction against normalized SQL and against sampling, as fact count and $p$ grow. For reference, Adnan et al. report 154 seconds for their densest contact-tracing setting. A certain-answer overhead within a small constant factor of normalized SQL would show that correctness under coarse time does not require leaving the relational engine.
References
- A Common-Sense Theory of Time
- Short Time Periods
- An Algebra of Granular Temporal Relations for Qualitative Reasoning
- On the First-Order Rewritability of Ontology-Mediated Queries in Linear Temporal Logic (Extended Abstract)
- Temporal Conjunctive Query Answering via Rewriting
- Ontology-Based Data Access with a Horn Fragment of Metric Temporal Logic
- Computing Compact Answers to Temporal Path Queries Using SQL
- Scalable Temporal Reasoning
- Multi-granularity Temporal Question Answering over Knowledge Graphs
- Time-aware ReAct Agent for Temporal Knowledge Graph Question Answering
- Self-Improvement Programming for Temporal Knowledge Graph Question Answering
- MTLearn: Extracting Temporal Rules Using Datalog Rule Learners