The following table exists:

Container-Containing

The table is trying to show that container 1 contains container 2. Container 2 then goes on to contain containers 3 and 4, etc...

Now let's say that you wanted to query all the subcontainers of 1...i.e. when the input is 1, you get back not only 2, but 3 and 4 as well.

This relationship can extend deeper than one level, as well.

How can this be done in SQL?

recursion is defined in SQL3

but of course, it matters not what the standard says, it matters only what your particular database system supports

you can do this easily in DB2 and Oracle (both of which supported recursion before SQL3)

in other database systems, it is not possible -- at least, not with that data model, called the adjacency model

do a search for nested set model for another approach

I don't even know if those'd be possible because in this model, a child can have many parents and a parent can have many children...

In MySQL, since it doesn't support what you mentioned, would it be possible to use stored procedures to execute the query above?

the example you showed looked like a hierarchy (each child can have only one parent)

for a many-to-many parent-child relationship, you're in even deeper water

you can use stored procs in mysql 5+ but that would not help you, you would only be doing "recursion with mirrors" -- running queries in a loop until they return no more data, with all the inefficiency that running queries in a loop entails

vk101

1 In most Bill of Materials/Assembly-Component models (thousands have been implemented in SQL2), you do need an associative table in the pure sense, you can do recursion BUT:
- only one direction (up xor down) at a time
- you have to do it in a loop, or if you have a serious commercial SQL engine, you can do it in a single stored procedure that calls itself (recursion)
- there is no penalty or overhead for loops/recursion in compiled code (there is for “new” code you throw at the server every time, but even then the additional overhead for the loop is not significant).

1.1 Certainly a Container (parent) can hold many Containers (children) but I do not believe that a specific Container can actually be in many Containers, therefore a child cannot have many parents. This is a hierarchy, not strictly a many-to-many. You may have lead Rudy astray. Pls confirm.

If you can truly have a specific Container located in many (other) specific Containers, then you have not finalised the identity of the element you are tracking (see 3 & 4 below).

2 If it is a hierarchy/BOM/A-C requirement, the following should do:

Container Table
ContainerId (PK)

Content Table
ParentId=Parent.ContainerId (FK)
ChildId=Child.ContainerId (FK)
[ParentId+ChildId (PK)]

This allows for:
- a containing-Container [Assembly, Parent] to have many contained-Containers [Components, Children], and
- a contained-Container [Component, Child] to be contained in many containing-Containers [Assemblies, Parents]
(they just cannot be the same, otherwise you will get an infinite loop)

3 What does an atomic Container (lowest level) contain ? It cannot be a Container. A Product ?

4 Are you managing Products (which Container is a certain Product located in ?) or Containers (now which Container did I put that Container in ?)

Cheers

1. Btw, what is compiled code? Not too sure...

1.1. I mean a many-to-many hierarchy. A child can have many parents, and a parent can have many children.

2. That's the kind of associative table I imagine would be relevant to this scenario.

3. Yes, the lowest level Container would contain Products. (I use the term Container and Contained in an abstract sense to help me see how to solve problems like this.)

4. Managing Containers, where for a given container I'd like to know all the contained elements under that container and all sub-containers.

You submit source code (human readable computer language like SQL or java) to a complier; which produced compiled code (minimum requirement to run other software [eg. SQL engine]) also called object code; you submit a bunch of objects plus class libraries, etc to a linker which produces machine code (also called binaries) which runs the machine. In (eg) Sybase, which compiles your SQL before it can execute it, it goes through a fair amount of resource allocation. Compiled code (eg which already exists if you created a stored proc) runs 10 to 100 times faster than new (source) SQL that you throw at the server. in such compiled SQL, loop overheads are not significant or measureable; in new code they may be significant.

Ok, but given your answer (3), you do have an associative table (in the relational sense), but you do have a clean hierarchy (of data). therefore my post 5 item (2) has the correct table defn. Your requirement can be serviced with recursion (recursive SQL to go up/down a level in the hierarchy).

As I thought.

No worries, this will do it.

Recursion should be avoided in SQL for hierarchical relationships. It is not efficient, and may be constrained by nesting level limits.
Here is an article I wrote on a simple and efficient(fast) method of returing recursive data. Note that it required only one execution per level, rather than one per item as a recursive routine would require:
------------------------------------------------------------------------
The most flexible and robust method of storing hierarchical data in a database is to use a table with a recursive relationship. In this design, each record has an associated parent record ID that indicates its relative place in the hierarchy. Here is an example:

CREATE TABLE [YourTable]
([RecordID] [int] IDENTITY (1, 1) NOT NULL ,
[ParentID] [int] NULL)

The challenge is to find a way to return all the child records and descendants for any given parent record.

While recursion is supported within SQL Server, it is limited to 32 nested levels and it tends to be ineffecient because it does not take full advantage of SQL Server's set-based operations.

A better algorithm is a method I call the "Accumulator Table".

In this method, a temporary table is declared that accumulates the result set. The table is seeded with the initial key of the parent record, and then a loop is entered which inserts the immediate descendants of all the records accumulated so far which have not already been added to the table.

Here is some skeleton code to show how it works:

--This variable will hold the parent record ID who's children we want to find.
declare @RecordID int
set @RecordID = 13

--This table will accumulate our output set.
declare @RecordList table (RecordID int)

--Seed the table with the @RecordID value, assuming it exists in the database.
insert into @RecordList (RecordID)
select RecordID
from YourTable
where YourTable.RecordID = @RecordID

--Add new child records until exhausted.
while @@RowCount > 0
insert into @RecordList (RecordID)
select YourTable.RecordID
from YourTable
inner join @RecordList RecordList on YourTable.ParentID = RecordList.RecordID
where not exists (select * from @RecordList CurrentRecords where CurrentRecords.RecordID = YourTable.RecordID)

--Return the result set
select RecordID
from @RecordList

This method is both flexible and efficient, and the concept is adaptable to other hierarchical data challenges.

For a completely different method of storing and manipulating hierarchical data, check out Celko's Nested Set model, which stores relationships as loops of records.

http://www.intelligententerprise.com...stid=145525%5D
-------------------------------------------------------------------

vk101

I do not believe in cross-posting (http://www.dbforums.com/showthread.p...79#post6225479 post 11). But some may think that Blindman's comments (post 8) applies to my post, so I will limit my responses (this post) to his comments that may or may not apply to my proposal (post 5)

1 My experience is limited to the managing hierarchies which I have implemented as true associative tables (many-to-many, with the restrictions as per post 5), in the following real world relational databases. All Sybase and one MicroStuffed, all tens of millions of rows with a strict response time requirement:
- Bill of Materials (manufacturing, several, as this is a well-established method)
- Genealogy (two plus one free)
- Ancestry/Progeny (Horses, this has since been implemented for dogs as well)
- Securities (hierarchy of stock ownership, this runs over 16 billion rows)

2 All require traversing the tree/hierarchy in both directions:
- what is the progeny(children[grandchildren[great-grandchildren]] ) of this row
- what are the parents[grandparents[great-grandparents]] of this row).
The system (db design) must not impose a limit in levels, and it does not in terms of storage. However, in terms of program execution, which is where recursion and therefore the nesting level, is relevant, the limit of 16 and now 32 is far more than the real application needs. This is why I was so intent on making the distinction (in post 5) re theoretical associative tables (no limits) and hierarchies, before I said the proposed design works for vk101's requirement.

3 For recursive queries, Sybase has no additional "overhead", MicroStuffed did not when I implemented it, when anything over 11 level of nesting sent it into the Great Void, but who knows what the codeline of the server is doing this year.

4 My recursive SQL code handles an entire level (not one row) of the hierarchy, either up or down, in each iteration, but uses a temp table. I have another, older, stored proc that executes once for each branch in the tree (for which there are children/parent) and does not use a temp table. Each has dis/advantages depending on the app requirements. The second is slower but more sociable on the server.

Cheers

Blindman

1 I can see that your table stores children of a parent (progeny, containing-containers). Where do you store the parents of a child (ancestry, contained-containers), as required in the initial post ?

2 Is Celko's method implemented in production anywhere ?

Cheers

Ten characters for good measure

You mean the OP's second post, right?
The article was written for the more common standard binary tree, but there is nothing preventing the same algorithm being used on an incestual many-to-many relationship. I'd be curious about the OP's data and whether he allows or prevents circular relationships.

No, I am not personnally familiar with any applied instances of the nested set model, though persons employing it occasionally pop on the forum with questions.

I would like to see skeleton code for your algorithm.

Blindman

I mean vk101's progressed requirement up to post 8, the point at which you presented a proposal, which I was questioning the completeness of, in post 10.

Okay, so that means in order to fill vk101's [progressed] requirement, your proposal would need to be enhanced to:
- either provide an additional table (for Children)
- or amend the proposed table which stores Parent/Child (to store Child/Parent as well).
The latter case is an ordinary many-to-many Associative table, your resulting table is exactly the same as mine (post 5), after you introduce a role name (to distinguish the otherwise duplicate FK column name). It would appear that we agree that the data should be stored as a recursive tree, and that this is:

Quote:

The most flexible and robust method of storing hierarchical data in a database

Container Table
ContainerId (PK)

Content Table (Given the progression/qualification I would now call this BillOfMaterial)
ParentId=Parent.ContainerId (FK)
ChildId=Child.ContainerId (FK)
[ParentId+ChildId=(PK)] (Eliminates dupes but not incest)

I would emphasise the distinction that many-to-many is not necesarily incestuous; circular relations is incestuous.

I think I presented a couple of qualifications (post 5) which vk101 confirmed (post 6), which means the progressed requirement and the proposal in post 5 apply to:
- pure hierarchy or pure tree (any n tree; a binary tree is only true for upward natural [parent] relationships, and not for Containers, etc)
- no incest
- no circular relations
Which means it is a natural structure or hierarchy (found in Nature). Which means recursion will work. If these qualifying questions were answered in the negative, then vk101's [progressed] requirement, my proposal including the recursion, would not have worked. Hence my insistence on the qualifications, before I categorically stated that it worked (post 7).

If this were a helpdesk I'd just give you the answer and close the ticket, but as it is a forum that tries to delve deeper into the particular subject, I invite you to delve.

Hint
In other threads in this forum, it is established that most posters & repondents automatically design/code from a row-processing (Procedural, pre-Relational) mindset, and are not familiar with the set-processing (Client-Server, Relational) paradigm. If you write a sproc that:
- takes the input parameters of PersonId (ContainerId, HorseId), LevelNumber (initially zero), Direction {Up|Down}
- the first execution creates a temp table
- each [iterative] execution handles the entire set of a LevelNumber at a time, populating the temp table as it goes
it can be called iteratively (checking for a max nesting level), which will produce a recursive traversal of the tree. I think your code as described, plus set-procesing (thus handling an entire level/set instead of one row), plus tightening-up so that it can be called iteratively would do just fine.

Cheers

Could you describe what you mean by set processing as opposed to row processing?

I'm also unsure of what is meant by LevelNumber. I assume it means the level in the hierarchy (i.e. the top parent would have a LevelNumber of 0 or 1, and every level would go down from there). Is this a concept that would manifest itself as a column, or simply something to be considered when writing the recursive stored procedure?

When you talk about specifying a Direction in the stored procedure of either up or down, is either procedure so similar that it could be done through specifying a parameter like that, or are the procedures different enough that one would have a both a findParents and findChildren procedure? (In which case the Direction parameter would be used to call whichever of these two was specified in the Direction flag.)

Thanks.