Re: SQL competition: the shortest interval coalesce/pack query

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?";?>