récursive MySQL requête

Question

Mon schéma de base de données ressemble à ceci:

Table t1: 
    id 
    valA 
    valB 

Table t2: 
    id 
    valA 
    valB 

Ce que je veux faire, est, pour un ensemble donné de lignes dans une de ces tables, trouver des lignes dans les deux tables qui ont le même valA ou valB (en comparant valA avec valA et valB avec valB, pas valA avec valB). Puis, je veux chercher les lignes avec le même valA ou valB que les lignes dans le résultat de la requête précédente, et ainsi de suite.

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 

Je voudrais avoir le niveau de la recherche à ce que la ligne a été trouvée dans le résultat (par exemple dans l'exemple 1: Niveau 1 pour t1/2 et t2/1, niveau 2 pour t1/5, ...) A profondeur limitée de récursion est correct. Au fil du temps, je souhaite peut-être inclure plus de tables suivant le même schéma dans la requête. Ce serait bien si c'était facile d'étendre la requête à cette fin.

Mais ce qui importe le plus, c'est la performance. Pouvez-vous me dire la manière la plus rapide possible d'accomplir ceci?

Merci d'avance!

Answer 1

essayer même si ce n'est pas entièrement testé, mais ressemblait à ça fonctionnait: 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

Vous pouvez le faire avec les procédures stockées (voir la liste 7 et 7 bis):

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

Vous avez juste besoin de trouver une requête pour l'étape de la récursion - prendre les lignes déjà trouvés et trouver plus de lignes.

Si vous aviez une base de données prise en charge SQL-99 expressions de table commune récursive (comme PostgreSQL ou Firebird, hint hint), vous pouvez prendre la même approche que dans le lien ci-dessus, mais en utilisant un CRTE comme cadre, afin d'éviter le besoin d'écrire une procédure stockée.

EDIT: J'ai essayé de le faire avec un rCTE dans PostgreSQL 8.4, et bien que je puisse trouver les lignes, je ne trouve pas un moyen de les étiqueter avec la profondeur à laquelle ils ont été trouvés. Tout d'abord, je crée aa vue d'unifier les tables:

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

Effectuez ensuite cette requête:

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; 

Vous imaginez que la profondeur de capture serait aussi simple que l'ajout d'une colonne de profondeur au CRTE, définissez à zéro dans la requête de départ, puis en quelque sorte incrémenté dans l'étape récursive. Cependant, je ne trouvais aucun moyen de le faire, étant donné que vous ne pouvez pas écrire de sous-requêtes sur le rCTE dans l'étape récursive (donc rien de semblable à select max(depth) + 1 from descendants dans la liste des colonnes), et vous ne pouvez pas utiliser une fonction colonne liste (donc pas max(p.depth) + 1 dans la liste des colonnes couplé avec un group by c.* sur le select).

Vous devez également ajouter une restriction à la requête pour exclure les lignes déjà sélectionnées; vous n'avez pas besoin de faire cela dans la version de base, à cause de l'effet distinctif de l'union, mais si vous ajoutez une colonne de compte, alors une ligne peut être incluse dans les résultats plus d'une fois avec des comptes différents, et vous aurez obtenir une explosion cartésienne.Mais vous ne pouvez pas l'empêcher facilement, car vous ne pouvez pas avoir de sous-requêtes sur le rCTE, ce qui signifie que vous ne pouvez rien dire comme and not exists (select * from descendants d where d.tbl = c.tbl and d.id = c.id)! Je sais que tout ce truc sur les requêtes récursives ne vous sert à rien, mais je trouve ça fascinant, alors s'il vous plaît excusez-moi.