Peter Larsson Blog

Patron Saint of Lost Yaks

Unified Relational Division algorithm


Today I finished my presentation about finding a unified algorithm for Relational Division, which should work for all types of division; singlerecord and multirecord, singlecolumn and multicolumn and both exact division and with remainder.
Optionally it should work with single and multiple divisor sets. That's 16 permutations of relational division kinds.

A bonus point is that the algorithm I've found work across multiple platforms with standard SQL language elements.
Also, I have performance tested the algorithm with the sample data from Mr Celko here.

For such small sample set, my algorithm is in the top queries, but the real performance kicks in when you use it against a real life dataset. I tested it on a PilotSkills table with 2 million records and used a Hangar table with 2 million records.
The fastest query I've found was a query from Mr Celko, but I had to kill it after 5 hours. To compare, my query ran in 24 seconds.

I think there is a great improvement to have one unified algorithm for all kinds of division because then it perhaps can be implemented by Microsoft as a T-SQL operator, just as MERGE is.

I will post the algorithm after SQLBits, because I have submitted this to them, the presentation is about finding this algorithm.


Legacy Comments

Alejandro Mesa
re: Unified Relational Division algorithm
That is really great, Peter. Let us know when you have filed the connect entry.

Looking forward to learn about this unified RD algorithm.


Ryan S.
re: Unified Relational Division algorithm
Ugh, relational division algorithms were the ones that I hated learning about during my college IT days. For some reason I couldn't get them to work out right. The fact that you discovered a unified algorithm is great news! Thankfully I won't need it because I am out of that line of work. These days I spend my efforts working with an Indianapolis Jiu Jitsu website so I focus more on HTML 5, Flash, and CSS.