TQuel Paper: Implementing Temporal Operators in Postgres

With UPDATE/DELETE FOR PORTION OF looking like it will land in Postgres 19, I’ve been thinking about next steps. I read a very helpful paper on temporal relational algebra last May by Richard Snodgrass. Here are some notes on it.

The paper was “An Overview of TQuel”. It’s Chapter 6 in Temporal Databases: Theory, Design, and Implementation from 1993.

TQuel was an extension to Quel, the query language for Ingres. Ingres, of course, was the predecessor to Postgres!

My main motivation reading this paper was to learn more about the algebraic identities of temporal relational operators. A query planner depends on such identities to transform your query into a more efficient shape. For instance, if you can filter rows before joining tables instead of after, you’ll get a much faster execution. The useful identities for regular relational operators are well-known, but what about temporal operators? If we ever want to support temporal joins and setops in Postgres, we have to figure that out.

I implemented some temporal operators in SQL in my temporal_ops extension. Since they are just SQL, I don’t have to worry about optimizer correctness. But it would be better to have dedicated executor nodes. That should get us closer to an optimal implementation. I want to teach that extension to inject CustomScans . . . somehow . . . maybe with a post-parser hook? Once I have that, I can experiment with planner transformations.

But as a first step, I’m trying to see what is in the research already. One surprise in Snodgrass’s paper was that TQuel valid-times are not intervals (like Postgres rangetypes or SQL:2011 PERIODs). Instead they are sets of “chronons”: all the times that the tuple is true, whether contiguous or not. I can see how that might be a more “pure” representation. There is something artificial to forcing the valid-time to be only a single contiguous stretch of time. Fortunately a set of chronons is exactly a multirange, so it is still something you could represent in Postgres.

A bigger surprise was that TQuel tracks valid-time for each attribute, instead of for the overall tuple. That is a bit more complicated! Actually it reminds me of how Date/Darwen/Lorentzos and Johnston both propose a separate-table-per-attribute structure (which Date calls “Sixth Normal Form”). You can see my temporal databases bibliography for more about that. There are hints in both of their books that they suspect this is asking too much from ordinary database users. And Snodgrass’s choice here made me worried that his results would be hard to apply to a practical RDBMS like Postgres.

But then I realized that any SQL:2011 valid-time tuple can be trivially represented in TQuel’s format: just copy the tuple valid-time onto each attribute. In fact Snodgrass has a term for that: a “homogeneous relation”. (Such TQuel relations still have multirange valid-time though.) That makes me hopeful that identities that are true in TQuel might still be true in SQL:2011. They might not be though, if TQuel operators on homogeneous relations don’t always have homogeneous relation results: if for those operators homogeneous relations aren’t “closed”.

Also TQuel has no nulls and no duplicates, but even that may not matter much. A valid-time never has null endpoints. Well with Postgres rangetypes we do use null to represent “unbounded”, but that has different behavior than a normal null. It is no different than using, say, 3000-01-01, except it works for any base type (unlike 'Infinity'). And I don’t think valid-time adds any further differences between duplicate and non-duplicate behavior. So the TQuel algebra should be as applicable as any non-temporal no-NULL no-duplicate algebra. At least it doesn’t add any new issues.

One result in the paper is that for homogeneous relations, TQuel operators are “snapshot reducible”. For such relations, “the valid-time operators ∪̂, −̂, ⨯̂, σ̂, and π̂ reduce to their snapshot counterparts.” In other words, if you want a final result at a single time t (a snapshot), you can evaluate temporal operators and then take the snapshot (which is slow) or take snapshots first, from all your base tables, and then evaluate non-temporal operators. You can “push down the qual” that valid_at @> now() (or whatever time you care about). It is a homomorphism:

σ(R ⨯̂ S) = σ(R) × σ(S)

I think this is the most common query shape against temporal tables, especially for complicated reports. You don’t need the whole history; you just want the result at a given moment. It means that if you are converting an existing app to use application-time tables, you don’t need temporal operators yet. You don’t even need to rewrite the queries. Just declare views that filter your history tables by now() (or by some variable), and run the queries on them. I talked about this in my PG DATA 2026 talk Migrating to a Temporal Schema.

The real reward of the paper though was Theorem 13. I found this a couple years ago from skimming, and I had wanted to read the whole thing ever since. Snodgrass says that most traditional algebraic identities are preserved by his temporal operators, but not all. A big exception is that Cartesian product does not distribute over difference:

Q ⨯̂ (R −̂ S) ≢ (Q ⨯̂ R) −̂ (Q ⨯̂ S)

In SQL the name for “difference” is EXCEPT. Since joins are all defined in terms of Cartesian product, this is a big one.

Why doesn’t this work?

To explore that question, I vibe-coded a “relational calculator”, relsim. It is a Racket library that lets you evaluate tuples, relations, and operators on them. It supports all the traditional operators (even division!), and also temporal versions. There are temporal operators for SQL:2011 tuples (a range for the whole tuple), multirange tuples (the same but a multirange), and TQuel tuples (a multirange for each attribute). To make it more SQL-like, I allow nulls and duplicates.

You don’t need to know Racket to use it. Actually I haven’t written Lisp since college myself. But I chose a Lisp so I could get a free parser and REPL, with syntax as math-like as possible. It is pretty easy to use, I think.

I used relsim to find a counterexample to the Cartesian-product-over-difference identity, and then “step through it” to see where it went wrong. Claude and I wrote up the investigation. Using TQuel-style tuples, suppose we have these relations:

     Q
-------------
'a', {[0,20)}

     R
-------------
'b', {[0,20)}

     S
-------------
'b', {[5,10)}

Each relation has one attribute: a string with an attached multirange valid-time. And each relation has a single row.

Then for the left-hand side of the identity, we have:

Q ⨯̂ (R −̂ S)
{('a', {[0,20)})} ⨯̂ ({('b', {[0,20)})} −̂ {('b', {[5,10)})})
{('a', {[0,20)})} ⨯̂ {('b', {[0,5), [10,20)})}
{('a', {[0,20)}, 'b', {[0,5), [10,20)})}

Here I’m using {...} for a relation (since it’s a set of tuples), and (...) for a tuple. For the valid-time I’m using Postgres multirange notation.

For the right-hand side, we have:

(Q ⨯̂ R) −̂ (Q ⨯̂ S)
({('a', {[0,20)})} ⨯̂ {('b', {[0,20)})}) −̂ ({('a', {[0,20)})} ⨯̂ {('b', {[5,10)})})
{('a', {[0,20)}, 'b', {[0,20)})} −̂ {('a', {[0,20)}, 'b', {[5,10)})}
{('a', {}, 'b', {[0,5), [10,20)})}

So b is the same, but we lost all of a! I’m not sure I have an intuitive explanation for “why” that happens.

What about non-TQuel tuples? I tried those too, and sadly got the same result. For example with rangetypes (where two tuples might be needed for a difference result), the LHS:

Q ⨯̂ (R −̂ S)
{('a', [0,20))} ⨯̂ ({('b', [0,20))} −̂ {('b', [5,10))})
{('a', [0,20))} ⨯̂ {('b', [0,5)),
                   ('b', [10,20))}
{('a', [0,20), 'b', [0,5), [0,5)),
 ('a', [0,20), 'b', [10,20), [10,20))}

Note that here for Cartesian product I’m keeping the inputs’ valid-times, as if they were regular attributes. Then I add a result valid-time that is the inputs’ intersection.

Versus the RHS:

(Q ⨯̂ R) −̂ (Q ⨯̂ S)
({('a', [0,20))} ⨯̂ {('b', [0,20))}) −̂ ({('a', [0,20))} ⨯̂ {('b', [5,10))})
{('a', [0,20), 'b', [0,20), [0,20))} −̂ {('a', [0,20), 'b', [5,10), [5,10))}
{('a', [0,20), 'b', [0,20), [0,20))}

Again, different! Here the problem is that the RHS didn’t subtract anything. That’s because the old valid-times didn’t match, and we compare those like regular attributes.

But if we drop input valid-times, then the algebra works out! The LHS:

Q ⨯̂ (R −̂ S)
{('a', [0,20))} ⨯̂ ({('b', [0,20))} −̂ {('b', [5,10))})
{('a', [0,20))} ⨯̂ {('b', [0,5)),
                   ('b', [10,20))}
{('a', 'b', [0,5)),
 ('a', 'b', [10,20))}

and the RHS:

(Q ⨯̂ R) −̂ (Q ⨯̂ S)
({('a', [0,20))} ⨯̂ {('b', [0,20))}) −̂ ({('a', [0,20))} ⨯̂ {('b', [5,10))})
{('a', 'b', [0,20))} −̂ {('a', 'b', [5,10))}
{('a', 'b', [0,5)),
 ('a', 'b', [10,20))}

We got the same answer! The same thing happens for multirange valid-times. Keeping the original valid-times spoils the algebra.

I find several layers of irony here.

One of the main features of Anton Dignös’s work is precisely preserving the input valid-times (for example the “extends” operator in his “Temporal Alignment” paper), and in temporal_ops I tried to follow that. That can be useful for scaling aggregates, also for filtering (e.g. find all hotel reservations of a certain length) and joining (apply a discount depending on reservation length). But maybe it should not be the default. If the user wants them, they can SELECT them explicitly. And indeed for these examples, the input valid-times are really used internally by the temporal operator (by the aggregation function or the join’s theta condition), and they don’t need to be in the result.

Another irony is that Snodgrass’s TSQL2 and SQL:2011 PERIODs have been criticized for not treating valid-time as an attribute within relational theory. And so for PERIODs you can’t SELECT them, put them in a VIEW or subquery, pass them to a function or return them, GROUP BY them, etc. I’ve repeated that criticism myself. The lack of composability is annoying. But semantically, Snodgrass was right: valid-time is not an attribute, but a qualifier of the other attributes.

To be fair to the critics, they don’t treat valid-times like regular attributes either. Since Date/Darwen/Lorentzos define temporal operators in terms of PACK and UNPACK, their inputs’ valid-times “disappear”, and the original values aren’t carried through to the result.

It has been a big help to me to think that you can replace any valid-time tuple with a bunch of ordinary tuples, one for each moment in the valid-time, and that is how temporal features should behave. So valid-time really is something “magic” and different. I still don’t love how PERIODs are not values in SQL, but somehow we do need to treat valid-time differently.

I’m very interested in seeing some proofs of temporal algebraic identities. Snodgrass cites a paper he wrote with E. McKenzie, “Supporting valid time in an historical relational algebra: Proofs and extensions.” But I haven’t been able to find a copy. It is “Technical Report TR-91-15, Department of Computer Science, University of Arizona, Tucson, AZ, August 1991.” That sounds like it might not have been widely distributed. Some other citations which I now have, but haven’t yet read, are Jeffrey D. Ullman, Database and Knowledge-Base Systems Vol I & II and David Maier, The Theory of Relational Databases.

It looks like the 80s and 90s were really a golden age for temporal research. There are a lot of different temporal models and algebraic systems. Already in 1990, this paper by Alexander Tuzhilin and James Clifford was complaining about how to compare them, and they give proofs to show that one is at least as powerful as another. But I’m doing my best to come to grips with what is out there.

Thanks to Jeff Davis, Noah Misch, Boris Novikov, and Kent Bulza for helpful conversations!

blog comments powered by Disqus Next: My Claude Code Setup