BOM, with Joe Celko Nested Sets
Jennifer Alden
I've got an Inventory DB that makes heavy use of Bill of Materials - type
architecture. I was looking through Dev Ashish's site and found a posting
called "BOM, with Joe Celko Nested Sets" - the example is for Access 2000,
and I've got 97, so I can't open it.
I looked around "SQL for Smarties" and through the archives of this group,
but couldn't find anything...can anyone point me to a link for more info?
I'm using recordsets for everything now and it is S-L-O-W.
Thanks for any help.
-Jennifer Alden.
-----= Posted via Newsfeeds.Com, Uncensored Usenet News =-----
http://www.newsfeeds.com - The #1 Newsgroup Service in the World!
-----== Over 80,000 Newsgroups - 16 Different Servers! =-----
Dev Ashish
Jet 4. Try using Robin's method for A97.
< http://www.mvps.org/access/modules/mdl0027.htm >
-- Dev
"Jennifer Alden" <JenA...@mermaidz.com> wrote in message
news:38b42...@news5.newsfeeds.com...
: Hi all -
George Shears
Jennifer Alden wrote in message <38b42...@news5.newsfeeds.com>...
>Hi all -
>
>I've got an Inventory DB that makes heavy use of Bill of Materials - type
>architecture. I was looking through Dev Ashish's site and found a posting
>called "BOM, with Joe Celko Nested Sets" - the example is for Access 2000,
>and I've got 97, so I can't open it.
>
>I looked around "SQL for Smarties" and through the archives of this group,
>but couldn't find anything...can anyone point me to a link for more info?
>I'm using recordsets for everything now and it is S-L-O-W.
>
>Thanks for any help.
>
> -Jennifer Alden.
>
I think you pretty much need to stick with Recordsets in A97. Following is
some code that, I think, gives fairly good performance. Not so much an
example of "good" Bill Of materials code as a couple of concepts I was
playing with. What got the biggest performance gain was moving the Database
Object and a Couple of the Recordset Objects to Globals and, in the one case
in the addPartLinkage() function, using rst.Clone rather than opening a new
recordset at every level. It could be made faster by using the Seek method
rather than FindFirst method but it would take some doing with Linked Tables
and the way I use .Clone.
The code builds a temporary table (mine was very special purpose, details
not important) from:
table Parts (Partname, PartID)
and
table PartLinks (ParentPartID, ChildPartID)
Code follows....
George Shears
Option Compare Database
Option Explicit
' --- Cheap hack to avoid testing for infinite recursion in this module.
' --- Assume that if level exceeds MAX_RECURSION_LEVEL
' --- we have it. Final code could do an actual test (performance??).
' --- The form interface tests each addition for self reference
' --- so this is, basically, a back-up strategy
Const MAX_RECURSION_LEVEL = 100
' --- some globals mostly for performance
Dim G_SEQUENCE As Long
Dim G_DB As Database
Dim G_LINK_RST As Recordset
Dim G_TEMP_RST As Recordset
Sub BuildPartLinkageTable()
Dim rst As Recordset
Dim strSQL
'--- Initialize Variables
'--- Keeps a Sequence For the Resulting Temp table
G_SEQUENCE = 0
'--- Initialize a Global Database Object
Set G_DB = CurrentDb()
'--- Clear temp table
G_DB.Execute "DELETE * FROM tempPartLinkage;"
'--- Open the Global Recordsets To be Used
Set G_LINK_RST = G_DB.OpenRecordset("PartLinks", dbOpenDynaset)
Set G_TEMP_RST = G_DB.OpenRecordset("tempPartLinkage", dbOpenDynaset)
'--- Open a local recordset (parts with No Parents)
strSQL = ""
strSQL = strSQL + "SELECT * FROM Parts "
strSQL = strSQL + "LEFT JOIN PartLinks "
strSQL = strSQL + "ON Parts.PartID = PartLinks.ChildPartID "
strSQL = strSQL + "WHERE (((PartLinks.ParentPartID) Is Null))"
Set rst = G_DB.OpenRecordset(strSQL, dbOpenDynaset)
'--- Loop Through No-Parent Parts and Add Linkage Info
While Not rst.EOF
AddPartLinkage rst!PartID, 1
rst.MoveNext
Wend
'--- Free/Clear Variables
G_LINK_RST.Close
G_TEMP_RST.Close
rst.Close
Set G_LINK_RST = Nothing
Set G_TEMP_RST = Nothing
Set rst = Nothing
Set G_DB = Nothing
End Sub
Sub AddPartLinkage(ID As Long, Level As Integer)
Dim rst As Recordset
Dim NextID As Long
G_SEQUENCE = G_SEQUENCE + 1
G_TEMP_RST.AddNew
G_TEMP_RST!LinkSequence = G_SEQUENCE
G_TEMP_RST!UsageLevel = Level
G_TEMP_RST!PartID = ID
G_TEMP_RST.Update
Set rst = G_LINK_RST.Clone
rst.FindFirst "ParentPartID = " & ID
While Not rst.NoMatch
If Level < MAX_RECURSION_LEVEL Then
AddPartLinkage rst!ChildPartID, Level + 1
End If
rst.FindNext "ParentPartID = " & ID
Wend
rst.Close
Set rst = Nothing
End Sub
sky...@my-deja.com
The retrieval queries are usable SQL in A97. The hard part is setting
up the left and right pointers, which requires code.
- Steve
In article <5WZs4.14824$tk7.8...@bgtnsc05-news.ops.worldnet.att.net>,
"Dev Ashish" <d...@nomail.please> wrote:
> Jennifer, I'm pretty sure the db uses SQL syntax which is only
supported by
> Jet 4. Try using Robin's method for A97.
>
> < http://www.mvps.org/access/modules/mdl0027.htm >
>
> -- Dev
>
> "Jennifer Alden" <JenA...@mermaidz.com> wrote in message
> news:38b42...@news5.newsfeeds.com...
> : Hi all -
> :
> : I've got an Inventory DB that makes heavy use of Bill of Materials -
type
> : architecture. I was looking through Dev Ashish's site and found a
posting
> : called "BOM, with Joe Celko Nested Sets" - the example is for
Access 2000,
> : and I've got 97, so I can't open it.
> :
> : I looked around "SQL for Smarties" and through the archives of this
group,
> : but couldn't find anything...can anyone point me to a link for more
info?
> : I'm using recordsets for everything now and it is S-L-O-W.
> :
> : Thanks for any help.
> :
> : -Jennifer Alden.
> :
> :
> :
> :
> :
> : -----= Posted via Newsfeeds.Com, Uncensored Usenet News =-----
> : http://www.newsfeeds.com - The #1 Newsgroup Service in the World!
> : -----== Over 80,000 Newsgroups - 16 Different Servers! =-----
>
>
Sent via Deja.com http://www.deja.com/
Before you buy.
joe_...@my-deja.com
>> I looked around "SQL for Smarties" and through the archives of this
group, but couldn't find anything...can anyone point me to a link for
more info? <<
Try Amazon.com -- it is a book!
Another way of representing trees is to show them as nested sets.
Since SQL is a set oriented language, this is a better model than the
usual adjacency list approach you see in most text books. Let us
define a simple Personnel table like this, ignoring the left (lft) and
right (rgt) columns for now.
This problem is always given with a column for the employee and one for
his boss in the textbooks:
CREATE TABLE Personnel
(emp CHAR(10) PRIMARY KEY,
boss CHAR(10), -- this column is unneeded & denormalizes the
table
salary DECIMAL(6,2) NOT NULL,
lft INTEGER NOT NULL,
rgt INTEGER NOT NULL);
Personnel
emp boss salary lft rgt
===================================
Albert NULL 1000.00 1 12
Bert Albert 900.00 2 3
Chuck Albert 900.00 4 11
Donna Chuck 800.00 5 6
Eddie Chuck 700.00 7 8
Fred Chuck 600.00 9 10
which would look like this as a directed graph:
Albert (1,12)
/ \
/ \
Bert (2,3) Chuck (4,11)
/ | \
/ | \
/ | \
/ | \
Donna (5,6) Eddie (7,8) Fred (9,10)
This (without the lft and rgt columns) is called the adjacency list
model, after the graph theory technique of the same name; the pairs of
nodes are adjacent to each other. The problem with the adjacency list
model is that the boss and employee columns are the same kind of thing
(i.e. names of personnel), and therefore should be shown in only one
column in a normalized table. To prove that this is not normalized,
assume that "Chuck" changes his name to "Charles"; you have to change
his name in both columns and several places. The defining
characteristic of a normalized table is that you have one fact, one
place, one time.
To show a tree as nested sets, replace the nodes with ovals, then nest
subordinate ovals inside each other. The root will be the largest oval
and will contain every other node. The leaf nodes will be the
innermost ovals with nothing else inside them and the nesting will show
the hierarchical relationship. The rgt and lft columns (I cannot use
the reserved words LEFT and RIGHT in SQL) are what shows the nesting.
If that mental model does not work, then imagine a little worm crawling
anti-clockwise along the tree. Every time he gets to the left or right
side of a node, he numbers it. The worm stops when he gets all the way
around the tree and back to the top.
This is a natural way to model a parts explosion, since a final
assembly is made of physically nested assemblies that final break down
into separate parts.
At this point, the boss column is both redundant and denormalized, so
it can be dropped. Also, note that the tree structure can be kept in
one table and all the information about a node can be put in a second
table and they can be joined on employee number for queries.
To convert the graph into a nested sets model think of a little worm
crawling along the tree. The worm starts at the top, the root, makes a
complete trip around the tree. When he comes to a node, he puts a
number in the cell on the side that he is visiting and increments his
counter. Each node will get two numbers, one of the right side and one
for the left. Computer Science majors will recognize this as a
modified preorder tree traversal algorithm. Finally, drop the unneeded
Personnel.boss column which used to represent the edges of a graph.
This has some predictable results that we can use for building
queries. The root is always (left = 1, right = 2 * (SELECT COUNT(*)
FROM TreeTable)); leaf nodes always have (left + 1 = right); subtrees
are defined by the BETWEEN predicate; etc. Here are two common queries
which can be used to build others:
1. An employee and all their Supervisors, no matter how deep the tree.
SELECT P2.*
FROM Personnel AS P1, Personnel AS P2
WHERE P1.lft BETWEEN P2.lft AND P2.rgt
AND P1.emp = :myemployee;
2. The employee and all subordinates. There is a nice symmetry here.
SELECT P2.*
FROM Personnel AS P1, Personnel AS P2
WHERE P1.lft BETWEEN P2.lft AND P2.rgt
AND P2.emp = :myemployee;
3. Add a GROUP BY and aggregate functions to these basic queries and
you have hierarchical reports. For example, the total salaries which
each employee controls:
SELECT P2.emp, SUM(P1.salary)
FROM Personnel AS P1, Personnel AS P2
WHERE P1.lft BETWEEN P2.lft AND P2.rgt
GROUP BY P2.emp;
4. Finding all leaf nodes is trivial:
SELECT P1.*
FROM Personnel AS P1
WHERE rgt = lft - 1;
This will be two to three orders of magnitude faster than the adjacency
list model.
For details, see the chapter in my book SQL FOR SMARTIES (second
editon) by Joe Celko, Morgan-Kaufmann, 1995, ISBN 1-55860-323-9 or my
columns in DBMS magazine in 1996 March, April, May and June issues. I
went into details as to how to manipulate this model.
--CELKO--
Robin Stoddart-Stones
>This problem is always given with a column for the employee and one for
>his boss in the textbooks:
>
> CREATE TABLE Personnel
> (emp CHAR(10) PRIMARY KEY,
> boss CHAR(10), -- this column is unneeded & denormalizes the
>table
> salary DECIMAL(6,2) NOT NULL,
> lft INTEGER NOT NULL,
> rgt INTEGER NOT NULL);
>
But then any reference to the personality involved should be instantly
recognised as redundant by a simple system analysis.
The fact is that in a project or merit-oriented company both emp and
boss are entirely irrelevant to the diagram, which is task or
organisationally oriented. Fundamentally this means that EMP CANNOT
BE A PRIMARY KEY, since it is entirely possible for one person to hold
two positions in the diagram.
If, for example, this is used as a responsibility breakdown of tasks
in a project a person may be responsible not only for the overall
task of the project, but may head up a team responsible for part of
the project.
In a current situation, the Head of the Undercarriage Team reports to
the Head of the Fuselage Integration. Coincidentally the same person
holds both jobs, expressed as wearing 'different hats') At progress
meetings, his senior assistant formally presents the report of the
undercarriage team to the Fuselage integration team, in the absence of
his boss, who happens to be chairing the meeting.
This may sound a bit bizarre, but when an avoidable error by the
undercarriage team was announced, the chair reamed out the
undercarriage team, ( effectively himself) in the same way that he
dealt with errors from other departments, which made for good
management.
However the point is, If emp is a primary key of the responsibility
table, th same person cannot hold more than one position and you are
going back to the pre-Handy model of authority. ( A common but
backward step.)
The other problem with the model as shown is the rigidity / or
requirement for recalculation for every new addition or deletion.
Either the model is complete and requires no recalculation or every
change requires the complete recalculation of the entire tree. In a
large structure this may involve millions of actions. You have to
balance the speed and convenience of the SQL method against the
convenience and frequency of change.
Having said that, I still find the method elegant.
Have fun
Robin
joe_...@my-deja.com
>> Fundamentally this means that EMP CANNOT BE A PRIMARY KEY, since it
is entirely possible for one person to hold two positions in the
diagram. <<
When I do nested set modeling "for real" instead for a quick email
posting, I have an organizational chart table and a Personnel table, so
I can show that the position "Grand Poobah" is either held by someone
from the Personnel table or vacant (NULL), and that one person can wear
more than one hat in the organization. There are also a lot of
deferrable constraitns I skip over for the short posting.
>> This may sound a bit bizarre, but when an avoidable error by the
undercarriage team was announced, the chair reamed out the
undercarriage team, (effectively himself) in the same way that he
dealt with errors from other departments, which made for good
management. <<
I like that! It is good managment and you do not see enough of it.
>> The other problem with the model as shown is the rigidity / or
requirement for recalculation for every new addition or deletion.
Either the model is complete and requires no recalculation or every
change requires the complete recalculation of the entire tree. In a
large structure this may involve millions of actions. You have to
balance the speed and convenience of the SQL method against the
convenience and frequency of change. <<
This is not the problem that people think it is. The OrgChart table is
two integers and a foreign key, which makes it pretty small. It fits
into a few pages of main storage for most applications, so structural
updates are fast. Secondly, personnel change more often than
organizational charts, even in today's business world. On average half
the rows in OrgChart are changed with each insertion. But it does not
matter if the insertion is one node or a whole new subtree.
You can also put UPDATE, INSERT and DELETE triggers on the table to
close up or create gaps in the (lft, rgt) pairs, so you will never see
it in your code.
Keri Hardwick
blatantly bad design - so that your method is "right" - is incredibly
self-serving and ridiculous.
The correct table definition is
EmpId PK
Name
BossId
If Chuck (EmpId = 5) changes to Charles, you make the change on record 5.
No other records are changed, as no other record is dependent upon the
attributes of the record with Id=5. BossId is simply a foreign key; it's
just a foreign key to the same table.
And furthermore, to give such a half-assed description of your premise and
then to say "go buy my book if you want to see how it really works" is even
more offensive.
I realize the poster asked for your book, and this certainly wasn't "spam" -
but it seems a simple link to it on Amazon would have been much more classy.
And, it may have inspired my interest in purchasing it, whereas your post
destroyed any such interest.
Keri Hardwick
<joe_...@my-deja.com> wrote in message news:89k4h0$ard$1...@nnrp1.deja.com...
<snip>
<snip>
joe_...@my-deja.com
>> If Chuck (EmpId = 5) changes to Charles, you make the change on
record 5. No other records are changed, as no other record is dependent
upon the attributes of the record with Id=5. BossId is simply a
foreign key; it's just a foreign key to the same table. <<
There are no records in SQL; they are rows which are not the same
thing. Yes, you can set up cascaded updates in DRI on the table
itself, which only hides the multiple updates. That one fact is
changed in multiple places. The real problem with the adjacency list
model is that it does not represent a heirarchical relationship.
Delete Chuck from the table and you lose the fact that Albert is still
the boss of Donna, Eddie and Fred. The first rule of a relationals
database is that all relationships are shown as values in columns of
tables.
>> And furthermore, to give such a half-assed description of your
premise and then to say "go buy my book if you want to see how it
really works" is even more offensive. <<
Gee, did you expect me to pull 8000 words into an email instead? Would
you have been less offended by "I know and I am not going to tell you"
as a reply?
>> I realize the poster asked for your book, and this certainly wasn't
"spam" - but it seems a simple link to it on Amazon would have been
much more classy. And, it may have inspired my interest in purchasing
it, whereas your post destroyed any such interest. <<
Actually, I consider posting links to my book at Amazon to be more self-
serving -- that is like saying "I am not going to help you unless you
pay $45 for the answer" as opposed to saying "Here is some help for
now, and where you can get the full monty, if you need it".
Keri Hardwick
you assume if a node is missing (vacant position) the next higher position
automatically assumes supervisor responsibility? That's a business rule,
and not one that is automatic. It is especially problematic in a part bill
of material situation.
Look, I was probably overly harsh in my words regarding your intentions, for
which I apologize. While I don't think you gave a working example in your
post, you do, so I guess that should eliminate my perception of "ulterior
motives" on your part.
I think we just have some fundamental disagreements on BOM/hierarchy; let's
just leave it at that.
Keri
<joe_...@my-deja.com> wrote in message news:89sife$7h5$1...@nnrp1.deja.com...
Larry Linson
> There are no records in SQL; they are rows which are not the same
> thing. Yes, you can set up cascaded updates in DRI on the table
> itself, which only hides the multiple updates. That one fact is
> changed in multiple places. The real problem with the adjacency list
> model is that it does not represent a heirarchical relationship.
> Delete Chuck from the table and you lose the fact that Albert is
still
> the boss of Donna, Eddie and Fred. The first rule of a relationals
> database is that all relationships are shown as values in columns of
> tables.
Careful, Joe. There are many names for the same thing, depending on
your point of view.
If you happen to be viewing RDB from Access (and this discussion is,
after all, in an Access newsgroup, and it wouldn't be out of line to do
so), Tables contain Records (Rows) and Records contain Fields
(Columns); viewing from other RDBMS, Tables contain Rows and Columns;
but, on the other hand, if you happen to be viewing it from the
Relational Model itself, then Relations contain Tuples and Tuples have
Attributes.
So, I would say, "Yes, there are records in SQL. Yes, they are the same
thing as Rows." I might also add, "They are Access' implementation of
Tuples." I might also agree, "There are things in computerdom called
Records which are not the same as Rows in Tables." On the other hand,
if you want to argue that Access isn't truly a relational database, I'd
ask you, "Which database _IS_?". Last I heard there was no
implementation that complied with all the current 300-plus rules Ed
Codd (and others, perhaps?) came up with.
Arguing terminology often implies that you have a rather narrow point
of view, or simply that you're being picky to prove your point; I doubt
that either is the case with you and doubt that you would want to leave
that impression.
--
L. M. (Larry) Linson
Access example databases at http://homestead.deja.com/user.accdevel
New: Book reviews, previously published in North Texas PC News
Script execution must be enabled and Windows set to Small Fonts
Albert Marshall
>Delete Chuck from the table and you lose the fact that Albert is still
>the boss of Donna, Eddie and Fred.
Now let's get something straight here! I don't care about all the
theoretical points being bandied about, but I still haven't had a pay
rise for having all these people working for me.
--
Albert Marshall
Visual Solutions
England
Dave
> assembly is made of physically nested assemblies that final break down
> into separate parts.
This set technique is pretty slick, but I'm curious as to if this idea can
be extended to model collections of trees (forests? sparsely connected
networks?) such as those created by the inclusion of a single part number
into many different BOMs that each have different top level numbers. Being
able to do a parts explosion on a system that uses a separate BOM table to
handle the situation where, for example, a particular piece of hardware,
like a screw, is used in multiple assemblies using only a single query would
be a pretty neat trick ;)
Possible?
Robin Stoddart-Stones
plentiful.
However, the problem is not a single component, like a screw, but when
an assembly, such as a fastening (nut,bolt,washer) is used multiple
times. As far as I can see the 'Celko' technique relies on being able
to identify all the components within the span. Thus the need for a
'fastening' falls within the primary span, but the components of the
fastening fall outside the span.
Therefore you have to identify all the components of any assembly,
rather than building a unit from assemblies, which is a bit limiting
as most things are built from repeating modules. It's not so much a
tree system, more modelling the forest.
There is a database system used for project management (Artemis) that
allows dynamic linking, each record in your master recordset, is
connected to a single record 'linker'. This can then be linked back to
your master set, such that a changing value in the linker creates a
whole new 'temporary' recordset of related values.
However I cannot create an SQL that updates the link set automatically
and then repeatedly runs an SQL for those new values. May be someone
else can think of devious wording.
( I came across an SQL that took the contents of your larder and then
looked through the recipe book and told you what you could make.
However it did not seem to see if you could create filo pastry and had
steak and pate then you could make beef wellington unless the BW
recipe contained the filo pastry components..... same problem,
different context)
Have Fun
Robin
On Wed, 22 Mar 2000 06:39:26 GMT, "Dave" <da...@nospam.com> wrote:
>> This is a natural way to model a parts explosion, since a final
>> assembly is made of physically nested assemblies that final break down
>> into separate parts.
>
Dave
> an assembly, such as a fastening (nut,bolt,washer) is used multiple
> times. As far as I can see the 'Celko' technique relies on being able
> to identify all the components within the span. Thus the need for a
> 'fastening' falls within the primary span, but the components of the
> fastening fall outside the span.
Your point about having to materialize the entire span ahead of time is true
enough, but I think there *would* be a problem with including a single
component into multiple assemblies if you only had Joe's scheme a single
item master table - try it ;)
If a part is included in two trees, once the L&R values are set for its
position in the first tree, how can it be placed into a second?
The other really weird thing is that Joe seems to believe that the 'normal'
reflexive relationship somehow violates 2NF, and that his scheme does not.
Just the opposite is true. Without going into a lot of mumbo jumbo, Joe's
scheme requires fixups to other records during insertion and deletion
operations (the L&R fields), the reflexive model does not. The *only* reason
that you ever *have to* touch other records during insertion, deletion, and
updates of *non-primary key* fields is that you are not 2NF - simple as that
(obviously if you *want to* journal transactions to maintain history in
another table, that's a different story) The other 'hidden' entity that
screaming to get out of the employee table is the tree entity itself.
The example about how changing the bosses name requires a change to the
employee records linked to it and how this 'proves' the table isn't
normalized is pretty far out there. You have to change the names in two
places because you selected a poor primary key for the table Joe.
(1) neither salary, nor a person's supervisor depends upon that person's
name (functional dependence of non-primes on primary doesn't exist)
(2) the full functional dependence rule only applies to non-prime
attributes - it should be obvious why that is the case. If you change the
value of a primary key, you have to change all the foreign key field values
to maintain the relationship - regardless of the level of normalization. If
you hadn't picked the name to be the primary key, the boss *could* change
his name without affecting the relationship. Try using an 'informationless'
primary key, and you'll see this reflexive relationship does not violate
2NF - record insert, delete and update (of non-primes) operations do not
require any fix ups to any other records - ever.
Your storage method always does during insert and delete - but I still think
it's a pretty slick hack ;)
Now let's see the version that does BOMs!