MySQL Forums
Forum List  »  Stored Procedures

Re: Recursive Procedure or Function in Mysql
Posted by: Roland Bouman
Date: February 10, 2007 03:42AM

Hi Murali,

Lemme get this straight....this is a tree, and for a given id, you want all the rows that have that id as ref_id, and for those rows, you want to take the id's again, and repeat the process?

p_magic_proc(0)

returns 1,2,4,3,5

First of all, you should read up on the subject of trees. You are now using what is called an "adjacency list model". It is very intuitive when you are adding, updating and removing data, but it is impossible to query. In many cases (and i think this is such a case), the "nested set model" is much more appropriate. Follow the link and read this article:

http://dev.mysql.com/tech-resources/articles/hierarchical-data.html

Follow links from there for more information.

Now, I know a lot of people still don't want to use that for reasons I personally don't understand. So, here's the solution if you want to stick to the adjacency list model. The one neat thing about a procedural approach is that you can also use it for networks - not just for trees.

Ok - here it is:

CREATE TABLE adjacency_list (
id int unsigned NOT NULL AUTO_INCREMENT
, name char(10) DEFAULT NULL,
, ref_id int unsigned DEFAULT NULL
, PRIMARY KEY (id)
, CONSTRAINT fk_ref_id
FOREIGN KEY (ref_id)
REFERENCES adjacency_list (id)
) ENGINE=InnoDB DEFAULT
;

insert into adjacency_list(
id,name,ref_id
) VALUES
(1,'A',null)
,(2,'B',1)
,(3,'C',2)
,(4,'D',1)
,(5,'E',4)
;

delimiter $$

drop procedure if exists p_breadth_first
$$

create procedure p_breadth_first(
p_id int unsigned
)
begin
declare v_level int unsigned default 0;
declare v_position int unsigned default 1;
declare v_row_count int unsigned default 0;

-- table for storing the result
create table
if not exists
tmp_adjacency_list(
pk int unsigned not null auto_increment -- insertion order
, id int unsigned -- id of the record
, level int unsigned -- level of search (depth)
, position int unsigned -- position of this record within this level
, primary key(pk)
);

-- discard contents from prior calls
truncate table tmp_adjacency_list;

-- insert our entrty record
insert
into tmp_adjacency_list(
id
, level
, position
)
values (p_id,v_level,v_position)
;

-- initialize our loop control variable
set v_row_count := row_count();

-- iterate, breadth first
while v_row_count != 0 DO

-- iterate, breadth first
set @position := 0;

-- insert all children for the current level
insert
into tmp_adjacency_list(
id
, level
, position
)
select al.id
, v_level + 1
, @position := @position+1
from adjacency_list al
inner join tmp_adjacency_list tal
on al.ref_id = tal.id
where tal.level = v_level
order by id
;

-- update loop control.
-- if there weren't any children of this level,
-- no new rows were inserted, and the loop will terminate
set v_row_count := row_count();

-- update the level
set v_level := v_level + 1;
end while;

-- show the result
select * from tmp_adjacency_list;
end;
$$

delimiter ;

call p_breadth_first(1);


Ok, let me know if you have any trouble understanding the procedure, I'll be happy to explain.

Options: ReplyQuote


Subject
Views
Written By
Posted
10607
September 08, 2006 12:44PM
Re: Recursive Procedure or Function in Mysql
13096
February 10, 2007 03:42AM


Sorry, you can't reply to this topic. It has been closed.

Content reproduced on this site is the property of the respective copyright holders. It is not reviewed in advance by Oracle and does not necessarily represent the opinion of Oracle or any other party.