As of Feb 3, 2014 and version 3.8.3, SQLite introduced “Recursive common table expressions (that) provide the ability to do hierarchical or recursive queries of trees and graphs, a capability that is not otherwise available in the SQL language”. (http://www.sqlite.org/lang_with.html) This means it is now possible to generate ancestry or descendancy lists within SQLite, without having to resort to a higher level language. These lists can be unlimited in length, unlike queries based on earlier versions of SQLite, which required a SELECT statement for each generation (e.g. the 2011 Ancestors Query). The WITH RECURSIVE syntax is much shorter than cascading like queries and executes much faster (60ms vs 300ms, for example). While the syntax is challenging to understand, an error or change needs to be dealt with in one or two spots, not in every SELECT in a cascade. Here’s a helpful guide to gain understanding: The Simplest SQLite Common Table Expression Tutorial.

A first attempt at a recursive query was reported on Ancestors Query – Recursive. I then proceeded to develop the complement – a recursive Descendants query. Because the two are complementary and will benefit from parallel development, and because recursion is such a significant step forward in the power of SQLite, a page focussed on recursion as it applies to the two essential genealogical queries seems appropriate. This page presents an enhanced Ancestors query and its complementary Descendants query and will, hopefully, see further development.

rev 2015-11-24 Descendants: filter added for sex so that a birth only relationship for female descendants of a woman would be those sharing mtDNA from her; the complementary male line is also provided which would those sharing the Y-STR chromosome. Note that RootsMagic has in its Select People dialogs tools to mark/unmark people by genetic lines.

Ancestors

This query is fundamentally the same as Ancestors Query – Recursive with the addition of named parameters which the user defines at run-time:

1. $BirthOnly(YN): enter “Y” or “y” to restrict the lineage to birth relationships (bloodlines); entry of anything else will include all relationships (adoptive, step, etc.)
2. $Person(RIN): enter the record number of the person whose list of ancestors is wanted

The result is a list of the record numbers of the ancestors under the heading AncestorID and does not include the starting RIN.
AncestorsRecursive.sql

-- AncestorsRecursive.sql
/*
2014-04-14 Tom Holden ve3meo
 
Generates the list of RINs for the ancestors of a person.
 
Requires support not only for SQLite 3.8.3 or later but also
for named parameters for user input of the RIN of the starting person
and choice of birth only or all relationships.
 
Developed and tested with current SQLite Expert Personal 3.5.36.2456
 
Uses the WITH RECURSIVE syntax introduced in SQLite 3.8.3 2014-02-03
modelled on http://www.sqlite.org/lang_with.html example
and complement of DescendantsRecursive.sql
*/
 
WITH RECURSIVE
  parent_of(ChildID, ParentID) AS
    (SELECT PersonID, FatherID AS ParentID FROM PersonTable
       LEFT JOIN ChildTable ON PersonID=ChildTable.ChildID
       LEFT JOIN FamilyTable USING(FamilyID)
       WHERE
         CASE $BirthOnly(YN)
         WHEN 'Y' OR 'y' THEN RelFather=0
         ELSE 1
         END
         --RelFather=0 --birth father (ELSE WHERE 1 to include all relationships)
     UNION
     SELECT PersonID, MotherID AS ParentID FROM PersonTable
       LEFT JOIN ChildTable ON PersonID=ChildTable.ChildID
       LEFT JOIN FamilyTable USING(FamilyID)
       WHERE
         CASE $BirthOnly(YN)
         WHEN 'Y' OR 'y' THEN RelMother=0
         ELSE 1
         END
         --RelMother=0 --birth mother (ELSE WHERE 1 to include all relationships)
     ),
  ancestor_of_person(AncestorID) AS
    (SELECT ParentID FROM parent_of
       WHERE ChildID=$Person(RIN) --enter RIN of starting person at runtime
     UNION --ALL
     SELECT ParentID FROM parent_of
       INNER JOIN ancestor_of_person ON ChildID = AncestorID)
SELECT AncestorID FROM ancestor_of_person, PersonTable
 WHERE ancestor_of_person.AncestorID=PersonTable.PersonID
;

Descendants

This query is a complement to the Ancestors query, structurally very similar, and with the same named parameters which the user defines at run-time:

1. $BirthOnly(YN): enter “Y” or “y” to restrict the lineage to birth relationships (bloodlines); entry of anything else will include all relationships (adoptive, step, etc.)
2. $Sex(MF?): enter one of “MmFf) to restrict the lineage to males or females only; anything else includes both.
3. $Person(RIN): enter the record number of the person whose list of descendants is wanted

The result is a list of the record numbers of the descendants under the heading DescendantID and does not include the starting RIN.
DescendantsRecursive.sql rev 2015-11-24 filter added for sex so that a birth only relationship for female descendants of a woman would be those sharing mtDNA from her. The code following is the original query.

-- DescendantsRecursive.sql
/*
2014-04-14 Tom Holden ve3meo
 
Generates the list of RINs for the descendants of a person.
 
Requires support not only for SQLite 3.8.3 or later but also
for named parameters for user input of the RIN of the starting person
and choice of birth only or all relationships.
 
Developed and tested with current SQLite Expert Personal 3.5.36.2456
 
Uses the WITH RECURSIVE syntax introduced in SQLite 3.8.3 2014-02-03
modelled on http://www.sqlite.org/lang_with.html example
and complement of AncestorsRecursive.sql
*/
 
WITH RECURSIVE
  child_of(ParentID, ChildID) AS
    (SELECT PersonID, ChildTable.ChildID FROM PersonTable
       LEFT JOIN FamilyTable ON PersonID=FatherID
       LEFT JOIN ChildTable USING(FamilyID)
       WHERE
         CASE $BirthOnly(YN)
         WHEN 'Y' OR 'y' THEN RelFather=0
         ELSE 1
         END
         --RelFather=0 --birth father (ELSE WHERE 1 to include all relationships)
     UNION
     SELECT PersonID, ChildTable.ChildID FROM PersonTable
       LEFT JOIN FamilyTable ON PersonID=MotherID
       LEFT JOIN ChildTable USING(FamilyID)
       WHERE
         CASE $BirthOnly(YN)
         WHEN 'Y' OR 'y' THEN RelMother=0
         ELSE 1
         END
         --RelMother=0 --birth mother (ELSE WHERE 1 to include all relationships)
     ),
  descendant_of_person(DescendantID) AS
    (SELECT ChildID FROM child_of
       WHERE ParentID=$Person(RIN) --enter RIN of starting person at runtime
     UNION --ALL
     SELECT ChildID FROM child_of
       INNER JOIN descendant_of_person ON ParentID = DescendantID)
SELECT DescendantID FROM descendant_of_person, PersonTable
 WHERE descendant_of_person.DescendantID=PersonTable.PersonID
;

To Do’s

1. Update previous queries that used the old cascaded Ancestors query, e.g., Ancestors Named Group
2. Create new queries based on these simple lists of ancestors and descendants, e.g. Named Groups and Color Coding
3. Investigate how one might add collateral lines
4. How might one apply the ancestry query to clearing the Living flag for ancestors of persons who should be dead.
5. Add generation number to results of ancestors and descendants – useful for reports
6. Add FamilyID to results