RE: [agileDatabases] deep object inheritance mapping in relational database
Please find below some advice from a known expert, which arrived on another
mailing list I had forwarded your message to.
---------- Forwarded message ----------
From: Paul Dorsey <pdorsey@...>
Date: Oct 25, 2007 1:58 PM
Subject: RE: [agileDatabases] deep object inheritance mapping in relational
To: Multiple recipients of list ODTUG-SQLPLUS-L <ODTUG-SQLPLUS-L@...
You can post this back to the thread if you want:
We implemented this in BRIM in the following way:
1) We draw the inheritance path as you would expect, with each node as a
concrete class connected using generalization.
2) We generate a table for each class with all the attribs including the
3) Place views on each of the tables that the UI will actually access
4) Use instead of triggers on the views to cascade the updates down the tree
when updates are applied. The entire logical object has to be locked prior
to the updates being applied so it is a 2 step process.
Note that NO logic is in the middle tier.
We rejected collapsing everything into a single table because people might
have very large trees and you would effectively have a stuff table to hold
all primary objects.
The cascade is only a single update statement to each table so is very fast.
Even if the tree gets to be 10 high (the largest you will ever see in
nature, you might have up to 10 updates stmts. But volitility in upper
parts of the tree tends to be rare in practice so this algorithm seems to be
robust across all projects where we have used this construct.
The only place where this might not work well is if you are doing batch
processing of thousands of records that are each requiring updates high in
the tree. Then you would take a significant performance hit.
> -----Original Message-------
> From: ml-errors@... [mailto:ml-errors@...] On
> Behalf Of Gabriel Tanase
> Sent: Wednesday, October 24, 2007 11:41 PM
> To: Multiple recipients of list ODTUG-SQLPLUS-L
> Subject: Fwd: [agileDatabases] deep object inheritance
> mapping in relational database
> I guess you might find this interesting. You may follow the
> thread from
> the Yahoo Groups.
> Apologies if you receive this multiple times.
> Best regards,
> ---------- Forwarded message ----------
> Date: Oct 23, 2007 5:43 PM
> To: agileDatabases@yahoogroups.com
> I found the article
> very useful regarding mapping object inheritance in
> relational databases. however my application is a bit
> different. in my application, the data is in hierarchical
> format like tree view. there are around 30k nodes in the tree
> where each node has a type and set of attributes and has one
> or more parent nodes. child nodes inherit the attributes of
> the parent. leaf node will have around 30 attributes which
> include both direct and inherited attributes. this can be
> modelled using the generic technique described in the
> article. however there are some issues. when the user clicks
> on a node on the screen, we need to display the direct plus
> all the inherited attributes for that node right upto the
> root node. this is not very easy because we need to walk up
> the tree finding the parent nodes in the path and collecting
> all the attributes. I would like to know if there is an easy
> way out for this. if we store the direct and inherited
> attributes against each node, then if the user updates an
> attribute value, we need to update all the copies and also it
> introduces data redundancy. we also want to have denormalized
> tables for the purpose of reporting. how can we have a
> parallel denormalized schema for node inheritance. should we
> store all the direct and inherited attributes for each node
> in denormalized schema. this can be done, but if user makes a
> change to a node attribute, we need to find all the impacted
> nodes in the tree and update all the copies of this attribute
> in reporting tables. this is problem of denormalization of
> inheritance. but if it is denormalized, then the node
> attribute retrieval performance will suffer. on top of this
> some of the attribute values come from static data, so we
> need to store a reference to static data for each attribute
> and also we need to store historical versions for each node
> and their attributes. but this is a different issue and can
> be discussed in another post.
> Please let me know if you have any suggestions to solve this
> inheritance problem. I have designed the data model, but not
> sure about how it will perform.
For more information on this topic or to become a member, visit our web site
at http://www.ODTUG.com Be sure to check out our Seriously Practical (SP)
Conferences coming up this year!
ODTUG is pleased to announce that Kaleidoscope 2008 will be held at The New
Orleans Sheraton from June 15-19. Keep checking www.ODTUG.com for more
Author: Paul Dorsey
Fat City Hosting, San Diego, California -- http://www.fatcity.com
To REMOVE yourself from this mailing list, send an E-Mail message
to: ListGuru@... (note EXACT spelling of 'ListGuru') and in
the message BODY, include a line containing: UNSUB ODTUG-SQLPLUS-L
(or the name of mailing list you want to be removed from). You may
also send the HELP command for other information (like subscribing).
[Non-text portions of this message have been removed]
- You should take into account any expected update behaviour around the
parent nodes. Is an attribute change somewhere up in the tree a
relatively infrequent event? Or is this happening all the time instead?
If it's infrequent, then I would prefer to propagate the update to all
child notes immediately during the update of the parent (within the same
transaction, actually). When changes are frequent, then the cost of
recursive updates may be too high and you may as well wait until the
'current values' for a child node are asked for and pull the data from
the nearest parent that has a value.
--- In agileDatabases@yahoogroups.com, "rk_poojari" <rk_poojari@...>
> as I said before, this idea is simple and great!! this table will
> also be useful to retrieve the hierarchy for a particular node
> excluding other nodes not part of this hierarchy.
> BUT I think there is still a small issue here. may be I forgot to
> mention that, user can choose to override the value of the parent
> node attribute at a child node level. in that case, while retrieving
> all the inherited attributes for a node , we need to get the
> overridden value if there is any from the parent nodes rather than
> the original value. the value can be overidden by any number of child
> nodes under a parent and any node under the node where the attribute
> is overridden will use the new value.
> to implement this behaviour, I think we can add an extra column
> called "depth" in transitive closures table and then start collecting
> the attributes from bottom to top of the tree. this is not as easy as
> it was before, but still better than querying the normalized
> hierarchy table which stores only two columns nodeid and parentnodeid
> without any redundant data.
> --- In agileDatabases@yahoogroups.com, "Johan Stuyts" j.stuyts@
> > > when the user clicks on a node on the screen, we need to
> > > display the direct plus all the inherited attributes for that
> > > node right upto the root node. this is not very easy because
> > > we need to walk up the tree finding the parent nodes in the
> > > path and collecting all the attributes. I would like to know
> > > if there is an easy way out for this. if we store the direct
> > > and inherited attributes against each node, then if the user
> > > updates an attribute value, we need to update all the copies
> > > and also it introduces data redundancy.
> > I am assuming you are modeling inheritance in the database instead
> > storing inheritance in the model in the database.
> > I guess this is the classic storage-of-trees-in-SQL problem. The
> > way to solve this is by adding redundant data to your database. One
> > technique I found useful is storing the transitive closure of the
> > ancestors of a node. So if you have a node table like this:
> > node_id, parent_id, <other columns>
> > You add another table which stores the transitive closure. The
> > key is the combination of the two columns. Always create an index
> on the
> > first column, and if you need to find all descendants of a node,
> > create an index on the second column:
> > node_id, ancestor_id
> > Given the following node tree:
> > 1
> > +--2
> > | +--3
> > +--4
> > The table containing the transitive closures will contain the
> > data. It is important that you include the node itself in the
> > closure:
> > 1, 1
> > 2, 1
> > 2, 2
> > 3, 1
> > 3, 2
> > 3, 3
> > 4, 1
> > 4, 4
> > If you need inherited information you start the query on the table
> > containing the transitive closures and join the information you
> > select
> > ...
> > from
> > transitive_closure tc
> > left join
> > node n
> > on tc.ancestor_id = n.node_id
> > where
> > tc.node_id = <ID of the node you are interested in>
> > ...
> > In your case you probably also have to join the table containing the
> > attributes, because, if I understand correctly, these are stored in
> > another table than the node table.
> > Kind regards,
> > Johan Stuyts
- --- Ramakrishna Pujari <rk_poojari@...> wrote:
> sorry for some misleading information. actually inI'd be tempted not to worry about that for now.
> the current application I am working on, the node
> has only one parent. but we wanted to give room for
> more than one parent, so we tried to have a separate
> table to store parent child node relationships just
> in case the business requirement changes to attach a
> node to more than one parent in future. thanks.
What's the advantage of over-engineering the solution?
You run the risk of over complicating things today to
solve a problem you may never run into. Why not
simply wait until you need a more complex solution and
then build it at that point?
Scott W. Ambler
Practice Leader Agile Development, IBM Methods Group
Agility at Scale: http://www.ibm.com/rational/agile/
Be smarter than spam. See how smart SpamGuard is at giving junk email the boot with the All-new Yahoo! Mail at http://mrd.mail.yahoo.com/try_beta?.intl=ca
> BUT I think there is still a small issue here. may be II might have missed the overriding bit, but the solution you propose
> forgot to mention that, user can choose to override the value
> of the parent node attribute at a child node level. in that
> case, while retrieving all the inherited attributes for a
> node , we need to get the overridden value if there is any
> from the parent nodes rather than the original value. the
> value can be overidden by any number of child nodes under a
> parent and any node under the node where the attribute is
> overridden will use the new value.
> to implement this behaviour, I think we can add an extra
> column called "depth" in transitive closures table and then
> start collecting the attributes from bottom to top of the
> tree. this is not as easy as it was before, but still better
> than querying the normalized hierarchy table which stores
> only two columns nodeid and parentnodeid without any redundant data.
will work fine. It's even possible that it allows filtering of the
attributes in the database using 'group by' and 'having'. I am always a
bit confused when I have to use those, but it should be along the lines
group by <attribute identifier column>
having max(tc.depth) = tc.depth