SQL query challenge

Basically, you can not do it (find a covering partition set of a forest) in pure set theory (e.g. as a bounded # of queries without a loop).

To do it in the most set-like way,

1. Create a temp table for forest partitioning (10 or 11 columns, 4 from failure #1, 4 from failure #2, 1 for partition ID, 1 for round in which node was inserted, and 1 for assorted optimizations I can't think of with a fever of 38C.

2. Run a loop (BFS or DFS, whatever you find to easier implement the forest partitioning algorithm in). The tricky part, compared to graphs, is that you can have many sub-trees joined from the top to current sub-tree

   You can use sheepsimulator's query as basic building block for the loop (e.g. finding 2 connected node)

3. When the partitioning loop is done, simply do

   select min(p1.start_time), max(p2.end_time), p1.partition,p2.partition
   from partitions p1, partitions p2
   where p1.partition = p2.partition
   group by p1.partition,p2.partition
   

    /* This will need to be tweaked using COALESCE 
       to deal with NULL end times in obvious way) */

I apologize for not spelling the exact code for forest partitioning (it may be filed under tree partitioning) - I'm dead tired and I'm certain some Googling will yield one now that you know the tdata structure and problem name (or you can post this as a more precisely formulated Q on StackOverflow - e.g. "How to implement an algorithm for complete partitioning of a forest of trees as a loop in SQL".

SELECT  DISTINCT 
        t1.machineId, 
        MIN(t2.start_time) start_time, 
        MAX(COALESCE(t2.end_time, '3210/01/01')) end_time
FROM FAULTS t1
JOIN FAULTS t2 ON t1.machineId = t2.machineId
                  AND ((t2.start_time >= t1.start_time
                       AND (t1.end_time IS NULL OR t2.start_time <= t1.end_time)
                  )
                  OR
                  (t1.start_time >= t2.start_time 
                       AND (t2.end_time IS NULL OR t1.start_time <= t2.end_time) 
                  ))
GROUP BY t1.machineId, t1.part_id

I tested this query on the following data:

machine_id   |part_id |start_time           |end_time
-------------------------------------------------------------------------
1           |2       |05 Oct 2009 09:00:00  |NULL
1           |3       |05 Oct 2009 08:00:00  |05 Oct 2009 10:00:00
2           |2       |30 Sep 2009 12:00:00  |30 Sep 2009 14:00:00
2           |3       |30 Sep 2009 15:00:00  |30 Sep 2009 16:00:00
2           |4       |30 Sep 2009 16:00:00  |30 Sep 2009 17:00:00
3           |2       |28 Sep 2009 12:00:00  |28 Sep 2009 14:00:00
3           |4       |28 Sep 2009 13:00:00  |28 Sep 2009 15:00:00

I got this:

machine_id   |start_time             |end_time
-----------------------------------------------------------------
1           |05 Oct 2009 08:00:00   |01 Jan 3210 00:00:00
2           |30 Sep 2009 12:00:00   |30 Sep 2009 14:00:00
2           |30 Sep 2009 15:00:00   |30 Sep 2009 17:00:00
3           |28 Sep 2009 12:00:00   |28 Sep 2009 15:00:00

SELECT machineid, min(start_time), max(ifnull(end_time, '3000-01-01 00:00'))
FROM faults
GROUP BY machineid

should do the job (replacing ifnull by the equivalent Oracle function if needed).

I wish I had time to give a full answer, but here is a hint to find overlapping downtimes:

select a.machineid, a.start_time, a.end_time, b.start_time, b.end_time
from faults a,
     faults b,
where a.machineid = b.machineid
  and b.start_time >= a.start_time
  and b.start_time <= a.end_time;

I believe you would need a stored proc to do this, or something like recursive 'Common Table Expressions (CTEs) (as exists in SQL srever), or otherwise (in a single SQL Statement) you would not be able to get the right answer when 3 or more rows togeher form a contiguous range of covered dates.

like:

 |----------|
           |---------------|
                        |----------------|

Without actually going through the exercise, I might suggest that in the stored proc, build a table of all "candidate dates" and then construct a table that contains all the dates that are NOT covered by a daterange in an existing row, then build your output resultset by "negating" this set.

See this discussion - with a solution near the bottom: http://www.microsoft.com/communities/newsgroups/en-us/default.aspx?dg=microsoft.public.sqlserver.programming&tid=2bae93da-c70e-4de4-a58b-d8cc0bf8ffd5

Hehe.

In SIRA_PRISE, which supports interval types, solving this problem would be as easy as

SELECT machineID, period FROM Faults.

IN which 'period' is an attribute of the time interval type whose start and end points are start_time and end_time of your SQL table.

But since you are presumably forced to solve this in SQL, and with a system that does not support interval types, I can only wish you a lot of courage.

Two hints :

The union of two intervals can be handled in SQL using complex CASE constructs (if interval_values_overlap then lowest_start_time highest_end_time, all that sort of stuff).

Since you cannot tell beforehand how many rows will merge into one, you will presumably find yourself forced to write recursive SQL.