Listing parent ids

Listing parent ids

am 27.07.2011 18:03:51 von Arno Kuhl

Not strictly a php issue but it's for a php app, hope that counts (plus I
haven't had much joy googling this)

I have a table with an id and a parentid.
If it's a top-level record the parentid is 0, otherwise it points to another
record, and if that record isn't a top-level record its parentid points to
another record, etc (a linked list).

Is there a single select that will return the complete list of parentids?
Or do I have to iterate selecting each parent record while parentid > 0 and
build the list entry by entry?

TIA
Cheers, Arno


--
PHP Database Mailing List (http://www.php.net/)
To unsubscribe, visit: http://www.php.net/unsub.php

RE: Listing parent ids

am 28.07.2011 11:39:56 von Arno Kuhl

Arno Kuhl wrote:
> Not strictly a php issue but it's for a php app, hope that counts
> (plus I haven't had much joy googling this)
>
> I have a table with an id and a parentid.
> If it's a top-level record the parentid is 0, otherwise it points to
> another record, and if that record isn't a top-level record its
> parentid points to another record, etc (a linked list).
>
> Is there a single select that will return the complete list of parentids?
> Or do I have to iterate selecting each parent record while parentid>
> 0 and build the list entry by entry?

Little difficult to answer what you don't say what you are using as a
database.
Recursive queries are now possible on many databases, except I think for
MySQL.
I run this type of query all the time on Firebird and Postgres now supports
the same CTE functions.

--
Lester Caine - G8HFL
-----------------------------


I'm currently using MySQL but I'll switch databases if there's a compelling
reason and no drawbacks.
Thanks for the lead, I'm googling recursive queries.

Cheers
Arno


--
PHP Database Mailing List (http://www.php.net/)
To unsubscribe, visit: http://www.php.net/unsub.php

Re: Listing parent ids

am 28.07.2011 12:09:39 von Richard Quadling

On 28 July 2011 10:39, Arno Kuhl wrote:
> Arno Kuhl wrote:
>> Not strictly a php issue but it's for a php app, hope that counts
>> (plus I haven't had much joy googling this)
>>
>> I have a table with an id and a parentid.
>> If it's a top-level record the parentid is 0, otherwise it points to
>> another record, and if that record isn't a top-level record its
>> parentid points to another record, etc (a linked list).
>>
>> Is there a single select that will return the complete list of parentids?
>> Or do I have to iterate selecting each parent record while parentid>
>> 0 and build the list entry by entry?
>
> Little difficult to answer what you don't say what you are using as a
> database.
> Recursive queries are now possible on many databases, except I think for
> MySQL.
> I run this type of query all the time on Firebird and Postgres now supports
> the same CTE functions.
>
> --
> Lester Caine - G8HFL
> -----------------------------
>
>
> I'm currently using MySQL but I'll switch databases if there's a compelling
> reason and no drawbacks.
> Thanks for the lead, I'm googling recursive queries.
>
> Cheers
> Arno
>
>
> --
> PHP Database Mailing List (http://www.php.net/)
> To unsubscribe, visit: http://www.php.net/unsub.php
>
>

I would take a long hard read of this article
http://web.archive.org/web/20100105135622/http://dev.mysql.c om/tech-resources/articles/hierarchical-data.html

I can't find it anywhere else now - it used to be on the mysql site -
but gone since Oracle has it and I can't find it in Google Cache.

But, it explains the pros and cons of using the Adjacency List Model
vs the Nested Set Model.

The article is quite old (the copyright on the page is 2008, but I've
no idea when it was actually created) and so, there are advances in
SQL features (CTE's being one of them) which aren't mentioned.

But, I've found Nested Sets to be much easier for me to work with,
allowing me to provide quite complex searching based upon an n-level
tree.

How you visualise the data won't change. It is still, visually at
least, a set of parent/child relationships, but to build a tree, you
don't need to use recursion. In most cases, a single query will be
enough to interact with the tree at any level, in any direction, for
more or less any purpose.


I recently bought "Joe Celkos SQL for Smarties: Advanced SQL
Programming" on eBay. It covers a LOT more about Nested Sets.
(http://desc.shop.ebay.co.uk/i.html?_nkw=Celkos+SQL+Smarties &_sacat=0&_dmpt=Non_Fiction&_odkw=Celkos+SQL+Smarties&_osaca t=0&_trksid=p3286.c0.m270.l1313&LH_TitleDesc=1
currently showing 2 entries) and a fourth edition on Amazon
(http://www.amazon.com/Joe-Celkos-SQL-Smarties-Fourth/dp/012 3820227/ref=sr_1_1?ie=UTF8&qid=1311847652&sr=8-1)



--
Richard Quadling
Twitter : EE : Zend : PHPDoc
@RQuadling : e-e.com/M_248814.html : bit.ly/9O8vFY : bit.ly/lFnVea

--
PHP Database Mailing List (http://www.php.net/)
To unsubscribe, visit: http://www.php.net/unsub.php

Re: Listing parent ids

am 28.07.2011 12:16:23 von Richard Quadling

And http://www.amazon.co.uk/exec/obidos/ASIN/1558609202/onlinepr icecouk


--
Richard Quadling
Twitter : EE : Zend : PHPDoc
@RQuadling : e-e.com/M_248814.html : bit.ly/9O8vFY : bit.ly/lFnVea

--
PHP Database Mailing List (http://www.php.net/)
To unsubscribe, visit: http://www.php.net/unsub.php

Re: Listing parent ids

am 28.07.2011 12:28:03 von Lester Caine

Arno Kuhl wrote:
> I'm currently using MySQL but I'll switch databases if there's a compelling
> reason and no drawbacks.
> Thanks for the lead, I'm googling recursive queries.

'common table expression' is the thing to google for, but MSDN seem to have
hijacked all the top spots.
http://syntaxhelp.com/SQLServer/Recursive_CTE is a nice example of what you
outlined ...

--
Lester Caine - G8HFL
-----------------------------
Contact - http://lsces.co.uk/wiki/?page=contact
L.S.Caine Electronic Services - http://lsces.co.uk
EnquirySolve - http://enquirysolve.com/
Model Engineers Digital Workshop - http://medw.co.uk//
Firebird - http://www.firebirdsql.org/index.php

--
PHP Database Mailing List (http://www.php.net/)
To unsubscribe, visit: http://www.php.net/unsub.php

RE: Listing parent ids

am 28.07.2011 13:30:28 von Arno Kuhl

On 28 July 2011 10:39, Arno Kuhl wrote:
> Arno Kuhl wrote:
>> Not strictly a php issue but it's for a php app, hope that counts
>> (plus I haven't had much joy googling this)
>>
>> I have a table with an id and a parentid.
>> If it's a top-level record the parentid is 0, otherwise it points to
>> another record, and if that record isn't a top-level record its
>> parentid points to another record, etc (a linked list).
>>
>> Is there a single select that will return the complete list of parentids?
>> Or do I have to iterate selecting each parent record while parentid>
>> 0 and build the list entry by entry?
>
> Little difficult to answer what you don't say what you are using as a
> database.
> Recursive queries are now possible on many databases, except I think
> for MySQL.
> I run this type of query all the time on Firebird and Postgres now
> supports the same CTE functions.
>
> Lester Caine - G8HFL
> -----------------------------
>
> I'm currently using MySQL but I'll switch databases if there's a
> compelling reason and no drawbacks.
> Thanks for the lead, I'm googling recursive queries.
>
> Arno
> --

I would take a long hard read of this article
http://web.archive.org/web/20100105135622/http://dev.mysql.c om/tech-resource
s/articles/hierarchical-data.html

I can't find it anywhere else now - it used to be on the mysql site - but
gone since Oracle has it and I can't find it in Google Cache.

But, it explains the pros and cons of using the Adjacency List Model vs the
Nested Set Model.

The article is quite old (the copyright on the page is 2008, but I've no
idea when it was actually created) and so, there are advances in SQL
features (CTE's being one of them) which aren't mentioned.

But, I've found Nested Sets to be much easier for me to work with, allowing
me to provide quite complex searching based upon an n-level tree.

How you visualise the data won't change. It is still, visually at least, a
set of parent/child relationships, but to build a tree, you don't need to
use recursion. In most cases, a single query will be enough to interact with
the tree at any level, in any direction, for more or less any purpose.

Richard Quadling
--

Thanks Richard. Your reference is exactly what I was looking for.
I'm just busy reading a sitepoint article about adjacent lists vs the
niftily titled "modified preorder tree traversal model".
http://www.sitepoint.com/hierarchical-data-database/ (really old - 2003)
I found I'm using the adjacent list model at the moment (didn't know it had
a name, I always thought of it as a type of linked list).
The "modified preorder tree traversal model" in the sitepoint article
appears to be equivalent to the "nested set model" in the mysql article.
It seems simple enough to implement, I'll definitely give it a closer look
and do some tests.

Thanks, it's great to hear the experiences of others who've used this.

Cheers
Arno


--
PHP Database Mailing List (http://www.php.net/)
To unsubscribe, visit: http://www.php.net/unsub.php

Re: Listing parent ids

am 28.07.2011 13:46:41 von Richard Quadling

On 28 July 2011 12:30, Arno Kuhl wrote:
> On 28 July 2011 10:39, Arno Kuhl wrote:
>> Arno Kuhl wrote:
>>> Not strictly a php issue but it's for a php app, hope that counts
>>> (plus I haven't had much joy googling this)
>>>
>>> I have a table with an id and a parentid.
>>> If it's a top-level record the parentid is 0, otherwise it points to
>>> another record, and if that record isn't a top-level record its
>>> parentid points to another record, etc (a linked list).
>>>
>>> Is there a single select that will return the complete list of parentid=
s?
>>> Or do I have to iterate selecting each parent record while parentid>
>>> 0 and build the list entry by entry?
>>
>> Little difficult to answer what you don't say what you are using as a
>> database.
>> Recursive queries are now possible on many databases, except I think
>> for MySQL.
>> I run this type of query all the time on Firebird and Postgres now
>> supports the same CTE functions.
>>
>> Lester Caine - G8HFL
>> -----------------------------
>>
>> I'm currently using MySQL but I'll switch databases if there's a
>> compelling reason and no drawbacks.
>> Thanks for the lead, I'm googling recursive queries.
>>
>> Arno
>> --
>
> I would take a long hard read of this article
> http://web.archive.org/web/20100105135622/http://dev.mysql.c om/tech-resou=
rce
> s/articles/hierarchical-data.html
>
> I can't find it anywhere else now - it used to be on the mysql site - but
> gone since Oracle has it and I can't find it in Google Cache.
>
> But, it explains the pros and cons of using the Adjacency List Model vs t=
he
> Nested Set Model.
>
> The article is quite old (the copyright on the page is 2008, but I've no
> idea when it was actually created) and so, there are advances in SQL
> features (CTE's being one of them) which aren't mentioned.
>
> But, I've found Nested Sets to be much easier for me to work with, allowi=
ng
> me to provide quite complex searching based upon an n-level tree.
>
> How you visualise the data won't change. It is still, visually at least, =
a
> set of parent/child relationships, but to build a tree, you don't need to
> use recursion. In most cases, a single query will be enough to interact w=
ith
> the tree at any level, in any direction, for more or less any purpose.
>
> Richard Quadling
> --
>
> Thanks Richard. Your reference is exactly what I was looking for.
> I'm just busy reading a sitepoint article about adjacent lists vs the
> niftily titled "modified preorder tree traversal model".
> http://www.sitepoint.com/hierarchical-data-database/   (really old -=
2003)
> I found I'm using the adjacent list model at the moment (didn't know it h=
ad
> a name, I always thought of it as a type of linked list).
> The "modified preorder tree traversal model" in the sitepoint article
> appears to be equivalent to the "nested set model" in the mysql article.
> It seems simple enough to implement, I'll definitely give it a closer loo=
k
> and do some tests.
>
> Thanks, it's great to hear the experiences of others who've used this.
>
> Cheers
> Arno
>
>
> --
> PHP Database Mailing List (http://www.php.net/)
> To unsubscribe, visit: http://www.php.net/unsub.php
>
>

In my day job, I process a LOT of data (MS SQL Server, 15 or so DBs,
maybe 250GB of data, at least 15 years of trends,etc.).

So I have a LOT of trees. Customer hierarchies (Customer Head Office,
Regional Office, Branch), Location hierarchies (Continent, Country,
Region, City, Street), Product hierarchies. BOM, etc.

When it comes to analysis, I can ask questions like "Which European
Customers have, overall, increased their turnover by at least 20% in
the last 6 months for a single product type?"

Because of the nested sets, I know that "European" means a left/right
of 23 to 224. Any customer branch with a location id in that range is
eligible for inclusion. No recursion of finding the European ID and
then chugging through all the IDs down to the street level to match
that ID to the customer.

And then realising that not all the customers are tagged at street
level, but maybe just at the city level.


It allows faster grouping and drilldown in my mind as the data is
always filtered for the required set in question.

And if you are filtering over multiple sets (location, date, product
category), you are going to get to the results a LOT faster than with
the easier understood, but not as useful (IMHO) adjacent list.

Richard.


--=20
Richard Quadling
Twitter : EE : Zend : PHPDoc
@RQuadling : e-e.com/M_248814.html : bit.ly/9O8vFY : bit.ly/lFnVea

--
PHP Database Mailing List (http://www.php.net/)
To unsubscribe, visit: http://www.php.net/unsub.php

RE: Listing parent ids

am 28.07.2011 13:49:26 von Arno Kuhl

> I'm currently using MySQL but I'll switch databases if there's a
> compelling reason and no drawbacks.
> Thanks for the lead, I'm googling recursive queries.

'common table expression' is the thing to google for, but MSDN seem to have
hijacked all the top spots.
http://syntaxhelp.com/SQLServer/Recursive_CTE is a nice example of what you
outlined ...

--
Lester Caine - G8HFL
-----------------------------

Thanks Lester. The data structure is a good example of what I outlined.
I want to avoid the recursion, whether in php or sql, possibly by using the
nested set model.

Cheers
Arno


--
PHP Database Mailing List (http://www.php.net/)
To unsubscribe, visit: http://www.php.net/unsub.php

Re: Listing parent ids

am 28.07.2011 14:24:55 von Jim Giner

""Arno Kuhl"" wrote in message
news:487F03135D2B452B89F22C95E278C7D4@point01...
>
> I have a table with an id and a parentid.
> If it's a top-level record the parentid is 0, otherwise it points to
> another
> record, and if that record isn't a top-level record its parentid points to
> another record, etc (a linked list).
>
> Is there a single select that will return the complete list of parentids?

You say you have a parentid and an id - ie, two specific fields in your
records. You say that you want to query all the parentids. Nobody else has
said this, but why not just

Select unique ids where parentid=0 ? That gives you (as you say) all your
top-level records, which are the parents of everything, no? Or are you
looking for each id that is itself a parent to something else? If the
latter, then why not
select unique parentid where parentid <> 0 ?



--
PHP Database Mailing List (http://www.php.net/)
To unsubscribe, visit: http://www.php.net/unsub.php

RE: Re: Listing parent ids

am 28.07.2011 15:09:19 von Arno Kuhl

>
> I have a table with an id and a parentid.
> If it's a top-level record the parentid is 0, otherwise it points to
> another record, and if that record isn't a top-level record its
> parentid points to another record, etc (a linked list).
>
> Is there a single select that will return the complete list of parentids?

You say you have a parentid and an id - ie, two specific fields in your
records. You say that you want to query all the parentids. Nobody else has
said this, but why not just

Select unique ids where parentid=0 ? That gives you (as you say) all your
top-level records, which are the parents of everything, no? Or are you
looking for each id that is itself a parent to something else? If the
latter, then why not
select unique parentid where parentid <> 0 ?

--

Hi Jim. I wanted the list of related parentids from current id to top-level
(parentid=0).
That could be 0 or more results, regardless of how many non-zero parentids
there are in total.
Currently I get this from selecting id=parentid while parentid>0, ie
recursively select each record going up the tree to the top level.
The nested set model apparently can return the entire hierarchical list from
the current node to the top level with a single select, but I haven't run
any tests yet on my specific data.

Cheers
Arno


--
PHP Database Mailing List (http://www.php.net/)
To unsubscribe, visit: http://www.php.net/unsub.php

Re: Re: Listing parent ids

am 28.07.2011 15:25:13 von Jim Giner

""Arno Kuhl"" wrote in message
news:D349CC15D13F48DD8D4F6ED70062138C@point01...
> >

> Hi Jim. I wanted the list of related parentids from current id to
> top-level
> (parentid=0).

Ahhhhh - now that is a much different question!

From your statement above, are you now saying you only want ONE list of
related ids, not the entire society of possible 'families' in your table?

Also - do your parent records have multiple children?



--
PHP Database Mailing List (http://www.php.net/)
To unsubscribe, visit: http://www.php.net/unsub.php

Re: Re: Listing parent ids

am 28.07.2011 15:34:38 von Richard Quadling

On 28 July 2011 14:09, Arno Kuhl wrote:
>>
>> I have a table with an id and a parentid.
>> If it's a top-level record the parentid is 0, otherwise it points to
>> another record, and if that record isn't a top-level record its
>> parentid points to another record, etc (a linked list).
>>
>> Is there a single select that will return the complete list of parentids=
?
>
> You say you have a parentid and an id - ie, two specific fields in your
> records.  You say that you want to query all the parentids.  No=
body else has
> said this, but why not just
>
> Select unique ids where parentid=3D0  ?  That gives you (as you=
say) all your
> top-level records, which are the parents of everything, no?  Or are =
you
> looking for each id that is itself a parent to something else?  If t=
he
> latter, then why not
>  select unique parentid where parentid <> 0  ?
>
> --
>
> Hi Jim. I wanted the list of related parentids from current id to top-lev=
el
> (parentid=3D0).
> That could be 0 or more results, regardless of how many non-zero parentid=
s
> there are in total.
> Currently I get this from selecting id=3Dparentid while parentid>0, ie
> recursively select each record going up the tree to the top level.
> The nested set model apparently can return the entire hierarchical list f=
rom
> the current node to the top level with a single select, but I haven't run
> any tests yet on my specific data.
>
> Cheers
> Arno
>
>
> --
> PHP Database Mailing List (http://www.php.net/)
> To unsubscribe, visit: http://www.php.net/unsub.php
>
>

If your data is based upon parentid and uniqueid, then you will need
to change your data...

http://data.bangtech.com/sql/nested_set_treeview.htm

and once you've done that and find you can't deal with things (maybe
it isn't for you), then
http://pratchev.blogspot.com/2007/02/convert-tree-structure- from-nested-set=
..html
will help you turn it all back again.

I've not used either of those but on the surface they seem adequate.

But just look at the difference in the volume of code.

NS =3D> AL ... 1 query. Any depth. It shows just how simple using a NS is.

I'll stop evangelising now.

I REALLY like NS.

--=20
Richard Quadling
Twitter : EE : Zend : PHPDoc
@RQuadling : e-e.com/M_248814.html : bit.ly/9O8vFY : bit.ly/lFnVea

--
PHP Database Mailing List (http://www.php.net/)
To unsubscribe, visit: http://www.php.net/unsub.php

RE: Re: Listing parent ids

am 28.07.2011 16:47:42 von Arno Kuhl

> Hi Jim. I wanted the list of related parentids from current id to
> top-level
> (parentid=0).

Ahhhhh - now that is a much different question!

From your statement above, are you now saying you only want ONE list of
related ids, not the entire society of possible 'families' in your table?

Also - do your parent records have multiple children?
--

Hi Jim. Only one linked list of parentids. No siblings.
Multiple records can have the same parentid, but that doesn't play a role.

Cheers
Arno


--
PHP Database Mailing List (http://www.php.net/)
To unsubscribe, visit: http://www.php.net/unsub.php

Re: Re: Listing parent ids

am 28.07.2011 17:21:35 von Jim Giner

""Arno Kuhl"" wrote in message
news:DB930522404B4552B8A15AF991C57E30@point01...
>
> Hi Jim. Only one linked list of parentids. No siblings.
> Multiple records can have the same parentid, but that doesn't play a role.
>

Okay. So you want only one 'family tree' at any given time, and a tree is a
straight line, ie, it has no branches.

Sounds to me like a loop surrounding a query that seeks out a specific id
which is continually re-evaluated from the last-read record's parentid. As
each query result is obtained (one record), the pair of keys is saved in an
array.

Curiousity has me asking - what are the contents of these records that such
a structure works? To me, this 'parentid' sounds like a foreign key, which
is usually used to read a separate table in a normalized db. Your
response that "multiple records can have the same parentid" is the same as a
"1-M" relationship, which implies the need for normalization. Apparently
your situation has normalized everything(?) into one table.



--
PHP Database Mailing List (http://www.php.net/)
To unsubscribe, visit: http://www.php.net/unsub.php

RE: Re: Listing parent ids

am 28.07.2011 17:23:58 von Arno Kuhl

If your data is based upon parentid and uniqueid, then you will need to
change your data...
http://data.bangtech.com/sql/nested_set_treeview.htm

and once you've done that and find you can't deal with things (maybe it
isn't for you), then
http://pratchev.blogspot.com/2007/02/convert-tree-structure- from-nested-set.
html
will help you turn it all back again.

Richard Quadling
--

Thanks Richard, those look like they could be really useful.

Cheers
Arno


--
PHP Database Mailing List (http://www.php.net/)
To unsubscribe, visit: http://www.php.net/unsub.php