Logo Home    Page list

Ancestors Query - Recursive #recursive

The result of this query is a list of the Record Numbers of the birth or bloodline ancestors of a given person. Not very useful by itself, it is a first effort at a recursive query exploiting the WITH RECURSIVE syntax and common-table-expressions support introduced in SQLite 3.8.3 2014-02-03. The earlier Ancestors Query was non-recursive and limited to 12 generations; this recursive query is unlimited. Moreover, it is on the order of five times faster (60ms vs 300ms, for example). It may be that there were ways that one could do recursion in earlier SQLite versions but I did not recognise how to do it until the word RECURSIVE jumped out in the syntax.


-- RecursiveAncestors.sql
2014-04-13 Tom Holden ve3meo
Generates the list of RINs for the ancestors of a person.
Uses the WITH RECURSIVE syntax introduced in SQLite 3.8.3 2014-02-03
/* modelled on http://www.sqlite.org/lang_with.html example:
The next example uses two common table expressions in a single WITH clause. The following table records a family tree:
  mom TEXT REFERENCES family,
  dad TEXT REFERENCES family,
  born DATETIME,
  died DATETIME, -- NULL if still alive
  -- other content
The "family" table is similar to the earlier "org" table except that now there are two parents to each member. We want to know all living ancestors of Alice, from oldest to youngest. An ordinary common table expression, "parent_of", is defined first. That ordinary CTE is a view that can be used to find all parents of any individual. That ordinary CTE is then used in the "ancestor_of_alice" recursive CTE. The recursive CTE is then used in the final query:
  parent_of(name, parent) AS
    (SELECT name, mom FROM family UNION SELECT name, dad FROM family),
  ancestor_of_alice(name) AS
    (SELECT parent FROM parent_of WHERE name='Alice'
     SELECT parent FROM parent_of JOIN ancestor_of_alice USING(name))
SELECT family.name FROM ancestor_of_alice, family
 WHERE ancestor_of_alice.name=family.name
   AND died IS NULL
 ORDER BY born;
  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 RelFather=0 --birth father (remove WHERE constraint to include all relationships)
     SELECT PersonID, MotherID AS ParentID FROM PersonTable
       LEFT JOIN ChildTable ON PersonID=ChildTable.ChildID
       LEFT JOIN FamilyTable USING(FamilyID)
       WHERE RelMother=0 --birth mother (remove WHERE constraint 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
Don't ask me how it works - I'm not sure...