Рекурсивный запрос MySQL

Question

Моя схема базы данных выглядит следующим образом:

Table t1:
    id
    valA
    valB

Table t2:
    id
    valA
    valB

Что я хочу сделать, это для данного набора строк в одной из этих таблиц, найти строки в обеих таблицах, которые имеюттот же valA или valB (сравнение valA с valA и valB с valB, а не valA с valB). Затем , я хочу искать строки с тем же valA или valB, что и строки в результате предыдущего запроса, и так далее .

Example data:

t1 (id, valA, valB):
    1, a, B
    2, b, J
    3, d, E
    4, d, B
    5, c, G
    6, h, J

t2 (id, valA, valB):
    1, b, E
    2, d, H
    3, g, B


Example 1:

Input: Row 1 in t1
Output: 
    t1/4, t2/3
    t1/3, t2/2
    t2/1
    ...


Example 2:

Input: Row 6 in t1
Output:
    t1/2
    t2/1

Я бы хотел получить уровень поиска , при котором строка была найдена в результате (например, в примере 1: Уровень 1 для t1/ 2 и t2 / 1, уровень 2 для t1 / 5, ...) A ограниченная глубина рекурсии в порядке .Со временем я, возможно, захочу включить в запрос больше таблиц, следующих по той же схеме.Было бы хорошо, если бы для этой цели было легко расширить запрос.

Но самое главное, это производительность .Можете ли вы сказать мне самый быстрый способ сделать это?

Заранее спасибо!

Answer 1

попробуйте это, хотя это не полностью проверено, но выглядело, как будто оно работало: P (http://pastie.org/1140339)

drop table if exists t1;
create table t1
(
id int unsigned not null auto_increment primary key,
valA char(1) not null,
valB char(1) not null
)
engine=innodb;

drop table if exists t2;
create table t2
(
id int unsigned not null auto_increment primary key,
valA char(1) not null,
valB char(1) not null
)
engine=innodb;

drop view if exists t12;
create view t12 as
select 1 as tid, id, valA, valB from t1
union
select 2 as tid, id, valA, valB from t2;

insert into t1 (valA, valB) values 
('a','B'),
('b','J'),
('d','E'),
('d','B'),
('c','G'),
('h','J');

insert into t2 (valA, valB) values 
('b','E'),
('d','H'),
('g','B');

drop procedure if exists find_children;

delimiter #

create procedure find_children
(
in p_tid tinyint unsigned,
in p_id int unsigned 
)
proc_main:begin

declare done tinyint unsigned default 0;
declare dpth smallint unsigned default 0;


create temporary table children(
 tid tinyint unsigned not null,
 id int unsigned not null,
 valA char(1) not null,
 valB char(1) not null,
 depth smallint unsigned default 0,
 primary key (tid, id, valA, valB)
)engine = memory;

insert into children select p_tid, t.id, t.valA, t.valB, dpth from t12 t where t.tid = p_tid and t.id = p_id; 

create temporary table tmp engine=memory select * from children;

/* http://dec.mysql.com/doc/refman/5.0/en/temporary-table-problems.html */

while done <> 1 do

    if exists(
    select 1 from t12 t 
      inner join tmp on tmp.valA = t.valA or tmp.valB = t.valB and tmp.depth = dpth) then

        insert ignore into children
        select 
        t.tid, t.id, t.valA, t.valB, dpth+1 
      from t12 t
      inner join tmp on tmp.valA = t.valA or tmp.valB = t.valB and tmp.depth = dpth;

        set dpth = dpth + 1;            

        truncate table tmp;
        insert into tmp select * from children where depth = dpth;

    else
        set done = 1;
    end if;

end while;

select * from children order by depth;

drop temporary table if exists children;
drop temporary table if exists tmp;

end proc_main #


delimiter ;


call find_children(1,1);

call find_children(1,6);

Answer 2

Вы можете сделать это с помощью хранимых процедур (см. Листинги 7 и 7a):

http://www.artfulsoftware.com/mysqlbook/sampler/mysqled1ch20.html

Вам просто нужно выяснить запрос для шага рекурсии - взятьуже найденные строки и поиск еще нескольких строк.

Если у вас есть база данных, которая поддерживает рекурсивные общие табличные выражения SQL-99 (например, PostgreSQL или Firebird, подсказка подсказки), вы можете использовать тот же подход, что и вышессылка, но с использованием rCTE в качестве основы, поэтому избегая необходимости писать хранимую процедуру.

РЕДАКТИРОВАТЬ: я попытался сделать это с rCTE в PostgreSQL 8.4, и хотя я могу найти строки,я не могу найти способ обозначить их глубиной, на которой они были найдены.Во-первых, я создаю представление для объединения таблиц:

create view t12 (tbl, id, vala, valb) as (
  (select 't1', id, vala, valb from t1)
  union
  (select 't2', id, vala, valb from t2)
)

Затем выполните этот запрос:

with recursive descendants (tbl, id, vala, valb) as (
  (select *
  from t12
  where tbl = 't1' and id = 1) -- the query that identifies the seed rows, here just t1/1
  union
  (select c.*
  from descendants p, t12 c
  where (p.vala = c.vala or p.valb = c.valb)) -- the recursive term
)
select * from descendants;

Вы можете себе представить, что захват глубины будет таким же простым, как добавление столбца глубины кrCTE, равный нулю в начальном запросе, затем каким-то образом увеличивающийся на рекурсивном шаге.Тем не менее, я не смог найти никакого способа сделать это, учитывая, что вы не можете писать подзапросы к rCTE на рекурсивном шаге (так что ничего подобного select max(depth) + 1 from descendants в списке столбцов), и вы не можете использовать агрегатную функциюв списке столбцов (поэтому max(p.depth) + 1 в списке столбцов в сочетании с group by c.* для выбора).

Вам также необходимо добавить ограничение в запрос, чтобы исключить уже выбранные строки;вам не нужно делать это в базовой версии из-за отличительного эффекта объединения, но если вы добавите столбец подсчета, то строка может быть включена в результаты более одного раза с разным количеством, и выполучить картезианский взрыв.Но вы не можете легко предотвратить это, потому что у вас не может быть подзапросов к rCTE, что означает, что вы не можете сказать ничего подобного and not exists (select * from descendants d where d.tbl = c.tbl and d.id = c.id)!

Я знаю, что все эти вещи о рекурсивных запросах бесполезныЯ использую это, но я нахожу это захватывающим, поэтому, пожалуйста, извините.