You have to transform your table parent-child into a table of nested sets.
The subroutine
FromParentToNested
creates a table with a nested set representation of you parent-child
representation.
FromParentToNested( "yourTableName", "[second]", "[first]",
"tableNameToBeCreated")
The program requires a 'top parent', a parent node that is THE ultimate
parent of all, the 'top' of the tree. Such node is asssumed given with NULL
as parent.
Now, once you have the nested table, a table with a lft and rgt field,
you can use the following properties:
To get a node without child,
SELECT * FROM nestedTable
WHERE lft+1 = rgt
To get all children under a given parent:
SELECT * FROM nestedTable
WHERE lft BETWEEN [givenParent.lft] AND [givenParent.rgt]
To get all parent of a given node (which their count is the depth of the
given node, in the 'tree' ) :
SELECT * FROM nestedTable
WHERE [givenNode.lft] BETWEEN lft AND rgt
and your case, to get THE last child, given a node.lft and node.rgt
values:
SELECT * FROM nestedSet
WHERE lft BETWEEN [node.lft] AND [node.rgt]
AND lft+1=rgt
If there is an index on lft and on rgt, these queries run almost instantly
(well, need to reach the index pages, but that is almost all). So we can
"see" the nested-set table as a kind of pre-compilation, a little bit the
same as index are to research.
Here is the code that should allow you to create your nested set table (run
it only once, then only if you original table change do you have to rebuilt
your nested set table). Sure, if your table changes each minutes, that
makes the nested set table almost useless, since you would have to rebuilt
it each time too, and the benefit of the (probably single) use you would
made of it would have to justify the time spent building it !
Hoping it may help,
Vanderghast, Access MVP
-------------------
Option Compare Database
Option Explicit
Private Const MyName As String = "NestedSets"
Private Const errParentTable As String = "Parent Table in error."
Private Const errParentTableKey As String = "Specified 'node' field in
Parent Table has null and so can't be use for primary key."
Private Const errNoRoot As String = "The Parent table has no identifiable
root node; fix and submit again."
Private Const errNoUniqueRoot As String = "The Parent table has more than
one possible root; fix and submit again."
Private Const errCantCreate As String = "Cannot create the nested set table
("
Private Const errCantInsert As String = "Cannot insert the nodeID "
Private Const errUnknownParent As String = "At least one ParentID is unknown
as NodeID in the supplied table."
Private Const errUnusedRecords As String = "Not all the records from the
table have been used."
Private db As Database ' To avoid using CurrentDb each time
Private OpeningString As String ' string to open the recordset with all
children
Private InsertInto As String ' string to insert a record
Private Sub RaiseError(ByVal Desc As String, Optional ErrNumber As Long =
513)
Err.Raise vbObjectError + ErrNumber, MyName, Desc
End Sub
Public Sub FromNestedToParent(ByVal NestedTable As String, _
ByVal ParentTableName As String, _
ByVal NodeFieldName As String, _
ByVal ParentFieldName As String)
Dim db As Database: Set db = CurrentDb
On Error Resume Next
db.Execute "DROP TABLE " & ParentTableName
Err.Clear
db.Execute "SELECT c.NodeID as " & NodeFieldName & _
", p.NodeID As " & ParentFieldName & _
" INTO " & ParentTableName & _
" FROM " & NestedTable & " AS c LEFT JOIN " & NestedTable & " AS p "
& _
" ON (c.lft BETWEEN p.lft AND p.rgt) AND c.lvl = p.lvl+1 ",
dbFailOnError
If 0 <> Err.Number Then
RaiseError Err.Description, Err.Number
End If
Debug.Assert 0 = Err.Number
End Sub
Public Sub FromParentToNested(ByVal ParentTable As String, _
ByVal NodeID As String, _
ByVal ParentID As String, _
ByVal NestedSet As String)
Dim nCount As Long
' Check if the table exists, and if the fields NodeID and ParentID exist
On Error Resume Next
DCount "*", ParentTable, NodeID & "=" & ParentID
If 0 <> Err.Number Then
RaiseError errParentTable
Exit Sub
End If
' Check if there are NULL under the nodeID
If 0 <> DCount("*", ParentTable, NodeID & " IS NULL") Then
RaiseError errParentTableKey
Exit Sub
End If
Set db = CurrentDb
If 0 <> db.OpenRecordset("SELECT COUNT(*) FROM (SELECT * FROM " &
ParentTable & " AS a LEFT JOIN " & _
ParentTable & " AS b ON a." & ParentID & "= b." & NodeID & _
" WHERE (NOT a." & ParentID & " IS NULL) AND b." & NodeID & " IS
NULL)").Fields(0).Value Then
RaiseError errUnknownParent
Exit Sub
End If
' Create the nested set table. Its three fields are NodeID, lft and rgt.
db.Execute "DROP TABLE " & NestedSet: Err.Clear
' We tried to drop a table, maybe it was not there... not important...
db.Execute "CREATE TABLE " & NestedSet & _
"(NodeID LONG CONSTRAINT PrimaryKey PRIMARY KEY," & _
" lft LONG NOT NULL CONSTRAINT UniqueLft UNIQUE, " & _
" rgt LONG NOT NULL CONSTRAINT UniqueRgt UNIQUE, " & _
" lvl LONG NOT NULL ); "
'In theory, we can compute the level, lvl, with a query, but there
is
' nothing wrong in storing it in the table too.
If 0 <> Err.Number Then
RaiseError errCantCreate & Err.Description & ")."
Exit Sub
End If
' Find the root, the node with a Null as ParentID, or the one with
itself.
Dim root As Long
Select Case DCount("*", ParentTable, NodeID & "=" & ParentID)
Case 0
' There is no node where NodeID=ParentID... look for a Parent Is
Null
Select Case DCount("*", ParentTable, ParentID & " IS Null")
Case 0
' There is no node where Parent Is Null, ... error...
RaiseError errNoRoot
Exit Sub
Case 1
' there is just one such node, perfect...
root = DLookup(NodeID, ParentTable, ParentID & " IS NULL")
Case Else
' there is more than one node with a parent Is Null... what to
do?
RaiseError errNoUniqueRoot
Exit Sub
End Select
Case 1
' There is just one node where parentID=NodeID... what about
' a node with a NULL parent???
If 0 <> DCount("*", ParentTable, ParentID & " Is Null") Then
RaiseError errNoUniqueRoot
Exit Sub
End If
root = DLookup(NodeID, ParentTable, ParentID & "=" & NodeID)
Case Else
' We have more than one node with ParentID=NodeID, someone has to
fix it...
RaiseError errNoUniqueRoot
Exit Sub
End Select
If 0 <> Err.Number Then
RaiseError errCantInsert & root
Exit Sub
End If
' Prepare the recursion
InsertInto = "INSERT INTO " & NestedSet & "(NodeID, lft, rgt, lvl)
VALUES("
OpeningString = "SELECT " & NodeID & " FROM " & ParentTable & " WHERE "
& ParentID & "="
Dim counting As Long
counting = 2
'Make some nasty recursion about calling for each of the children
CallChildren root, counting, 2
' Append the root...
db.Execute InsertInto & root & ", 1, " & counting & ", 1 ); "
'Job is done... we can alter the rgt field so it doesn't accept NULLs
anymore
' but that is not 'strictly' required...
db.Execute "CREATE INDEX level ON " & NestedSet & "(lvl)"
If counting <> 2 * DCount("*", ParentTable) Then
RaiseError errUnusedRecords
Exit Sub
End If
If 0 <> Err.Number Then
RaiseError Err.Description, Err.Number
Exit Sub
End If
End Sub
Private Sub CallChildren(ByVal ParentNodeID As Long, ByRef counting As Long,
ByVal level As Long)
Dim rst As DAO.Recordset
Dim opening As Long ' the current worm counter, the lft value
' for a given node
On Error Resume Next
' Open a recordset will al the children of the given parent...
Set rst = db.OpenRecordset(OpeningString & ParentNodeID,
dbOpenForwardOnly, dbReadOnly)
' For each, remember the lft, call the children, then having the rgt
value, insert the record.
Do Until rst.EOF
opening = counting ' get a copy, that is our rgt value.
' we can't insert the whole record,now, since we ignore the rgt
value
' We need to increase the running worm counter...
counting = counting + 1
CallChildren rst.Fields(0).Value, counting, level + 1 ' recursive
call on all the actual children
db.Execute InsertInto & rst.Fields(0).Value & ", " & opening & ", "
& counting & ", " & level & ") ;"
' Increase the running worm counter
counting = counting + 1
rst.MoveNext
Loop
Debug.Assert 0 = Err.Number
End Sub
-----------------------------------
stickandrock said:
A nesting approach is going to be my method, just not sure how it should
be
designed, because I could have 1 to 100 levels of nesting.
Thanks,
Michel Walsh said:
If the number of nested levels is high or undefined, use a nested set
approach.
If the number of nested levels is determined to be small, such a no more
than 3 levels, then you can use outer joins.
SELECT a.[first], a.[second],
Nz(c.[second], Nz(b.[second], a.[second])) AS final
FROM (myTable AS a LEFT JOIN Table11 AS b ON a.[second]= b.[first])
LEFT JOIN Table11 AS c ON b.[second]= c.[first];
should do. The data you supplied has much more 'level', and using outer
joins may soon proved itself to be too time (and space) consuming.
Hoping it may help,
Vanderghast, Access MVP
stickandrock said:
Here is my dilema...
I have a table that has as three columns that has has one column of a
current value and another column with a succeeding value. There could
be
one
or 100 rows that have a series of these of these chains.
Example of Data
first second FinalValue
AA AB
AB 675
675 AD
AD AE
AE AF
AF AG
AG AH
AH AI
AI
BA BB
BB BC
BC BD
BD BE
BE BF
CA CB
CB NS1
Desired result
first second final
AA AB AI
AB 675 AI
675 AD AI
AD AE AI
AE AF AI
AF AG AI
AG AH AI
AH AI AI
AI AI
BA BB BF
BB BC BF
BC BD BF
BD BE BF
BE BF BF
CA CB NS1
CB NS1 NS1
I hope this makes sense. please ask in questions you may have.
