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

From: John Gilson <jag_at_acm.org>
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;
--
JAG
Received on Sat Dec 04 2004 - 09:12:10 CET

Original text of this message