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

Date: 4 Dec 2004 07:42:15 -0800

Message-ID: <6dae7e65.0412040742.572da937_at_posting.google.com>

"John Gilson" <jag_at_acm.org> wrote in message news:<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>...
**> >
**> > [...]
**> > >
*

[...]

*>
*

> 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;
*

Hi John. Very interesting and I will have a look at it later.

In fact I hadnt started worrying about the correctness of my attempt, but merely the performance. Because of the nature of the problem the cover set grows very fast. I took the liberty to take you code for a run

select * from intervals

X Y

----------- -----------

1 3 2 5 4 11 10 12 20 21 4 16 5 17 6 18

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 count(C1.x)

FROM Cover AS C1;

1

SQL0347W The recursive common table expression "LELLE.COVER" may contain an

infinite loop. SQLSTATE=01605

2379720

But your query terminates very quickly so perhaps the optimizer is smart enough to push the predicates inside the cover clause?

/Lennart Received on Sat Dec 04 2004 - 16:42:15 CET