Re: SQL competition: the shortest interval coalesce/pack query
Date: Mon, 06 Dec 2004 18:08:19 -0500
Message-ID: <3c5f82-ldi.ln1_at_pluto.downsfam.net>
Mikito Harakiri wrote:
> Write the shortest sql query that would return a minimal cover of a set of
> intervals. For example, given
>
> Intervals = {(x=1,y=3), (x=2,y=5), (x=4, y=11), (x=10,y=12), (x=20,y=21)}
>
> it should return
>
> cover(Intervals) = {(x=1,y=12), (x=20,y=21)}
>
> "Developing Time-Oriented..." book by R.Snordgrass demonstrates several
> rather lenthy solutions (pp.160+). The book is freely downloadable.
>
> To be able to compare results, lets agree that each of the clauses
> (select, from, where, group by, having) starts a new line. (Each
> subquery/inner view must obey this rule as well.) Also, no more than 2
> column expressions are allowed to fit on a single line in the select
> clause. Likewise, no more than 2 view/tables are allowed on a single line
> within from clause, no more than 2 predicates in the each line of the
> where clause, etc. If anybody knows alternative (maybe even standard) sql
> formatting rules, you are welcome to suggest those.
Just for the fun of it, I asked myself what would the query be if we had an interval type, and if I stuck with the overloading of = to mean overlapping.
Since interval or range types are not supported in commercial products, I had to take some liberties in making up some DDL syntax, which might look like this:
CREATE TABLE Intervals (i interval) -- made up type: interval
or maybe:
CREATE TABLE Intervals (i interval:int)
insert into intervals (i)
({1,3} ), ({2,5} ), ({4,11} ), ({10,12}), ({20,21})
If the GROUP BY went in order (a whalloping big if), the query would be:
SELECT MIN(i[0]),MAX(i[1])
FROM intervals
GROUP BY i
In the old procedural days we would say that we "break" on non-overlapping values and write a record to output.
I wish I could spend more time on this as it looks interesting, but the past couple of weeks have been spent paying bill$.
-- Kenneth Downs <?php $sig_block="Variable scope? What's that?";?>Received on Tue Dec 07 2004 - 00:08:19 CET