Thread: checking the gaps in intervals

checking the gaps in intervals

From
Anton Gavazuk
Date:
Hi dear community,

Have probably quite simple task but cannot find the solution,

Imagine the table A with 2 columns start and end, data type is date

start          end
01 dec.     10 dec
11 dec.     13 dec
17 dec.     19 dec
.....

If I have interval, for example, 12 dec-18 dec, how can I determine
that the interval cannot be fully covered by values from table A
because of the gap 14-16 dec? Looking for solution and unfortunately
nothing has come to the mind yet...

Thanks,
Anton

Re: checking the gaps in intervals

From
Andreas Kretschmer
Date:
Anton Gavazuk <antongavazuk@gmail.com> wrote:

> Hi dear community,
> 
> Have probably quite simple task but cannot find the solution,
> 
> Imagine the table A with 2 columns start and end, data type is date
> 
> start          end
> 01 dec.     10 dec
> 11 dec.     13 dec
> 17 dec.     19 dec
> .....
> 
> If I have interval, for example, 12 dec-18 dec, how can I determine
> that the interval cannot be fully covered by values from table A
> because of the gap 14-16 dec? Looking for solution and unfortunately
> nothing has come to the mind yet...

I'm thinking about a solution with DATERANGE (PostgreSQL 9.2)...


Are start and end including or excluding?


Andreas
-- 
Really, I'm not out to destroy Microsoft. That will just be a completely
unintentional side effect.                              (Linus Torvalds)
"If I was god, I would recompile penguin with --enable-fly."   (unknown)
Kaufbach, Saxony, Germany, Europe.              N 51.05082°, E 13.56889°



Re: checking the gaps in intervals

From
Andreas Kretschmer
Date:
Andreas Kretschmer <akretschmer@spamfence.net> wrote:

> Anton Gavazuk <antongavazuk@gmail.com> wrote:
> 
> > Hi dear community,
> > 
> > Have probably quite simple task but cannot find the solution,
> > 
> > Imagine the table A with 2 columns start and end, data type is date
> > 
> > start          end
> > 01 dec.     10 dec
> > 11 dec.     13 dec
> > 17 dec.     19 dec
> > .....
> > 
> > If I have interval, for example, 12 dec-18 dec, how can I determine
> > that the interval cannot be fully covered by values from table A
> > because of the gap 14-16 dec? Looking for solution and unfortunately
> > nothing has come to the mind yet...
> 
> I'm thinking about a solution with DATERANGE (PostgreSQL 9.2)...
> 
> 
> Are start and end including or excluding?

Okay, my solution, quick and dirty ;-)

-- that's your table:

test=*# select * from ag;date_start |  date_end  
------------+------------2012-12-01 | 2012-12-10 2012-12-11 | 2012-12-13 2012-12-17 | 2012-12-19 
(3 rows)                 



-- now some views:
test=*# \d+ view_ag;                  View "public.view_ag" Column  |   Type    | Modifiers | Storage  | Description 
----------+-----------+-----------+----------+-------------my_range | daterange |           | extended |             
View definition:                                           SELECT daterange(ag.date_start, ag.date_end, '[]'::text) AS
my_range FROM ag;
 

test=*# \d+ view_ag2;                 View "public.view_ag2" Column  |   Type    | Modifiers | Storage  | Description
----------+-----------+-----------+----------+-------------my_range | daterange |           | extended |my_lag   |
daterange|           | extended |
 
View definition:SELECT view_ag.my_range,   lag(view_ag.my_range) OVER (ORDER BY lower(view_ag.my_range)) AS my_lag
FROMview_ag;
 

test=*# \d+ view_ag3;                  View "public.view_ag3" Column   |   Type    | Modifiers | Storage  |
Description
-----------+-----------+-----------+----------+-------------my_range  | daterange |           | extended |my_lag    |
daterange|           | extended |?column?  | boolean   |           | plain    |new_range | daterange |           |
extended|
 
View definition:SELECT view_ag2.my_range, view_ag2.my_lag,   view_ag2.my_lag -|- view_ag2.my_range,       CASE
WHEN view_ag2.my_lag -|- view_ag2.my_range THEN view_ag2.my_lag + view_ag2.my_range           ELSE view_ag2.my_range
  END AS new_range  FROM view_ag2;
 

-- and now my select:
-- first case, the range is not included
test=*# select count(*) from view_ag3 where new_range @> '[2012-12-12,2012-12-18]';count
-------    0
(1 row)

-- and now, the range is included
test=*# select count(*) from view_ag3 where new_range @> '[2012-12-02,2012-12-13]';count
-------    1
(1 row)


Hope that helps, but you need the 9.2.



Andreas
-- 
Really, I'm not out to destroy Microsoft. That will just be a completely
unintentional side effect.                              (Linus Torvalds)
"If I was god, I would recompile penguin with --enable-fly."   (unknown)
Kaufbach, Saxony, Germany, Europe.              N 51.05082°, E 13.56889°



Re: checking the gaps in intervals

From
Gavin Flower
Date:
<div class="moz-cite-prefix">On 06/10/12 11:42, Anton Gavazuk wrote:<br /></div><blockquote
cite="mid:-3205649711969780110@unknownmsgid"type="cite"><pre wrap="">Hi dear community,
 

Have probably quite simple task but cannot find the solution,

Imagine the table A with 2 columns start and end, data type is date

start          end
01 dec.     10 dec
11 dec.     13 dec
17 dec.     19 dec
.....

If I have interval, for example, 12 dec-18 dec, how can I determine
that the interval cannot be fully covered by values from table A
because of the gap 14-16 dec? Looking for solution and unfortunately
nothing has come to the mind yet...

Thanks,
Anton


</pre></blockquote><font face="Courier New, Courier, monospace">How about something like the following?<br /><br />
Cheers,<br/> Gavin</font><br /><font face="Courier New, Courier, monospace"><br /> DROP TABLE IF EXISTS period;<br
/><br/> CREATE TABLE period<br /> (<br />     id          serial PRIMARY KEY,<br />     start_date  date,<br />    
end_date   date<br /> );<br /><br /><br /> INSERT INTO period (start_date, end_date) VALUES<br /> ('2012-12-01',
'2012-12-10'),<br/> ('2012-12-11', '2012-12-13'),<br /> ('2012-12-17', '2012-12-19'),<br /> ('2012-12-20',
'2012-12-25');<br/><br /><br /> WITH RECURSIVE <br />     slot (start_date, end_date) AS<br />     (<br />            
SELECT<br />                 p1.start_date, <br />                 p1.end_date<br />             FROM<br />
               period p1<br />             WHERE<br />                 NOT EXISTS<br />                 (<br />
                   SELECT<br />                         1<br />                     FROM<br />                        
periodp2<br />                     WHERE<br />                         p1.start_date = p2.end_date + 1<br />
               )<br />         UNION ALL<br />             SELECT <br />                 s1.start_date, <br />
               p3.end_date<br />             FROM<br />                 slot s1,<br />                 period p3<br />
           WHERE<br />                     p3.start_date = s1.end_date + 1<br />                 AND p3.end_date >
s1.end_date<br/>     )<br /><br /> SELECT<br />     s3.start_date, <br />     MIN(s3.end_date)<br /> FROM<br />    
slots3<br /> WHERE<br />         s3.start_date <= '2012-12-01'<br />     AND s3.end_date >= '2012-12-18'<br />
GROUPBY<br />     s3.start_date<br /> /**/;/**/</font><font face="Courier New, Courier, monospace">.</font><br /><br /> 

Re: checking the gaps in intervals

From
Gavin Flower
Date:
<div class="moz-cite-prefix">On 06/10/12 11:42, Anton Gavazuk wrote:<br /></div><blockquote
cite="mid:-3205649711969780110@unknownmsgid"type="cite"><pre wrap="">Hi dear community,
 

Have probably quite simple task but cannot find the solution,

Imagine the table A with 2 columns start and end, data type is date

start          end
01 dec.     10 dec
11 dec.     13 dec
17 dec.     19 dec
.....

If I have interval, for example, 12 dec-18 dec, how can I determine
that the interval cannot be fully covered by values from table A
because of the gap 14-16 dec? Looking for solution and unfortunately
nothing has come to the mind yet...

Thanks,
Anton


</pre></blockquote> If the periods _NEVER_ overlap, you can also use this this approach<br /> (N.B. The indexing of the
periodtable here, can be used in my previous solution where I had not considered the indexing seriously!)<br /><br />
Cheers,<br/> Gavin<br /><br /><small><small><font face="monospace">DROP TABLE IF EXISTS period;<br /> DROP TABLE IF
EXISTStarget;<br /><br /> CREATE TABLE period<br /> (<br />     start_date  date,<br />     end_date    date,<br />    
<br/>     PRIMARY KEY (start_date, end_date)<br /> );<br /><br /> CREATE INDEX ON period (end_date);<br /><br /><br />
INSERTINTO period (start_date, end_date) VALUES<br /> ('2012-11-21', '2012-11-29'),<br /> ('2012-12-01',
'2012-12-10'),<br/> ('2012-12-11', '2012-12-13'),<br /> ('2012-12-17', '2012-12-19'),<br /> ('2012-12-20',
'2012-12-25');<br/><br /> TABLE period;<br /><br /><br /> CREATE TABLE target<br /> (<br />     start_date  date,<br />
   end_date    date<br /> );<br /><br /><br /> INSERT INTO target (start_date, end_date) VALUES<br /> ('2012-12-01',
'2012-12-01'),<br/> ('2012-12-02', '2012-12-02'),<br /> ('2012-12-09', '2012-12-09'),<br /> ('2012-12-10',
'2012-12-10'),<br/> ('2012-12-01', '2012-12-09'),<br /> ('2012-12-01', '2012-12-10'),<br /> ('2012-12-01',
'2012-12-12'),<br/> ('2012-12-01', '2012-12-13'),<br /> ('2012-12-02', '2012-12-09'),<br /> ('2012-12-02',
'2012-12-12'),<br/> ('2012-12-03', '2012-12-11'),<br /> ('2012-12-02', '2012-12-13'),<br /> ('2012-12-02',
'2012-12-15'),<br/> ('2012-12-01', '2012-12-18');<br /><br /> SELECT<br />     t.start_date,<br />     t.end_date<br />
FROM<br/>     target t<br /> ORDER BY<br />     t.start_date,<br />     t.end_date    <br /> /**/;/**/<br /><br /><br
/>SELECT<br />     t1.start_date AS "Target Start",<br />     t1.end_date AS "Target End",<br />     (t1.end_date -
t1.start_date)+ 1 AS "Duration",<br />     p1.start_date AS "Period Start",<br />     p1.end_date AS "Period End"<br />
FROM<br/>     target t1,<br />     period p1<br /> WHERE<br />     (<br />         SELECT<br />             SUM<br />
           (<br />                 CASE <br />                     WHEN p2.end_date > t1.end_date <br />
                       THEN p2.end_date - (p2.end_date - t1.end_date)<br />                         ELSE p2.end_date<br
/>                END<br />                 -<br />                 CASE <br />                     WHEN p2.start_date
<t1.start_date<br />                         THEN p2.start_date + (t1.start_date - p2.start_date)<br />
                       ELSE p2.start_date<br />                 END <br />                 + 1<br />             ) <br
/>        FROM<br />             period p2<br />         WHERE<br />                 p2.start_date <= t1.end_date<br
/>            AND p2.end_date >= t1.start_date<br />     ) = (t1.end_date - t1.start_date) + 1<br />     AND
p1.start_date<= t1.end_date<br />     AND p1.end_date >= t1.start_date<br /> ORDER BY<br />     t1.start_date,<br
/>    t1.end_date,<br />     p1<small><small><font
face="monospace">.start_date</font></small></small></font></small></small><br/><small><small><font
face="monospace">/**/;/**/<br/></font></small></small><br /> 

Re: checking the gaps in intervals

From
Jasen Betts
Date:
On 2012-10-05, Anton Gavazuk <antongavazuk@gmail.com> wrote:
> Hi dear community,
>
> Have probably quite simple task but cannot find the solution,
>
> Imagine the table A with 2 columns start and end, data type is date
>
> start          end
> 01 dec.     10 dec
> 11 dec.     13 dec
> 17 dec.     19 dec
> .....
>
> If I have interval, for example, 12 dec-18 dec, how can I determine
> that the interval cannot be fully covered by values from table A
> because of the gap 14-16 dec? Looking for solution and unfortunately
> nothing has come to the mind yet...

perhaps you can do a with-recursive query ?

create temp table Gavazuk      (id serial primary key, start date ,fin date);
insert into Gavazuk (start,fin) 
values ('2012-12-01','2012-12-10')     ,('2012-12-11','2012-12-13')     ,('2012-12-17','2012-12-19');

-- this version treats ('2012-12-01','2012-12-10') ('2012-12-11','2012-12-13')
-- as contiguous   

with recursive a as (  select max (fin) as f from Gavazuk    where ('2012-12-12') between start and fin union all
selectdistinct (fin) from gavazuk,a   where a.f+1 between start and fin and start <= '2012-12-12'
 
)
select max(f) >= '2012-12-18' from a;

-- this version treats ('2012-12-01','2012-12-10') ('2012-12-11','2012-12-13')
-- as non-contiguous   

with recursive a as (  select max (fin) as f from Gavazuk    where ('2012-12-12') between start and fin union all
selectdistinct (fin) from gavazuk,a   where a.f between start and fin-1 and start <= '2012-12-12'
 
)
select max(f) >= '2012-12-18' from a;


-- 
⚂⚃ 100% natural




Re: checking the gaps in intervals

From
Gavin Flower
Date:
On 07/10/12 14:30, Jasen Betts wrote:
> On 2012-10-05, Anton Gavazuk <antongavazuk@gmail.com> wrote:
>> Hi dear community,
>>
>> Have probably quite simple task but cannot find the solution,
>>
>> Imagine the table A with 2 columns start and end, data type is date
>>
>> start          end
>> 01 dec.     10 dec
>> 11 dec.     13 dec
>> 17 dec.     19 dec
>> .....
>>
>> If I have interval, for example, 12 dec-18 dec, how can I determine
>> that the interval cannot be fully covered by values from table A
>> because of the gap 14-16 dec? Looking for solution and unfortunately
>> nothing has come to the mind yet...
> perhaps you can do a with-recursive query ?
>
> create temp table Gavazuk
>        (id serial primary key, start date ,fin date);
> insert into Gavazuk (start,fin)
> values ('2012-12-01','2012-12-10')
>        ,('2012-12-11','2012-12-13')
>        ,('2012-12-17','2012-12-19');
>
> -- this version treats ('2012-12-01','2012-12-10') ('2012-12-11','2012-12-13')
> -- as contiguous
>
> with recursive a as (
>     select max (fin) as f from Gavazuk
>     where ('2012-12-12') between start and fin
>    union all
>     select distinct (fin) from gavazuk,a
>     where a.f+1 between start and fin and start <= '2012-12-12'
> )
> select max(f) >= '2012-12-18' from a;
>
> -- this version treats ('2012-12-01','2012-12-10') ('2012-12-11','2012-12-13')
> -- as non-contiguous
>
> with recursive a as (
>     select max (fin) as f from Gavazuk
>     where ('2012-12-12') between start and fin
>    union all
>     select distinct (fin) from gavazuk,a
>     where a.f between start and fin-1 and start <= '2012-12-12'
> )
> select max(f) >= '2012-12-18' from a;
>
>
Cunning, also much more elegant and concise than my solutions!

Cheers,
Gavin