SQL Puzzle

Normally I’m very good at solving SQL issues, but this particular one has my mind twisted up in knots :frowning:

I have TWO tables (simplfied here for illustration)

Table #1 - Child, Parent, Attribute (where attribute is BLANK)
Table #2 - Person, Attribute (where attribute will be “1” or “2”, or there may be no record for “parent” at all

Objective : find the appropriate attribute for every Child based on themself, or their PARENT
Problem : those who don’t have a parent represented in table 2, look for a grandparent, or great-grandparent (until either a match is found, or come to end of “the chain”)

example SQL - which only works for direct parents :frowning:

  "SELECT a.child,a.parent,ifNull(CASE b.attribute WHEN '' THEN '*' ELSE b.attribute END,'????') as attribute " + _
  "  FROM table1 a" + _
  "  LEFT JOIN table2 b" + _
  "    ON a.child=b.person " 

table 1

C1  P1  -
C2  P2 -
C3  P3 -
P1  *   - 
P2  P4 -
P3 * -
P4  *

table 2

P1 A
P3 B
P4 C

C1 would get Attribute of “A” by virtue of P1 being its parent
C2 would get “C”, its parent… it doesnt have a parent in table 2, but does have a GRANDPARENT (C2->P2->P4)
That parent chain has to be able to be followed to the end… I don’t know if a match WILL be found, but I do know the chains are not recursive

Hi Dave,

What a fun(?) puzzle.
First question: Is this an existing database design you are being forced to work with or is this one you are designing yourself?

Next,
You have defined Table 1 as Child, Parent, Attribute.

[quote]table 1

C1 P1 - C2 P2 - C3 P3 - P1 * - P2 P4 - P3 * - P4 *
[/quote]

If a “Child” has no parent as is the case in P1, P3, and P4 then it is really a Parent without children and thus the values should be swapped around.
The logic is that any person has the potential to have children(nullable), but they may not have children. But every person must have a parent.
Also, parent/child relationships are recursive by definition.
I am sorry, I am not trying to play word games. You have been tremendously helpful to me and so many others in the past I would like to return the favor.
But either what you are trying to do fits the rules of parent/child relationships or it doesn’t. And if it doesn’t then it is not a parent child relationship, but something else. And if it is something else then I think we need to know more about the rules around the data.
Does that help?

Think of this a a series of Xojo Classes… and you need to find the super class that contains the declaration of a specific function

class A declares function xyz
class B is a subclass of class A
class C is a subclass of class B

C.XYZ is valid… but where was it actually declared? (given the database structure I showed above)

And yes all children have a parent (ie class has a superclass). but not all “people” (classes) have a particular attribute, but they inherit it… so who did they inherit it from? C2 inherits ultimatly from P4, just like class “C” inherits “xyz” from Class A

Its a linked list.
I dont think Dave meant recursive so much as ‘no child can be it’s own ancestor’

eg A -> B ->C ->A does not occur

I would hope there is a limit to the chain.
eg ‘cannot be be more than 10 levels deep’
If so, an inelegant solution is a set of views of increasingly nested complexity.
Then a union query to bind them all together

Inelegant because Dave wants a ‘single query solution’ I expect , rather than an algorithm

I dont understand the purpose of ‘attribute’ in table 1
Attributes are attributes of the person.
All people have a people record.
Some of these records have non-null attributes.

All people with attributes:

create view lev1 as
select person,attribute from t2 where attribute is not null;[/code]

All people whose parent has an attribute while they do not:

[code]create view lev2 as
select t2.person, t1.attribute from t1,t2 where t1.parent = t2  
and t2.attribute is not null
and t1.person not in (select person from lev1);[/code]

[code]create view lev2a as
select person, attribute from lev1 union select person, attribute from lev2;

create view lev3 as select t2.person, t1.attribute from t1,t2 where t1.parent = t2 and t2.attribute is not null and t1.person not in (select person from lev2a);

create view lev3a as select person, attribute from lev2a union select person, attribute from lev3;

and so on, until there are no extra rows added… 6,7 levels?

Finally select * from the last level.

[quote=278571:@Jeff Tullin]Its a linked list.
I dont think Dave meant recursive so much as ‘no child can be it’s own ancestor’[/quote]

Fair enough. :slight_smile:

One way of doing this also, if you know the max number of levels deep it can go, is through a series of left outer joins:

SELECT
T1.Parent,
T1.Child,
T1.Attribute,
T2.Parent,
T2.Child,
T2.Attribute,
T3.Parent,
T3.Child,
T3.Attribute,
ETC…
FROM Table1 T1 --Level 1
LEFT OUTER JOIN
Table1 T2 --Level 2
ON T1.Child = T2.Parent
LEFT OUTER JOIN
Table1 T3 --Level 3
ON T2.Child = T3.Parent
ETC…
WHERE T1.Parent IS NULL --this sets things to the top of the list or hierarchy

I have seen this sort of thing perform decently well as long as the Parent & Child columns are indexed for as many as 15 levels deep.
The drawback here is that you have to read through the recordset, find “C” then you would know if one of the parents has the function “XYZ”.

Oracle & SQL Server both have hierarchy functions that would likely make this easier.
I just did something like this on SQL Server and the hierarchy functions, using the hierarchy data type, allowed me to get all the ancestors or descendants that match certain criteria. Which I think is what you are looking to do.

distance from child to ancestor if unknown… it might be their “parent”. it might be a great-g-g-g-g-g-parent, or it may be nobody at all

the question is “From whom did XXX inherit what attribute, if any?”
the “attribute” is the table2 in my first query

A single SQL query solution while most elegant is not mandatory… super speed is not important… accuracy is.

Since it is of unknown depth I think the best approach would be a recursive function that checks for the attribute at each layer. If it is found then return that info else keep walking the tree.

So:

Method = WalkTree(ChildId as Integer)
strSQL = SELECT * from Table1 where Child = "X" -- gives you all the immediate parents
rs = db.SQLSelect(strSQL)
Do Until rs.EOF
If rs.field("Attribute").StringValue = "XYZ" then 
Found = True
ParentId = rs.Field("Parent").IntegerValue
Exit
End If
ParentArray.Append  rs.Field("Parent").IntegerValue
rs.MoveNext
Loop

If Found = False then
For x = 0 to ParentArray.Ubound
WalkTree(ParentArray(x))
Next x
End If

I am sure there are more elegant ways of doing this, but I think this at least communicates the main idea.

Isn’t this working:

[code]Dim ArrayDepth As Integer

ArrayDepth = ParentArray.Ubound

If Not Found Then
For x = 0 To ArrayDepth
WalkTree(ParentArray(x))
Next x
End If[/code]

Isn’t she lovely ?
(Stewie Wonder)