Recursive SQL Query

Feb 17, 2011 by Clinovo    No Comments    Posted under: New Technologies

A family tree is a relation (Father, Mother, Child). The restriction of this relation to subrelation (Father, Son) or (Mother, Daughter) looks more like a tree in the sense of computer data structure.

It is a quite common question in genealogy to trace the ancestry of a given offspring. The algorithm can be specified recursively in a language agnostic way:

Take the paternal branch of the family tree. The ancestry of a male offspring A is the union of the father of A and the ancestry of the father of A.

How could this question be addressed from within SAS? Consider the following three generation family tree where each individual is coded with an id number:


data FamilyTree; input Father Mother Child;
datalines;
1 2 9
1 2 10
1 2 11
3 4 12
3 4 13
3 4 14
3 4 15
5 6 16
5 6 17
7 8 18
7 8 19
7 8 20
9 12 21
9 12 22
9 12 23
10 16 24
10 16 25
15 18 26
15 18 27
;
run;


The following SAS macro prints out the entire paternal ancestry of a given offspring:


%macro Tracing(OffSpring,
Q=%str(select Father from FamilyTree where Child in (&OffSpring))
);
proc sql;
%unquote(&Q)
;quit;
%if &sqlobs %then
%Tracing(&OffSpring,
Q=%str(select Father from FamilyTree where Child in ( &Q ))
)
;
%mend;


To test, try

%Tracing(21)


The following SAS macro searches and puts the earliest forefather of a given offspring into a macro variable:

%macro ForeFather(Id);
%local Tmp;
proc sql noprint;
select Father into :Tmp from FamilyTree
where Child = &Id;
quit;
%if &sqlobs %then %do;
%ForeFather(&Tmp)
%end;
%else %do;
%global FFather;
%let FFather=&Id;
%end;
%mend;


To test, try

%ForeFather(26)


Reference:
http://tech.groups.yahoo.com/group/sas081708/message/325