select parent?

#11

On 29 June, 15:53, Willem Bogaerts <w.bogae... (AT) kratz (DOT) nl> wrote:

Quote:

SELECT * FROM TableName WHERE Parent LIKE '%/34/%';

OK as long as there aren't too many entries I guess.

#12

"Peter H. Coffin" <hellsop (AT) ninehells (DOT) com> wrote

Quote:

On Tue, 29 Jun 2010 14:35:17 +0100, Brian Cryer wrote:
"lallous" <lallous (AT) lgwm (DOT) org> wrote in message
news:09dad895-95dc-4bfd-8810-2c0c5ec16075 (AT) w12g2000yqj (DOT) googlegroups.com...
Hello,

I have the following table:

id=int
pid=int
name=varchar(100)

It will hold tree items where 'pid' is the parent id. If zero then the
item belongs to the root and has no parents.

Suppose I have this structure:

[dir] -> pid=0, id=1
dir\f1 -> id=2, pid=1
dir\[dir2] -> id = 3, pid=1
dir\dir2\f2 -> id=4, pid=3

Is there is a nice way to directly figure out the root's id given the
record with id=4 ?

So I want to tell what is the root parent of itemid=4 (the answer is
id=1).

Unless you know the depth in advance I don't think you can generate a
single
SQL statement which will do it for you. I think you will need to fall
back
to a programming language (PHP, Delphi, Java, .NET - whatever you feel
most
at home with) and do it using that - basically a simple loop reading a
record and looping until the record doesn't have a parent.

Stored procedures can recurse. At least as of version 5 point
*mumble*...

Yes. Point taken, I should have included a stored procedure solution in my
list. In fact, YES, a stored procedure solution should be faster than a
client side (PHP/Delphi/etc) solution and would therefore be the better
solution.

BTW the solution doesn't have to be recursive, an itterative solution would
be just as viable.
--
Brian Cryer
http://www.cryer.co.uk/brian

#13

"Captain Paralytic" <paul_lautman (AT) yahoo (DOT) com> wrote

Quote:

On 29 June, 15:53, Willem Bogaerts <w.bogae... (AT) kratz (DOT) nl> wrote:
SELECT * FROM TableName WHERE Parent LIKE '%/34/%';

OK as long as there aren't too many entries I guess.

Meaning that if there are lots of entries in your table then performance
will suck because it involves a full table scan rather than making use of
any indexes.
--
Brian Cryer
http://www.cryer.co.uk/brian

#14

On 29 June, 16:56, "Brian Cryer" <not.here@localhost> wrote:

Quote:

"Captain Paralytic" <paul_laut... (AT) yahoo (DOT) com> wrote in message

news:2e0cc35a-a083-4a9f-a716-c656a301e18f (AT) y11g2000yqm (DOT) googlegroups.com...

On 29 June, 15:53, Willem Bogaerts <w.bogae... (AT) kratz (DOT) nl> wrote:
SELECT * FROM TableName WHERE Parent LIKE '%/34/%';

OK as long as there aren't too many entries I guess.

Meaning that if there are lots of entries in your table then performance
will suck because it involves a full table scan rather than making use of
any indexes.
Spot on

#15

On 2010-06-29 16:53, Willem Bogaerts wrote:

Quote:

@Willem: so what exactly you mean by path strings?you store the
complete path in each node?

I have defined a "parent" field as VARCHAR DEFAULT '/'. Any top-level
object (that means object with no parent) will have '/' as its path. For
any parent, I prepend a slash and the parent's ID value. So if the
parent field holds "/2/34/", it has a top-level object with ID#2 and a
direct parent with ID#34. You can search on any subtree with a
LIKE-query. For instance, if the example object wants to find other
objects in the same subtree, it can be done with:

Willem, do you store only two nodes in the parent column, root and
direct parent, regardless of which depth the node is located at?

/Lennart

#16

Willem Bogaerts wrote:

Quote:

@Willem: so what exactly you mean by path strings?you store the
complete path in each node?

I have defined a "parent" field as VARCHAR DEFAULT '/'. Any top-level
object (that means object with no parent) will have '/' as its path. For
any parent, I prepend a slash and the parent's ID value. So if the
parent field holds "/2/34/", it has a top-level object with ID#2 and a
direct parent with ID#34. You can search on any subtree with a
LIKE-query. For instance, if the example object wants to find other
objects in the same subtree, it can be done with:

SELECT * FROM TableName WHERE Parent LIKE '%/34/%';

Best regards,

The problem with that is - what happens if you need to change the parent
of #34 from #2 to #5? Now everything below #34 is incorrect.

Not a real good design (and violates normalization rules).

--
==================
Remove the "x" from my email address
Jerry Stuckle
JDS Computer Training Corp.
jstucklex (AT) attglobal (DOT) net
==================

#17

Quote:

Willem, do you store only two nodes in the parent column, root and
direct parent, regardless of which depth the node is located at?

No, I store the entire path from the root to the record itself.

Best regards,
--
Willem Bogaerts

Application smith
Kratz B.V.
http://www.kratz.nl/

#18

Quote:

SELECT * FROM TableName WHERE Parent LIKE '%/34/%';

The problem with that is - what happens if you need to change the parent
of #34 from #2 to #5? Now everything below #34 is incorrect.

I do this with an UPDATE statement that replaces all occurrences of
'/2/' with '/5/'. But that is the short-sighted answer. The program
itself gives the user the possibility to either take an entity out of
the chain or move an entire subtree.

Quote:

Not a real good design (and violates normalization rules).

No disagreement on that. But at least it works. I started with a
ParentId field, then tried the left-right approach (subtree entry index
and subtree exit index) and hit myself hard. The path string works for
my purposes.

One of the advantages of the path string over the left-right method is
that the only affected records are the ones you expect to be affected.
Adding an element to a subtree in the left-right method alters not only
the exit index of the subtree itself, but also the entry _and_ exit
index of all subtrees that come after it. So for each operation, a large
part of the table must be locked, and all entry- and exitvalues must be
updated in your application before a store can be done. It's not nice in
a multi-user application that everything affects everything else.

Best regards,
--
Willem Bogaerts

Application smith
Kratz B.V.
http://www.kratz.nl/

#19

Willem Bogaerts wrote:

Quote:

SELECT * FROM TableName WHERE Parent LIKE '%/34/%';

The problem with that is - what happens if you need to change the parent
of #34 from #2 to #5? Now everything below #34 is incorrect.

I do this with an UPDATE statement that replaces all occurrences of
'/2/' with '/5/'. But that is the short-sighted answer. The program
itself gives the user the possibility to either take an entity out of
the chain or move an entire subtree.

Which depends on proper execution of the client to maintain database
integrity.

Quote:

Not a real good design (and violates normalization rules).

No disagreement on that. But at least it works. I started with a
ParentId field, then tried the left-right approach (subtree entry index
and subtree exit index) and hit myself hard. The path string works for
my purposes.

As long as it works for you. But there are better ways.

Quote:

One of the advantages of the path string over the left-right method is
that the only affected records are the ones you expect to be affected.
Adding an element to a subtree in the left-right method alters not only
the exit index of the subtree itself, but also the entry _and_ exit
index of all subtrees that come after it. So for each operation, a large
part of the table must be locked, and all entry- and exitvalues must be
updated in your application before a store can be done. It's not nice in
a multi-user application that everything affects everything else.

Best regards,

Personally, I don't like the subtree approach myself, mainly because of
the locking. So when I need something like for large tables, I use DB2
- it supports recursive SQL. Oracle and SQL Server also work fine.
Haven't checked out if PostGresSQL does or not.

But a SP works fine for relatively small tables.

--
==================
Remove the "x" from my email address
Jerry Stuckle
JDS Computer Training Corp.
jstucklex (AT) attglobal (DOT) net
==================

#20

On 2010-06-30 09:48, Willem Bogaerts wrote:

Quote:

Willem, do you store only two nodes in the parent column, root and
direct parent, regardless of which depth the node is located at?

No, I store the entire path from the root to the record itself.

Just a thought, since you then know (or can know) the "path" from root
to the node under investigation, it is likely to be more efficient to
change the query:

SELECT * FROM TableName WHERE Parent LIKE '%/34/%';

to:

SELECT * FROM TableName WHERE Parent LIKE '/2/34/%';

/Lennart