Re: SQL competition: the shortest interval coalesce/pack query
Date: Sat, 04 Dec 2004 08:12:10 GMT
Message-ID: <ujesd.60193$Vk6.30697_at_twister.nyc.rr.com>
"Lennart Jonsson" <lennart_at_kommunicera.umea.se> wrote in message
news:6dae7e65.0412031821.4df452c6_at_posting.google.com...
> lennart_at_kommunicera.umea.se (Lennart Jonsson) wrote in message
news:<6dae7e65.0412031228.3051dff_at_posting.google.com>...
> > "Mikito Harakiri" <mikharakiri_at_iahu.com> wrote in message
news:<2uPrd.61$G45.36_at_news.oracle.com>...
>
> [...]
> >
> > I have not looked at the article, so I'm not sure this is any shorter but:
> >
> > with cover(x,y,n) as (
> > select x, y, 1 from intervals
> > union all
> > select c.x, i.y, n+1 from cover c, intervals i
> > where c.y > i.x
> > and (n+1) < (select count(1) from intervals)
> > )
> > select x, max(y) from cover c
> > where not exists (
> > select 1 from cover where y=c.y and x < c.x
> > ) group by x
> >
>
> Hmmm, on second thought. This explodes with just a few more intervals.
> I will have to come up with something slightly smarter.
>
>
> /Lennart
Lennart, as you've noted, your query does exhibit problems. For example,
starting with the sample interval set, if you remove (20,21) so that you no
longer have a gap, that is,
INSERT INTO Intervals (x,y)
VALUES (1,3),(2,5),(4,11),(10,12);
then the query returns
1 11
2 12
Also, if we add an interval to the interval set that's contiguous with say
(20,21), e.g.,
INSERT INTO Intervals (x,y)
VALUES (1,3),(2,5),(4,11),(10,12),(20,21),(21,25);
then the query returns
1 12
20 21
21 25
However, using recursion is an interesting take on this so here's an offering:
CREATE TABLE Intervals
(
x INT NOT NULL,
y INT NOT NULL,
CHECK (y > x),
PRIMARY KEY (x,y)
);
WITH Cover (x,y,n)
AS (SELECT x,y,
(SELECT COUNT(*) FROM Intervals) FROM Intervals UNION ALL SELECT CASE WHEN C.x <= I.x THEN C.x ELSE I.x END, CASE WHEN C.y >= I.y THEN C.y ELSE I.y END, C.n - 1 FROM Intervals AS I, Cover AS C WHERE I.x <= C.y AND I.y >= C.x AND (I.x <> C.x OR I.y <> C.y) AND C.n > 1)
SELECT DISTINCT C1.x, C1.y
FROM Cover AS C1
WHERE NOT EXISTS (SELECT *
FROM Cover AS C2 WHERE C2.x <= C1.x AND C2.y >= C1.y AND (C1.x <> C2.x OR C1.y <> C2.y))ORDER BY C1.x;
-- JAGReceived on Sat Dec 04 2004 - 09:12:10 CET