Click here to monitor SSC
SQLServerCentral is supported by Red Gate Software Ltd.
 
Log in  ::  Register  ::  Not logged in
 
 
 
        
Home       Members    Calendar    Who's On


Add to briefcase 12345»»»

Hierarchies in SQL Expand / Collapse
Author
Message
Posted Tuesday, January 27, 2009 10:14 PM


SSCoach

SSCoachSSCoachSSCoachSSCoachSSCoachSSCoachSSCoachSSCoachSSCoachSSCoachSSCoach

Group: General Forum Members
Last Login: Friday, June 27, 2014 12:43 PM
Points: 15,444, Visits: 9,596
Comments posted to this topic are about the item Hierarchies in SQL

- Gus "GSquared", RSVP, OODA, MAP, NMVP, FAQ, SAT, SQL, DNA, RNA, UOI, IOU, AM, PM, AD, BC, BCE, USA, UN, CF, ROFL, LOL, ETC
Property of The Thread

"Nobody knows the age of the human race, but everyone agrees it's old enough to know better." - Anon
Post #644681
Posted Wednesday, January 28, 2009 1:12 AM
SSC Veteran

SSC VeteranSSC VeteranSSC VeteranSSC VeteranSSC VeteranSSC VeteranSSC VeteranSSC Veteran

Group: General Forum Members
Last Login: Monday, April 1, 2013 10:44 PM
Points: 272, Visits: 143
For the sake of completeness, I'd mention another method to store hierarchies in the database - the path model which is similiar to the adjancey model, in that each node in the hierarchy contains information on its ancestor. However, in the path model, each node contains information on all its ancestors up to the root.

HierarchyID in SQL Server 2008 does exactly that, and has a very rich set of functions to query and manipulate the data.

Books Online article on HierarchyID here: http://technet.microsoft.com/en-us/library/bb677290.aspx
Post #644722
Posted Wednesday, January 28, 2009 5:33 AM


SSC-Dedicated

SSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-Dedicated

Group: General Forum Members
Last Login: Today @ 12:36 AM
Points: 36,995, Visits: 31,524
Nicely done, Gus. And, considering that the article is about a fix you made for an actual problem having to do with Adjacency and Nested Set methods, I don't have a problem with leaving out the Path method.

I almost wish I had some hierarchy problems so I could use your good method and, heh..., justify the need for 2k8.


--Jeff Moden
"RBAR is pronounced "ree-bar" and is a "Modenism" for "Row-By-Agonizing-Row".

First step towards the paradigm shift of writing Set Based code:
Stop thinking about what you want to do to a row... think, instead, of what you want to do to a column."

(play on words) "Just because you CAN do something in T-SQL, doesn't mean you SHOULDN'T." --22 Aug 2013

Helpful Links:
How to post code problems
How to post performance problems
Post #644806
Posted Wednesday, January 28, 2009 6:34 AM


SSCoach

SSCoachSSCoachSSCoachSSCoachSSCoachSSCoachSSCoachSSCoachSSCoachSSCoachSSCoach

Group: General Forum Members
Last Login: Friday, June 27, 2014 12:43 PM
Points: 15,444, Visits: 9,596
I've played with the SQL 2008 hierarchyID data type a little bit, but only a few minutes, and I've never used it in a production environment.

I have tested pre-2008 path-hierarchies, and found them to have all the negatives of denormalized data, and few of the positives. They are slower to update or query than adjacency, much slower to query than nested sets, and only slightly faster to update than nested sets. But that's basically because it's all string or XML functions. I'm not sure how performant the 2008 version is.

I'll see about getting a dev copy of 2008 this weekend (after payday), and see what I can do by way of speed tests.


- Gus "GSquared", RSVP, OODA, MAP, NMVP, FAQ, SAT, SQL, DNA, RNA, UOI, IOU, AM, PM, AD, BC, BCE, USA, UN, CF, ROFL, LOL, ETC
Property of The Thread

"Nobody knows the age of the human race, but everyone agrees it's old enough to know better." - Anon
Post #644853
Posted Wednesday, January 28, 2009 6:41 AM
Forum Newbie

Forum NewbieForum NewbieForum NewbieForum NewbieForum NewbieForum NewbieForum NewbieForum Newbie

Group: General Forum Members
Last Login: Tuesday, December 14, 2010 1:25 PM
Points: 1, Visits: 6
Or you could use CLR store procedures which are very fast in execution and sometimes are faster than T-SQL.
http://blog.vmladenov.com/?p=197
Post #644859
Posted Wednesday, January 28, 2009 6:45 AM
Grasshopper

GrasshopperGrasshopperGrasshopperGrasshopperGrasshopperGrasshopperGrasshopperGrasshopper

Group: General Forum Members
Last Login: 2 days ago @ 12:12 AM
Points: 22, Visits: 149
Having not known about your topic, I found other resources:
I needed a way to show a hierarchical structure and found a few informative sites:

* http://groups.google.com/group/borland.public.delphi.objectpascal/browse_thread/thread/8bd20a203e20eaa2
* http://www.delphi3000.com/articles/article_2740.asp?SK
* http://www.evolt.org/article/Four_ways_to_work_with_hierarchical_data/17/4047/index.html

And what most were saying, was the, Modified Preorder Tree Traversal Algorithm, was a preferred way of doing hierarchical sets.

This is the Create for the tables (I am using both MySQL version 5 and Elevate DB version 2)


--
-- Definition of table `tblcategories`
--
DROP TABLE IF EXISTS `tblcategories`;
CREATE TABLE `tblcategories` (
`idtblcategories` int(10) unsigned NOT NULL auto_increment,
`Description` varchar(45) NOT NULL,
`lft` int(10) unsigned NOT NULL,
`rgt` int(10) unsigned NOT NULL,
PRIMARY KEY USING BTREE (`idtblcategories`),
UNIQUE KEY `ndxDescription` (`Description`)
) ENGINE=InnoDB AUTO_INCREMENT=20 DEFAULT CHARSET=latin1;

-- some working records
/*!40000 ALTER TABLE `tblcategories` DISABLE KEYS */;
INSERT INTO `tblcategories` (`idtblcategories`,`Description`,`lft`,`rgt`) VALUES
(11,'Food',1,18),
(12,'Fruit',2,11),
(13,'Red',3,6),
(14,'Cherry',4,5),
(15,'Yellow',7,10),
(16,'Banana',8,9),
(17,'Meat',12,17),
(18,'Beef',13,14),
(19,'Pork',15,16);
/*!40000 ALTER TABLE `tblcategories` ENABLE KEYS */;


To add a new node, say at Yellow, first begin a transaction, then update the existing entries:
UPDATE tblcategories SET rgt = rgt + 2
WHERE rgt > 7;

UPDATE tblcategories SET lft = lft + 2
WHERE lft > 10;

Now, insert your row and commit:
INSERT INTO tblcategories VALUES ('New Node', 8, 9);

To remove a node, subtract instead of add 2 in the UPDDATE statement, then, delete your node.

Happy hierarchy.
Post #644867
Posted Wednesday, January 28, 2009 8:02 AM
Forum Newbie

Forum NewbieForum NewbieForum NewbieForum NewbieForum NewbieForum NewbieForum NewbieForum Newbie

Group: General Forum Members
Last Login: Friday, July 10, 2009 8:51 AM
Points: 3, Visits: 9
hi guys,

I am new to the forum, so I would like to say "hi" first :)

Now back onto the topic: I would be very interested in finding out the results of your comparison tests, GSquared.

I am not sure if you will agree with me, but there is also another factor when considering different solutions to a problem: simplicity. I am saying that as a tsql programmer - not a DBA.

Working with the built in hierarchyID data type would be much cleaner and easier to understand than complicated structures involving complicated logic to maintain them and that also means less errors in my application caused by people using it in a wrong way.

Thanks,
Lukasz
Post #644952
Posted Wednesday, January 28, 2009 8:15 AM
Grasshopper

GrasshopperGrasshopperGrasshopperGrasshopperGrasshopperGrasshopperGrasshopperGrasshopper

Group: General Forum Members
Last Login: 2 days ago @ 12:12 AM
Points: 22, Visits: 149
I just feel, to tie myself to a DB structure type, like you mentioned using the hierarchcical ID, might limit my application's portability - say, if I want to take it from MS SQL server to MySQL or Oracle or DB2.

Doing a small amount of coding in order to remain with ISO standard fields, is in my opinion, making for a far better application.

My 2cents.
Post #644961
Posted Wednesday, January 28, 2009 8:16 AM
SSCertifiable

SSCertifiableSSCertifiableSSCertifiableSSCertifiableSSCertifiableSSCertifiableSSCertifiableSSCertifiableSSCertifiable

Group: General Forum Members
Last Login: Tuesday, May 6, 2014 5:51 AM
Points: 6,266, Visits: 2,028
I liked the compromised you took when dealing with this problem.

I have worked in the past with these issues and my opinion is that it is the "usage" what dictates what's better.
- path-based hierarchies are *NOT* slow for many kind of queries but they *ARE* for some others.
- Nested-Sets are *NOT* good as you already pointed out for changes BUT also certain queries are "hard" to craft.
- The Built-in hierarchy-ID of 2008 is basically a path-based method that happens to be in binary representation and it has many (almost all) the drawbacks of the pre-2008 forms it just operates faster and it does not have as many limitations as a varchar column.

All in all I think you put together an interesting method.

Great work!



* Noel
Post #644962
Posted Wednesday, January 28, 2009 8:21 AM


SSCoach

SSCoachSSCoachSSCoachSSCoachSSCoachSSCoachSSCoachSSCoachSSCoachSSCoachSSCoach

Group: General Forum Members
Last Login: Friday, June 27, 2014 12:43 PM
Points: 15,444, Visits: 9,596
danielk1: yes, that's a "nested sets" hierarchy.

For something like your sample, it's definitely the way to go. It's not likely that "Meat" will ever be moved out of the "Food" category, or that "Beef" will ever move out of the "Meat" sub-category.

That works just fine for relatively static hierarchies. No problem.

The problem I had to solve was what to do with a volatile hierarchy. In this case, a customer-facing web page that had hierarchical access control.

Joe works for company X, and he places an order that will have details on this web page. Joe can see the details, as can various people at X. Simple hierarchy, right? Joe then changes to working with company Y, and now people at X should no longer see his details, but people at Y should. The following week, he moves to Z.

At the same time, Bob moves from Z to X, and Sue moves from A to Y, and B adds twelve new people who will all be placing orders and who weren't even in your database.

And that's a typical hour for this hierarchy.

It's no longer as simple as adding "yellow" by expanding the range for "food". Even that isn't as simple as you might think. What happens in your example if you already have a category "dinnerware" that starts at 19? How do you then add "Vegetable" to "Food"? You can't add 2 to "Food", because now you're going to end up with an overlap with "Dinnerware", which is, of course, wrong. So, you have to redefine "Dinnerware", and everything in it, in order to add "Vegetable" to "Food". Let's say you have to do that kind of thing several times per minute. You need to add "Vegetable" and twenty items in it. At the same time, you need to add four new types of "Meat", six new "Fruit", two more types of "Apple" (under "Fruit"). Also, you're changing who you buy your dinnerware from, and they have different product IDs for plates, cups, glasses, silverware, etc., so you basically have to double the size of that category, but "Dinnerware" has a range that ends at 26 and "Furniture" starts at 27. Suddenly, you have to manage updates that affect nearly every row in your table. The complexity of the update is huge.

There are a number of solutions for this. You could add room to each category you add, based on anticipated growth over a reasonable time span. Instead of defining "Food" as 1-12, you define it as 1-1000, even though you only need 1-12 when you first build it. But does "Fruit" get 2-500, or 2-100, or 2-20, in that scheme? Managing the data ranges becomes something that requires a lot more work.

A path or adjacency hierarchy handles that kind of situation very, very easily. Want to add a new sub-set to "Food"? Easy, add one row, and its ParentID = "Food". You're done. No other rows to do anything with at all. Now you need to add 100 items under "Dinnerware"? Again, it's a single transaction that simply adds 100 rows to the table, each with the correct ParentID. Milliseconds later, you have your hierarchy fully functional.

In other words, there's more to it than what your sample code does. A lot more.


- Gus "GSquared", RSVP, OODA, MAP, NMVP, FAQ, SAT, SQL, DNA, RNA, UOI, IOU, AM, PM, AD, BC, BCE, USA, UN, CF, ROFL, LOL, ETC
Property of The Thread

"Nobody knows the age of the human race, but everyone agrees it's old enough to know better." - Anon
Post #644968
« Prev Topic | Next Topic »

Add to briefcase 12345»»»

Permissions Expand / Collapse