Часть таблиы в таблице

LykovAleksey
Дата: 07.12.2007 08:44:05
Есть таблица t1(t1_id,t1_name,t1_tag) order by t1.t1_id
Есть таблица t2(t2_id,t2_main_id,t2_name,t2_tag) order by t2.t2_main_id, t2.t2_id

Необходимо найти t2_main_id и min(t1_id),
таки что в таблице t1 присутствуют все записи для t2.t2_main_id, порядок следования для t2_main_id совпадает. Соответствующие поля t1_name=t2_name и t1_tag=t2_tag

Пример:
t1:
1 name1 tag1
2 name2 tag2
3 name3 tag3
4 name4 tag4
5 name2 tag2
6 name3 tag3
7 name5 tag5
8 name2 tag2

t2:

1 1 name2 tag2
2 1 name3 tag3
3 2 name1 tag1
4 2 name2 tag2
5 2 name3 tag3
6 3 name2 tag2
7 3 name3 tag3
8 3 name5 tag5
9 3 name2 tag2
10 4 name2 tag9

результат:

t2_main_id и min(t1_id),
1 2
1 6
2 1
3 5
Elic
Дата: 07.12.2007 09:18:26
LykovAleksey
результат:
t2_main_idmin(t1_id)
12
16
21
35
with
t1 as
( select  1 t1_id, 'name1' t1_name, 'tag1' t1_tag from dual union all
  select  2, 'name2', 'tag2' from dual union all
  select  3, 'name3', 'tag3' from dual union all
  select  4, 'name4', 'tag4' from dual union all
  select  5, 'name2', 'tag2' from dual union all
  select  6, 'name3', 'tag3' from dual union all
  select  7, 'name5', 'tag5' from dual union all
  select  8, 'name2', 'tag2' from dual
),
t2 as
( select  1 t2_id, 1 t2_main_id, 'name2' t2_name, 'tag2' t2_tag from dual union all
  select  2, 1, 'name3', 'tag3' from dual union all
  select  3, 2, 'name1', 'tag1' from dual union all
  select  4, 2, 'name2', 'tag2' from dual union all
  select  5, 2, 'name3', 'tag3' from dual union all
  select  6, 3, 'name2', 'tag2' from dual union all
  select  7, 3, 'name3', 'tag3' from dual union all
  select  8, 3, 'name5', 'tag5' from dual union all
  select  9, 3, 'name2', 'tag2' from dual union all
  select  10, 4, 'name2', 'tag9' from dual
),
--
tt1 as (select t1.*, row_number() over (partition by t1_name, t1_tag order by t1_id) as t1_rn from t1),
tt2 as (select t2.*, row_number() over (partition by t2_name, t2_tag order by t2_main_id, t2_id) as t2_rn from t2)
--
select t2_main_id, min(t1_id)
  from tt1, tt2
  where t1_name = t2_name
    and t1_tag  = t2_tag
    and t1_rn   = t2_rn
  group by t2_main_id
;

   T2_MAIN_ID    MIN(T1_ID)
------------- -------------
            1             2
            2             1
            3             7
LykovAleksey
таки что в таблице t1 присутствуют все записи для t2.t2_main_id, порядок следования для t2_main_id совпадает.
__
LykovAleksey
Дата: 07.12.2007 10:04:43
Elic
LykovAleksey
результат:
[quot LykovAleksey]таки что в таблице t1 присутствуют все записи для t2.t2_main_id, порядок следования для t2_main_id совпадает.
__


Я имел ввиду, что например в данном случае должна быть, ещё одна запись:
1 5

т.к. группа номер один второй таблицы полностью присутствует в двух местах первой таблицы.
(
5 name2 tag2
6 name3 tag3
)

а в данном варианте берётся только один случай вхождения
Elic
Дата: 07.12.2007 12:15:16
Чисто из любви к искусству:
with
t1 as
( select  1 t1_id, 'name1' t1_name, 'tag1' t1_tag from dual union all
  select  2, 'name2', 'tag2' from dual union all
  select  3, 'name3', 'tag3' from dual union all
  select  4, 'name4', 'tag4' from dual union all
  select  5, 'name2', 'tag2' from dual union all
  select  6, 'name3', 'tag3' from dual union all
  select  7, 'name5', 'tag5' from dual union all
  select  8, 'name2', 'tag2' from dual
),
t2 as
( select  1 t2_id, 1 t2_main_id, 'name2' t2_name, 'tag2' t2_tag from dual union all
  select  2, 1, 'name3', 'tag3' from dual union all
  select  3, 2, 'name1', 'tag1' from dual union all
  select  4, 2, 'name2', 'tag2' from dual union all
  select  5, 2, 'name3', 'tag3' from dual union all
  select  6, 3, 'name2', 'tag2' from dual union all
  select  7, 3, 'name3', 'tag3' from dual union all
  select  8, 3, 'name5', 'tag5' from dual union all
  select  9, 3, 'name2', 'tag2' from dual union all
  select  10, 4, 'name2', 'tag9' from dual
),
--
tt1 as (select t1.*, row_number() over (order by t1_id) as t1_rn from t1),
tt2 as (select t2.*, row_number() over (partition by t2_main_id order by t2_id) as t2_rn from t2),
ttt1 as
( select connect_by_root t1_id as t1_id, sys_connect_by_path(t1_name||'^'||t1_tag, '\') as t1_path
    from tt1, (select max(count(*)) as max_level from tt2 group by t2_main_id)
    connect by t1_rn = prior t1_rn + 1 and level <= max_level
),
ttt2 as
( select t2_main_id, max(sys_connect_by_path(t2_name||'^'||t2_tag, '\')) as t2_path
    from tt2
    start with t2_rn = 1
    connect by t2_rn = prior t2_rn + 1 and t2_main_id = prior t2_main_id
    group by t2_main_id
)
select distinct t2_main_id, t1_id
  from ttt1, ttt2
  where t1_path like t2_path || '%'
  order by 1, 2
;

   T2_MAIN_ID         T1_ID
------------- -------------
            1             2
            1             5
            2             1
            3             5
Но реальные данные наверняка не пролезут в ограничения :)
Elic
Дата: 07.12.2007 12:36:35
Для тех, кто захочет решить эту интересную и по сути пятничную задачу поясню, чего же не сказал автор.
Каждая группа в т2 - это окно. Нужно найти все начала соответствующих окон в т1.
LykovAleksey
Дата: 07.12.2007 12:46:35
Elic
Для тех, кто захочет решить эту интересную и по сути пятничную задачу поясню, чего же не сказал автор.
Каждая группа в т2 - это окно. Нужно найти все начала соответствующих окон в т1.


Зачёт!!!!!!!!! Спасибо !!!!
Vladimir Sitnikov
Дата: 07.12.2007 13:10:21
Elic
Для тех, кто захочет решить эту интересную и по сути пятничную задачу поясню, чего же не сказал автор.
Каждая группа в т2 - это окно. Нужно найти все начала соответствующих окон в т1.
А, если перевести с русского на русский, то автор попросил решить задачу поиска подстроки в строке:
таблица t1 -- это "текст", в котором ищут слова. Буквами являются комбинации (name, tag)
t2 -- набор слов, которые мы будем искать (t2_main_id -- идентификатор "слова").

Соотвественно, алгоритм решения существенно зависит от ограничений, которые наложены на входные данные.
LykovAleksey
Дата: 07.12.2007 14:45:17
На самом деле задача ещё совсем другая:
Надо найти поддерево в дереве :-)
Vladimir Sitnikov
Дата: 07.12.2007 14:55:30
LykovAleksey
На самом деле задача ещё совсем другая:
Надо найти поддерево в дереве :-)
Не хочу вас огорчать, но ни о каких деревьях тут речи не идёт.

STFF усложнять просто
Jannny
Дата: 07.12.2007 15:04:07
не так давно было
В основном вариантов решения подобных задач всегда 3:
1) собрать(как-либо) строку, представляющую массив
2) писать кучу подзапросов с exists
3) сравнивать наборами (multiset)
Ничего не забыла?