[TransWarp] Towards a query theory, part 1: filters and correlation

[Phillip J. Eby]

At 02:20 PM 10/14/03 +0300, Niki Spahiev wrote:
>IIRC SQLObjects has many similar ideas implemented.

Thanks, but as far as I can tell from its documentation, it does not 
support correlation, aggregation, or grouping.  It only implements what I 
consider "the easy part": pure filtering based on traversal expressions 
from a single start set.  Such "easy" queries can be executed now on Python 
objects, using the functions in peak.model.queries, although SQL generation 
is not yet supported.

Generating SQL from "easy" queries involves a lot of details, but is 
straightforward, on the whole.  Mostly it's a process of walking the query 
to extract table aliases, joins, and criteria.

Here are PEAK's "hard" query requirements:

* Support correlations (e.g. the "find employees that lives in the same 
city as their supervisor, but was born in a different country" example)

* Support aggregation (count/min/max/avg) over groups (GROUP BY in SQL)

* Support cross-database joins, where an object's data resides in more than 
one system, or where some of an object's features are the result of 
computation in Python over data retrieved from an external source.

Really, these correspond pretty directly to the promised features of the 
fabled Gadfly 2.  Alas, Gadfly 2 has been vaporware for almost four years 
now.  :(  Worse, although Aaron Watters' paper for IPC 8 lays out some key 
algorithms, others are missing, e.g.:

"""Also note that the treatment of logical OR and NOT as well as EXIST, IN, 
UNION and aggregation and so forth are not discussed here, even though they 
do fit into this approach."""

And that's largely a description of the "hard" areas!  Anyway, I've been 
beating my head up against the theory for long enough now that I'm going to 
have to bite the bullet and try reading up on Aaron's references again.  So 
far, I've painstakingly figured out how to implement a variety of things by 
reinventing the theory, but I think I'd better read some real theory in 
order to verify my ideas so far.