Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Oracle Новый топик    Ответить
Топик располагается на нескольких страницах: [1] 2   вперед  Ctrl      все
 Помогите составить запрос - пересекающиеся интервалы  [new]
Cross over
Guest
Доброго времени суток, всем участникам форума!!!
Помогите, пожалуйста, решить задачу (составить запрос на SQL).
Суть задачи в следующем: дана числовая ось (все действительные числа, от -00 до +00), на этой числовой оси отмечены числовые интервалы, принадлежащие разным типам интервалов (различным числовым подмножествам: все натуральные, все целые, все положительные, все положительные целые, все отрицательные целые, все отрицательные и т.д. и т.п.).
Есть таблица, описывающая отрезки на этой прямой. Необходимо найти все пересекающиеся интервалы в пределах одинакового типа отрезков.
CREATE TABLE NUM_INTERVAL 
   (
     INTERVAL_ID    NUMBER(10), 
     BEGIN_X        NUMBER, 
     END_X          NUMBER, 
     INTERVAL_TYPE  NUMBER(10)
   )
/
INSERT INTO NUM_INTERVAL VALUES (1,  0, 10, 1);
INSERT INTO NUM_INTERVAL VALUES (2, 10, 20, 1);
INSERT INTO NUM_INTERVAL VALUES (3, 20, 30, 1);
INSERT INTO NUM_INTERVAL VALUES (4, 30, 40, 1);
INSERT INTO NUM_INTERVAL VALUES (5, 40, 50, 1);
INSERT INTO NUM_INTERVAL VALUES (6,  5, 20, 1);
INSERT INTO NUM_INTERVAL VALUES (7, 50, 60, 1);
INSERT INTO NUM_INTERVAL VALUES (8, 45, 55, 1);
COMMIT;
Где:
INTERVAL_ID идентификатор записи в таблице (добавил это поле исключительно для демонстрации того, что мне нужно будет в итоге выбрать)
BEGIN_X координата начала отрезка
END_X координата конца отрезка
INTERVAL_TYPE тип интервала, которому принадлежит отрезок

Считаем, что отрезки - величина невекторная, не имеющая направленности. Поэтому принимаем за аксиому следующее утверждение: координата начала отрезка всегда меньше координаты конца отрезка (обеспечивается соответствующим триггером и последующей периодической проверкой).
Хотелось бы получить посредсвом SQL-запроса все отрезки внутри типа, которые имеют между собой пересечения. За пересечение принять наличие у отрезков более одной общей точки, то есть, если начала одного отрезка совпадает с концом другого, то такие отрезки НЕ считаются ПЕРЕСЕКАЮЩИМИСЯ
В итоге из исходной информации видно, что пересекаются интервалы с ID 1, 2, 6 и 5, 7, 8, вот их-то всех и нужно выдать:
select * 
  from num_interval
order by begin_x, end_x

Query finished, retrieving results...

INTERVAL_ID  BEGIN_X  END_X  INTERVAL_TYPE
-----------  -------  -----  -------------
          1        0     10             1 
          6        5     20             1 
          2       10     20             1 
          3       20     30             1 
          4       30     40             1 
          5       40     50             1
          8       45     55             1
          7       50     60             1

8 row(s) retrieved



То есть, хотелось бы получить следующее:
INTERVAL_ID  INTERVAL_TYPE  BEGIN_X  END_X
----------- ------------- ------- -----
1 1 0 10
6 1 5 20
2 1 10 20
5 1 40 50
8 1 45 55
7 1 50 60
25 окт 05, 07:50    [2000825]     Ответить | Цитировать Сообщить модератору
 Re: Помогите составить запрос - пересекающиеся интервалы  [new]
Part
Member

Откуда: Краснодар
Сообщений: 187
Я так вижу :-), что нужно вывести те интервалы, для которых имеется хотя бы один интервал с которым он пересекается
select 
    * 
from 
    num_interval a
where
    exists
        (select
             1
        from
             num_interval b
        where
             b.interval_type = a.interval_type /* в одной категории  */
             and b.interval_id <> a.interval_id /* не он сам */
             and greates(a.begin_x, b.begin_x) > least(a.end_x, b.end_x)
        )
25 окт 05, 08:33    [2000872]     Ответить | Цитировать Сообщить модератору
 Re: Помогите составить запрос - пересекающиеся интервалы  [new]
Владимор Конев
Member

Откуда:
Сообщений: 3451
Part
Я так вижу :-), что нужно вывести те интервалы, для которых имеется хотя бы один интервал с которым он пересекается
select 
    * 
from 
    num_interval a
where
    exists
        (select
             1
        from
             num_interval b
        where
             b.interval_type = a.interval_type /* в одной категории  */
             and b.interval_id <> a.interval_id /* не он сам */
             and greates(a.begin_x, b.begin_x) > least(a.end_x, b.end_x)
        )
Такой вариант точно работать не будет!!! :-)
Он просто выдаст вообще все имеющиеся записи в таблице, и всё...
Но, если его немного переписать, то он станет вполне рабочим:
select 
    * 
from 
    num_interval a
where
    exists
        (select
             1
        from
             num_interval b
        where
             b.interval_type = a.interval_type /* в одной категории  */
             and b.interval_id <> a.interval_id /* не он сам */
             and greatest(a.begin_x, b.begin_x) < least(a.end_x, b.end_x)
        )
[/quot]То есть ты там со знаками > и < запутался :-).
25 окт 05, 08:40    [2000880]     Ответить | Цитировать Сообщить модератору
 Re: Помогите составить запрос - пересекающиеся интервалы  [new]
Part
Member

Откуда: Краснодар
Сообщений: 187
Да, каюсь, запутался и непроверил (-:
25 окт 05, 08:44    [2000883]     Ответить | Цитировать Сообщить модератору
 Re: Помогите составить запрос - пересекающиеся интервалы  [new]
CRep
Guest
select t.begin_x interval1_x1,
       t.end_x interval1_x2,
       t1.begin_x interval2_x1,
       t1.end_x interval2_x2
from   num_interval t,
       num_interval t1
where  ( t1.begin_x>t.begin_x 
         and t1.begin_x<t.end_x
       )
and    t1.end_x>=t.end_x
25 окт 05, 09:09    [2000930]     Ответить | Цитировать Сообщить модератору
 Re: Помогите составить запрос - пересекающиеся интервалы  [new]
Владимор Конев
Member

Откуда:
Сообщений: 3451
CRep
select t.begin_x interval1_x1,
       t.end_x interval1_x2,
       t1.begin_x interval2_x1,
       t1.end_x interval2_x2
from   num_interval t,
       num_interval t1
where  ( t1.begin_x>t.begin_x 
         and t1.begin_x<t.end_x
       )
and    t1.end_x>=t.end_x
А ты хоть сам-то пробывал посмотреть, чего выдаст твой запрос? Сдается мне, что он даже на приведенном наборе данных будет работать некорректно :-)
25 окт 05, 09:24    [2000984]     Ответить | Цитировать Сообщить модератору
 Re: Помогите составить запрос - пересекающиеся интервалы  [new]
CRep
Guest
Конечно я пробовал - и результат мне очень даже понравился.
В чем геометрический смысл поставленной задачи? В том что отрезки (или как вы их по-научному называете, интервалы) считаются пересекающимися, если начальная координата одного из них находится внутри другого отрезка... Короче долго объяснять... Вот такой наверно должен быть запрос:
select t.begin_x interval1_x1,
       t.end_x interval1_x2,
       t1.begin_x interval2_x1,
       t1.end_x interval2_x2
from   num_interval t,
       num_interval t1
where  ( t1.begin_x>=t.begin_x 
         and t1.begin_x<t.end_x
       )
and    ( t1.begin_x>t.begin_x 
         and t1.begin_x<=t.end_x
       )       
and    t1.interval_id<>t.interval_id
and    t1.interval_type=t.interval_type
and    t.interval_type=1
И попутно вопрос: Одинаковые отрезки считаются пересекающимися?
25 окт 05, 09:50    [2001086]     Ответить | Цитировать Сообщить модератору
 Re: Помогите составить запрос - пересекающиеся интервалы  [new]
Elic
Member

Откуда:
Сообщений: 29977
CRep
интервалы считаются пересекающимися, если начальная координата одного из них находится внутри другого отрезка...
Этот критерий выражается одной строчкой, выделенной Владимором.
CRep
Вот такой наверно должен быть запрос:
Если бред написать два раза, это нисколько не добавит ему гениальности
25 окт 05, 10:01    [2001128]     Ответить | Цитировать Сообщить модератору
 Re: Помогите составить запрос - пересекающиеся интервалы  [new]
Stax.
Guest
несколько не то (не совсем понял вопрос)
select 
  row_number() over(order by begin_x) n
 ,BEGIN_X
 ,end_x
from (
   select 
     x BEGIN_X
    ,lead(x) over (order by x) END_X 
   from
     (select BEGIN_X x from NUM_INTERVAL
      union 
      select END_X from NUM_INTERVAL) t
 )
where
 end_x is not null
/
SQL> /

        N   BEGIN_X     END_X
--------- --------- ---------
        1         0         5  в оригинале не так
        2         5        10
        3        10        20
        4        20        30
        5        30        40
        6        40        45
        7        45        50
        8        50        55
        9        55        60

9 rows selected.

........
Stax
25 окт 05, 10:01    [2001129]     Ответить | Цитировать Сообщить модератору
 Re: Помогите составить запрос - пересекающиеся интервалы  [new]
CRep
Guest
Elic
Если бред написать два раза, это нисколько не добавит ему гениальности

Ну тогда попробую написать в третий раз :)
select *
from   num_interval t
where  exists
       (
        select *
        from   num_interval t2
        where  t2.interval_id<>t.interval_id
        and    t2.interval_type=t.interval_type
        and    t2.interval_type=1
        and    t2.begin_x>=t.begin_x
        and    t2.begin_x<t.end_x
       )
or     exists
       (
        select *
        from   num_interval t3
        where  t3.interval_id<>t.interval_id
        and    t3.interval_type=t.interval_type
        and    t3.interval_type=1
        and    t.begin_x>=t3.begin_x
        and    t.begin_x<t3.end_x
       )
25 окт 05, 10:15    [2001197]     Ответить | Цитировать Сообщить модератору
 Re: Помогите составить запрос - пересекающиеся интервалы  [new]
Stax.
Guest
Запутался совсем
почему не подходит вариант Part (без очепятки)

select
    *
from
    num_interval a
where
    exists
        (select
             1
        from
             num_interval b
        where
             b.interval_type = a.interval_type /* в одной категории  */
             and b.interval_id <> a.interval_id /* не он сам */
             and greatest(a.begin_x, b.begin_x) < least(a.end_x, b.end_x)
        )
SQL> /

INTERVAL_ID   BEGIN_X     END_X INTERVAL_TYPE
----------- --------- --------- -------------
          1         0        10             1
          2        10        20             1
          5        40        50             1
          6         5        20             1
          7        50        60             1
          8        45        55             1

6 rows selected.


.......
Stax
25 окт 05, 10:15    [2001203]     Ответить | Цитировать Сообщить модератору
 Re: Помогите составить запрос - пересекающиеся интервалы  [new]
Cross Over
Guest
CRep
Конечно я пробовал - и результат мне очень даже понравился.
И попутно вопрос: Одинаковые отрезки считаются пересекающимися?
ТО, что результат понравился тебе, ещё не значит, что он и мне понравится :-). Результат работы твоего запроса не тот,что мне нужен.
Что касается попутного вопроса - то такого быть не может.
В оригинале таблицы ещё есть ограничение уникальности по трем полям: тип отрезка, начало отрезка, конец отрезка.
25 окт 05, 10:39    [2001350]     Ответить | Цитировать Сообщить модератору
 Re: Помогите составить запрос - пересекающиеся интервалы  [new]
Владимор Конев
Member

Откуда:
Сообщений: 3451
Stax.
Запутался совсем
почему не подходит вариант Part (без очепятки)
Потому что вариант Part без опечатки на приведенном автором топика наборе данных выдает все имеющиеся в таблице записи (все восемь штук, а должен был выдать 6 штук). Автор топика же довольно ясно всё описал и привел пример необходимой выборки :-)

От себя лично могу предложить вот такой вариант:
select int_1.interval_id,
       int_1.interval_type,
       int_1.begin_x,
       int_1.end_x
  from num_interval int_1,
       (
          select interval_id, 
                 interval_type,
                 begin_x,
                 end_x
            from (
                    select interval_id,
                           interval_type,
                           begin_x,
                           end_x,
                           case 
                              when lead(begin_x) 
                                   over (
                                           partition by interval_type 
                                               order by begin_x, end_x
                                        ) < end_x 
                              then 1 
                              else null 
                           end flag
                      from num_interval
                 ) v_middle
           where flag = 1
       ) int_2
 where int_2.interval_type = int_1.interval_type
   and greatest(int_1.begin_x, int_2.begin_x) < least(int_1.end_x, int_2.end_x)
   and int_1.interval_id != int_2.interval_id
order by int_1.interval_id
25 окт 05, 10:39    [2001352]     Ответить | Цитировать Сообщить модератору
 Re: Помогите составить запрос - пересекающиеся интервалы  [new]
Владимор Конев
Member

Откуда:
Сообщений: 3451
Владимор Конев
Stax.
Запутался совсем
почему не подходит вариант Part (без очепятки)
Потому что вариант Part без опечатки на приведенном автором топика наборе данных выдает все имеющиеся в таблице записи (все восемь штук, а должен был выдать 6 штук). Автор топика же довольно ясно всё описал и привел пример необходимой выборки :-)
Ой, кажись я тож уже запутался!
Изначально вариант Part был неверен, так как там была опечатка (знак сравнения не тот стоял, что нужно). Слегка подправленный мной вариант даёт корректные данные.
Кроме того, я привел свой вариант - с аналитикой.
Какой вариант выбрать - корректный (исправленный) от Part или тот, что привел я (с аналитикой) - решать уже автору топика. Как по мне, так варианты не эквивалентны в плане количества проделываемой работы (сдается мне, что они будут отличаться как минимум по числу логических чтений).
25 окт 05, 10:46    [2001411]     Ответить | Цитировать Сообщить модератору
 Re: Помогите составить запрос - пересекающиеся интервалы  [new]
Vint
Member

Откуда: Москва
Сообщений: 4564
Ну вы заморочились господа) а для 8 кто нить может написать чтобы не было ни greatest ни least, у меня сработал вот такой вариант но по моему он не всегда будет верен просьба покретиковать :))

SELECT distinct b.interval_id, b.begin_x, b.end_x, b.interval_type
  FROM num_interval a, num_interval b
 where (b.begin_x > a.begin_x and b.begin_x < a.end_x)
   OR (b.end_x > a.begin_x and b.end_x < a.end_x)
есть второй вариант но он по моему избыточен

SELECT distinct a.interval_id, a.begin_x, a.end_x, a.interval_type
  FROM num_interval a, num_interval b
 where (b.begin_x > a.begin_x and b.begin_x < a.end_x)
   OR (b.end_x > a.begin_x and b.end_x < a.end_x)
union
SELECT distinct b.interval_id, b.begin_x, b.end_x, b.interval_type
  FROM num_interval a, num_interval b
 where (b.begin_x > a.begin_x and b.begin_x < a.end_x)
   OR (b.end_x > a.begin_x and b.end_x < a.end_x)
25 окт 05, 11:01    [2001508]     Ответить | Цитировать Сообщить модератору
 Re: Помогите составить запрос - пересекающиеся интервалы  [new]
mcureenab
Member

Откуда: Murmansk
Сообщений: 5928
Cross over

Считаем, что отрезки - величина невекторная, не имеющая направленности. Поэтому принимаем за аксиому следующее утверждение: координата начала отрезка всегда меньше координаты конца отрезка (обеспечивается соответствующим триггером и последующей периодической проверкой).


Декларативные ограничения целостности не прокатывают???


alter table num_interval add check (BEGIN_X<=END_X)

25 окт 05, 11:08    [2001544]     Ответить | Цитировать Сообщить модератору
 Re: Помогите составить запрос - пересекающиеся интервалы  [new]
Владимор Конев
Member

Откуда:
Сообщений: 3451
Vint
Ну вы заморочились господа) а для 8 кто нить может написать чтобы не было ни greatest ни least, у меня сработал вот такой вариант но по моему он не всегда будет верен просьба покретиковать :))

SELECT distinct b.interval_id, b.begin_x, b.end_x, b.interval_type
  FROM num_interval a, num_interval b
 where (b.begin_x > a.begin_x and b.begin_x < a.end_x)
   OR (b.end_x > a.begin_x and b.end_x < a.end_x)
есть второй вариант но он по моему избыточен

SELECT distinct a.interval_id, a.begin_x, a.end_x, a.interval_type
  FROM num_interval a, num_interval b
 where (b.begin_x > a.begin_x and b.begin_x < a.end_x)
   OR (b.end_x > a.begin_x and b.end_x < a.end_x)
union
SELECT distinct b.interval_id, b.begin_x, b.end_x, b.interval_type
  FROM num_interval a, num_interval b
 where (b.begin_x > a.begin_x and b.begin_x < a.end_x)
   OR (b.end_x > a.begin_x and b.end_x < a.end_x)
В обоих вариант как минимум не хватает условия на проверку принадлежности интервалов к одному типу.
Во втором варианте та часть запроса, что указана до UNION - вообще лишняя. Там и нижнего куска хватит...
25 окт 05, 11:21    [2001644]     Ответить | Цитировать Сообщить модератору
 Re: Помогите составить запрос - пересекающиеся интервалы  [new]
Part
Member

Откуда: Краснодар
Сообщений: 187
2 Vint В Восьмерке greatest, least замечательно работают
SQL>select greatest(1, 2), least(1, 2) from dual;

GREATEST(1,2) LEAST(1,2)
------------- ----------
            2          1

SQL> select * from v$version;

BANNER
----------------------------------------------------------------
Oracle8i Enterprise Edition Release 8.1.7.4.1 - Production
PL/SQL Release 8.1.7.4.0 - Production
CORE	8.1.7.2.1	Production

TNS for 32-bit Windows: Version 8.1.7.4.0 - Production
NLSRTL Version 3.4.1.0.0 - Production
25 окт 05, 11:23    [2001654]     Ответить | Цитировать Сообщить модератору
 Re: Помогите составить запрос - пересекающиеся интервалы  [new]
mcureenab
Member

Откуда: Murmansk
Сообщений: 5928
Vint

Ну вы заморочились господа) а для 8 кто нить может написать чтобы не было ни greatest ни least, у меня сработал вот такой вариант но по моему он не всегда будет верен просьба покретиковать :))


SELECT a.interval_id, a.begin_x, a.end_x, a.interval_type
  FROM num_interval a
 where exists
 (select *
  from num_interval b
  where
    a.begin_x < b.end_x and b.begin_x < a.end_x
    and b.interval_type = a.interval_type
 )
order by a.begin_x, a.end_x



INTERVAL_ID BEGIN_X END_X INTERVAL_TYPE
----------- --------- --------- -------------
1 0 10 1
6 5 20 1
2 10 20 1
3 20 30 1
4 30 40 1
5 40 50 1
8 45 55 1
7 50 60 1

8 rows selected.

25 окт 05, 11:24    [2001660]     Ответить | Цитировать Сообщить модератору
 Re: Помогите составить запрос - пересекающиеся интервалы  [new]
CRep
Guest
Vint
Ну вы заморочились господа) а для 8 кто нить может написать чтобы не было ни greatest ни least

select t.*
from   num_interval t
where  exists
       (
        select 1
        from   num_interval t2
        where  t2.interval_id<>t.interval_id
        and    t2.interval_type=t.interval_type
        and    t2.begin_x>=t.begin_x
        and    t2.begin_x<t.end_x
       )
or     exists
       (
        select 1
        from   num_interval t3
        where  t3.interval_id<>t.interval_id
        and    t3.interval_type=t.interval_type
        and    t.begin_x>=t3.begin_x
        and    t.begin_x<t3.end_x
       )
and  t.interval_type=1
Проверено, работает на предложенном автором наборе данных
25 окт 05, 11:35    [2001739]     Ответить | Цитировать Сообщить модератору
 Re: Помогите составить запрос - пересекающиеся интервалы  [new]
Владимор Конев
Member

Откуда:
Сообщений: 3451
Part
2 Vint В Восьмерке greatest, least замечательно работают
SQL>select greatest(1, 2), least(1, 2) from dual;

GREATEST(1,2) LEAST(1,2)
------------- ----------
            2          1

SQL> select * from v$version;

BANNER
----------------------------------------------------------------
Oracle8i Enterprise Edition Release 8.1.7.4.1 - Production
PL/SQL Release 8.1.7.4.0 - Production
CORE	8.1.7.2.1	Production

TNS for 32-bit Windows: Version 8.1.7.4.0 - Production
NLSRTL Version 3.4.1.0.0 - Production
Вся соль в том, что "восмерка" - это версия Oracle 8.0.х.х
А указанная тобой Oracle 8.1.7.х.х. - это уже Oracle 8i.
ТО есть, грубо говоря - это совершенно два разных сервера, имеющих лишь общую цифру 8 в названии. :-)
25 окт 05, 11:37    [2001752]     Ответить | Цитировать Сообщить модератору
 Re: Помогите составить запрос - пересекающиеся интервалы  [new]
Вячеслав Любомудров
Member

Откуда: Владивосток
Сообщений: 18483
Насколько мне помнится (могу ошибаться), GREAST, LEAST отлично работала в 7.3.4
25 окт 05, 11:43    [2001794]     Ответить | Цитировать Сообщить модератору
 Re: Помогите составить запрос - пересекающиеся интервалы  [new]
mcureenab
Member

Откуда: Murmansk
Сообщений: 5928
Пропустил проверку на пересечение интервала с самим собой. :c(

Vint

Ну вы заморочились господа) а для 8 кто нить может написать чтобы не было ни greatest ни least, у меня сработал вот такой вариант но по моему он не всегда будет верен просьба покретиковать :))


SELECT a.interval_id, a.begin_x, a.end_x, a.interval_type
  FROM num_interval a
 where exists
 (select *
  from num_interval b
  where
    a.begin_x < b.end_x and b.begin_x < a.end_x
    and b.interval_type = a.interval_type
    and not(a.interval_id = b.interval_id) -- так
-- and  not(a.begin_x = b.begin_x and a.end_x = b.end_x) -- или так
 )
order by a.begin_x, a.end_x
25 окт 05, 11:52    [2001861]     Ответить | Цитировать Сообщить модератору
 Re: Помогите составить запрос - пересекающиеся интервалы  [new]
Elic
Member

Откуда:
Сообщений: 29977
Вячеслав Любомудров
Насколько мне помнится (могу ошибаться), GREAST, LEAST отлично работала в 7.3.4
Во-во: Oracle7 Server SQL Reference Manual. Далась им эта версия :)

"Нелюбовь" к greatest&least можно объяснить только "любовью" к возможности индексных планов доступа.
25 окт 05, 11:53    [2001868]     Ответить | Цитировать Сообщить модератору
 Re: Помогите составить запрос - пересекающиеся интервалы  [new]
Part
Member

Откуда: Краснодар
Сообщений: 187
Еле нашел 7 :-)

SQL> select greatest(1, 2), least(1, 2) from dual;

GREATEST(1,2) LEAST(1,2)
------------- ----------
            2          1

SQL> select * from v$version;

BANNER
----------------------------------------------------------------
Oracle7 Server Release 7.3.4.3.0 - Production
PL/SQL Release 2.3.4.3.0 - Production
CORE Version 3.5.4.0.0 - Production
25 окт 05, 12:06    [2001952]     Ответить | Цитировать Сообщить модератору
Топик располагается на нескольких страницах: [1] 2   вперед  Ctrl      все
Все форумы / Oracle Ответить