Tìm tất cả các giao lộ của tất cả các dải ô trong PostgreSQL

Question

Tôi đang tìm một cách hiệu quả để tìm tất cả các giao lộ giữa các tập hợp các dấu thời gian. Nó cần phải làm việc với PostgreSQL 9.2.

Giả sử phạm vi biểu thị thời gian khi một người có mặt để đáp ứng. Mỗi người có thể có một hoặc nhiều khoảng thời gian khi họ có mặt. Tôi muốn tìm tất cả khoảng thời gian khi cuộc họp có thể diễn ra (nghĩa là trong thời gian đó tất cả mọi người đều có mặt).

Đây là những gì tôi đã có cho đến nay. Dường như nó hoạt động, nhưng tôi không nghĩ nó rất hiệu quả, vì nó xem xét tính khả dụng của một người tại một thời điểm.

WITH RECURSIVE td AS 
(
    -- Test data. Returns: 
    -- ["2014-01-20 00:00:00","2014-01-31 00:00:00") 
    -- ["2014-02-01 00:00:00","2014-02-20 00:00:00") 
    -- ["2014-04-15 00:00:00","2014-04-20 00:00:00") 
    SELECT 1 AS entity_id, '2014-01-01'::timestamp AS begin_time, '2014-01-31'::timestamp AS end_time 
    UNION SELECT 1, '2014-02-01', '2014-02-28' 
    UNION SELECT 1, '2014-04-01', '2014-04-30' 
    UNION SELECT 2, '2014-01-15', '2014-02-20' 
    UNION SELECT 2, '2014-04-15', '2014-05-05' 
    UNION SELECT 3, '2014-01-20', '2014-04-20' 
) 
, ranges AS 
(
    -- Convert to tsrange type 
    SELECT entity_id, tsrange(begin_time, end_time) AS the_range 
    FROM td 
) 
, min_max AS 
(
    SELECT MIN(entity_id), MAX(entity_id) 
    FROM td 
) 
, inter AS 
(
    -- Ranges for the lowest ID 
    SELECT entity_id AS last_id, the_range 
    FROM ranges r 
    WHERE r.entity_id = (SELECT min FROM min_max) 

    UNION ALL 

    -- Iteratively intersect with ranges for the next higher ID 
    SELECT entity_id, r.the_range * i.the_range 
    FROM ranges r 
    JOIN inter i ON r.the_range && i.the_range 
    WHERE r.entity_id > i.last_id 
     AND NOT EXISTS 
     (
      SELECT * 
      FROM ranges r2 
      WHERE r2.entity_id < r.entity_id AND r2.entity_id > i.last_id 
     ) 
) 
-- Take the final set of intersections 
SELECT * 
FROM inter 
WHERE last_id = (SELECT max FROM min_max) 
ORDER BY the_range; 

Answer 1

tôi tạo ra các tsrange_interception_agg tổng

create function tsrange_interception (
    internal_state tsrange, next_data_values tsrange 
) returns tsrange as $$ 
    select internal_state * next_data_values; 
$$ language sql; 

create aggregate tsrange_interception_agg (tsrange) (
    sfunc = tsrange_interception, 
    stype = tsrange, 
    initcond = $$[-infinity, infinity]$$ 
); 

Sau đó truy vấn này

with td (id, begin_time, end_time) as 
(
    values 
    (1, '2014-01-01'::timestamp, '2014-01-31'::timestamp), 
    (1, '2014-02-01', '2014-02-28'), 
    (1, '2014-04-01', '2014-04-30'), 
    (2, '2014-01-15', '2014-02-20'), 
    (2, '2014-04-15', '2014-05-05'), 
    (3, '2014-01-20', '2014-04-20') 
), ranges as (
    select 
     id, 
     row_number() over(partition by id) as rn, 
     tsrange(begin_time, end_time) as tr 
    from td 
), cr as (
    select r0.tr tr0, r1.tr as tr1 
    from ranges r0 cross join ranges r1 
    where 
     r0.id < r1.id and 
     r0.tr && r1.tr and 
     r0.id = (select min(id) from td) 
) 
select tr0 * tsrange_interception_agg(tr1) as interseptions 
from cr 
group by tr0 
having count(*) = (select count(distinct id) from td) - 1 
; 
       interseptions     
----------------------------------------------- 
["2014-02-01 00:00:00","2014-02-20 00:00:00") 
["2014-01-20 00:00:00","2014-01-31 00:00:00") 
["2014-04-15 00:00:00","2014-04-20 00:00:00") 

Answer 2

OK, tôi đã viết và thử nghiệm điều này trong TSQL nhưng nó phải chạy hoặc ít nhất là đủ gần để bạn dịch ngược lại, tất cả đều là cấu trúc khá vani. Ngoại trừ có thể giữa, nhưng điều đó có thể được chia thành một mệnh đề < và a> mệnh đề. (nhờ @Horse)

WITH cteSched AS (--Schedule for everyone 
    -- Test data. Returns: 
    -- ["2014-01-20 00:00:00","2014-01-31 00:00:00") 
    -- ["2014-02-01 00:00:00","2014-02-20 00:00:00") 
    -- ["2014-04-15 00:00:00","2014-04-20 00:00:00") 
    SELECT 1 AS entity_id, '2014-01-01' AS begin_time, '2014-01-31' AS end_time 
    UNION SELECT 1, '2014-02-01', '2014-02-28' 
    UNION SELECT 1, '2014-04-01', '2014-04-30' 
    UNION SELECT 2, '2014-01-15', '2014-02-20' 
    UNION SELECT 2, '2014-04-15', '2014-05-05' 
    UNION SELECT 3, '2014-01-20', '2014-04-20' 
), cteReq as ( --List of people to schedule (or is everyone in Sched required? Not clear, doesn't hurt) 
    SELECT 1 as entity_id UNION SELECT 2 UNION SELECT 3 
), cteBegins as (
    SELECT distinct begin_time FROM cteSched as T 
    WHERE NOT EXISTS (SELECT entity_id FROM cteReq as R 
         WHERE NOT EXISTS (SELECT * FROM cteSched as X 
             WHERE X.entity_id = R.entity_id 
              AND T.begin_time BETWEEN X.begin_time AND X.end_time)) 
) SELECT B.begin_time, MIN(S.end_time) as end_time 
    FROM cteBegins as B cross join cteSched as S 
    WHERE B.begin_time between S.begin_time and S.end_time 
    GROUP BY B.begin_time 
-- NOTE: This assume users do not have schedules that overlap with themselves! That is, nothing like 
-- John is available 2014-01-01 to 2014-01-15 and 2014-01-10 to 2014-01-20. 

EDIT: Thêm đầu ra từ trên cao (khi thực thi trên SQL-Server 2008R2)
BEGIN_TIME END_TIME
2014-01-20 2014-01-31
2014-02- 01 2014-02-20
2014-04-15 2014-04-20

Answer 3

Nếu bạn có số lượng thực thể cố định mà bạn muốn tham chiếu chéo, bạn có thể sử dụng tham gia chéo cho mỗi người trong số họ và xây dựng giao lộ (sử dụng toán tử * trên phạm vi).

Sử dụng tham gia chéo như thế này có thể kém hiệu quả hơn. Ví dụ sau có nhiều việc phải làm với việc giải thích ví dụ phức tạp hơn bên dưới.

WITH td AS 
(
    SELECT 1 AS entity_id, '2014-01-01'::timestamp AS begin_time, '2014-01-31'::timestamp AS end_time 
    UNION SELECT 1, '2014-02-01', '2014-02-28' 
    UNION SELECT 1, '2014-04-01', '2014-04-30' 
    UNION SELECT 2, '2014-01-15', '2014-02-20' 
    UNION SELECT 2, '2014-04-15', '2014-05-05' 
    UNION SELECT 4, '2014-01-20', '2014-04-20' 
) 
,ranges AS 
(
    -- Convert to tsrange type 
    SELECT entity_id, tsrange(begin_time, end_time) AS the_range 
    FROM td 
) 
SELECT r1.the_range * r2.the_range * r3.the_range AS r 
FROM ranges r1 
CROSS JOIN ranges r2 
CROSS JOIN ranges r3 
WHERE r1.entity_id=1 AND r2.entity_id=2 AND r3.entity_id=4 
    AND NOT isempty(r1.the_range * r2.the_range * r3.the_range) 
ORDER BY r 

Trong trường hợp này một bội chéo tham gia có lẽ là kém hiệu quả vì bạn không thực sự cần phải có tất cả các kết hợp có thể có của mỗi phạm vi trong thực tế, kể từ khi isempty(r1.the_range * r2.the_range) là đủ để làm cho isempty(r1.the_range * r2.the_range * r3.the_range) đúng.

Tôi không nghĩ rằng bạn có thể tránh đi qua sự sẵn có của mỗi người vào thời điểm đó, vì bạn muốn tất cả họ đều được gặp nhau.

Điều gì có thể giúp xây dựng bộ giao lộ tăng dần, bằng cách kết hợp tính khả dụng của từng người với tập hợp con trước đó bạn đã tính toán bằng CTE đệ quy khác (intersections trong ví dụ bên dưới). Sau đó, bạn xây dựng các nút giao nhau theo từng bước và loại bỏ các dải trống, cả hai mảng được lưu trữ:

WITH RECURSIVE td AS 
(
    SELECT 1 AS entity_id, '2014-01-01'::timestamp AS begin_time, '2014-01-31'::timestamp AS end_time 
    UNION SELECT 1, '2014-02-01', '2014-02-28' 
    UNION SELECT 1, '2014-04-01', '2014-04-30' 
    UNION SELECT 2, '2014-01-15', '2014-02-20' 
    UNION SELECT 2, '2014-04-15', '2014-05-05' 
    UNION SELECT 4, '2014-01-20', '2014-04-20' 
) 
,ranges AS 
(
    -- Convert to tsrange type 
    SELECT entity_id, tsrange(begin_time, end_time) AS the_range 
    FROM td 
) 
,ranges_arrays AS (
    -- Prepare an array of all possible intervals per entity 
    SELECT entity_id, array_agg(the_range) AS ranges_arr 
    FROM ranges 
     GROUP BY entity_id 
) 
,numbered_ranges_arrays AS (
    -- We'll join using pos+1 next, so we want continuous integers 
    -- I've changed the example entity_id from 3 to 4 to demonstrate this. 
    SELECT ROW_NUMBER() OVER() AS pos, entity_id, ranges_arr 
    FROM ranges_arrays 
) 
,intersections (pos, subranges) AS (
    -- We start off with the infinite range. 
    SELECT 0::bigint, ARRAY['[,)'::tsrange] 
    UNION ALL 
    -- Then, we unnest the previous intermediate result, 
    -- cross join it against the array of ranges from the 
    -- next row in numbered_ranges_arrays (joined via pos+1). 
    -- We take the intersection and remove the empty array. 
    SELECT r.pos, 
      ARRAY(SELECT x * y FROM unnest(r.ranges_arr) x CROSS JOIN unnest(i.subranges) y WHERE NOT isempty(x * y)) 
    FROM numbered_ranges_arrays r 
     INNER JOIN intersections i ON r.pos=i.pos+1 
) 
,last_intersections AS (
    -- We just really want the result from the last operation (with the max pos). 
    SELECT subranges FROM intersections ORDER BY pos DESC LIMIT 1 
) 
SELECT unnest(subranges) r FROM last_intersections ORDER BY r 

Tôi không chắc liệu điều này có khả năng hoạt động tốt hơn hay không. Bạn có thể cần một tập dữ liệu lớn hơn để có điểm chuẩn có ý nghĩa.