[prev in list] [next in list] [prev in thread] [next in thread]
List: postgresql-admin
Subject: Re: [ADMIN] [Fwd: binary tree query]
From: Jodi Kanter <jkanter () virginia ! edu>
Date: 2004-01-29 14:10:41
Message-ID: 40191461.9030800 () virginia ! edu
[Download RAW message or body]
Thanks for the article. It did help some but I am still not sure if
representing a tree is best served using a self referential table.
Wouldn't it be better to separate it into several tables?
Can anyone else comment? Anyone have experience storing data that is
hierarchical in nature (e.g. a tree formation).
Jodi
Yuji Shinozaki wrote:
>Hi Jodi,
>
>I believe the technique they are using is representing a tree as nested
>sets. It requires that the database is built with properly nested
>left_id's and right_id's, and this technique is often regarded as a
>efficient means for retrieving hierachical information.
>
>Here is one reference about it:
>
>http://www.geocrawler.com/archives/3/6/2001/10/0/6961775/
>
>As for the inner join clauses they are in effect analogous to
>where's but the optimizer handles them differently. That is where
>(pardon the pun) my understanding dwindles. Perhaps someone else has
>better insight about inner join's vs where's.
>
>Hope this sheds some light and not too many shadows,
>
>yuji
>----
>
>
>On Mon, 26 Jan 2004, Jodi Kanter wrote:
>
>
>
>>I have a biochemist telling me that this query below is a typical one
>>for crawling through a taxonomic tree and that this is how I should
>>represent some peptide information we have. Is there anyone on this list
>>familiar with such data? I am weak in the science department but this
>>query looks like it might not be the most efficient approach.
>>I have not been able to run an explain analyze yet as the database
>>structure and data are not in place yet. We are just in the planning
>>stages right now.
>>
>>Any comments, suggestions, concerns, etc. would be much appreciated.
>>Would an experienced DBA recommend a different approach? Can anyone
>>offer some insight into the usefulness of INNER joins and the use of
>>BETWEEN? I am concernec about performance as well since I expect this
>>table to get large.
>>
>>SELECT count(*)
>> FROM taxon_name
>> INNER JOIN taxon AS tax_b USING(taxon_id)
>> INNER JOIN taxon AS tax_v ON (tax_v.left_id BETWEEN
>>tax_b.left_id AND tax_b.right_id )
>> INNER JOIN annot ON (tax_v.taxon_id = annot.taxon_id)
>> INNER JOIN protein ON (protein.prot_id= annot.prot_id)
>> WHERE annot.pref = 1
>> AND taxon_name.taxon_id=207245
>>;
>>
>>
>>
>>Thanks,
>>Jodi
>>
>>--
>>
>>/_______________________________
>>//Jodi L Kanter
>>BioInformatics Database Administrator
>>University of Virginia
>>(434) 924-2846
>>jkanter@virginia.edu <mailto:jkanter@virginia.edu>/
>>
>>
>>
>>/ /
>>
>>/ /
>>
>>
>>
>>
>
>Yuji Shinozaki Computer Systems Senior Engineer
>ys2n@virginia.edu Advanced Technologies Group
>(434)924-7171 Information Technology & Communication
>http://www.people.virginia.edu/~ys2n University of Virginia
>
>
>---------------------------(end of broadcast)---------------------------
>TIP 4: Don't 'kill -9' the postmaster
>
>
>
--
/_______________________________
//Jodi L Kanter
BioInformatics Database Administrator
University of Virginia
(434) 924-2846
jkanter@virginia.edu <mailto:jkanter@virginia.edu>/
/ /
/ /
[Attachment #3 (text/html)]
<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
<html>
<head>
<meta http-equiv="Content-Type" content="text/html;charset=ISO-8859-1">
<title></title>
</head>
<body text="#000000" bgcolor="#ffffff">
Thanks for the article. It did help some but I am still not sure if
representing a tree is best served using a self referential table.
Wouldn't it be better to separate it into several tables?<br>
Can anyone else comment? Anyone have experience storing data that is
hierarchical in nature (e.g. a tree formation).<br>
Jodi<br>
<br>
Yuji Shinozaki wrote:<br>
<blockquote type="cite"
cite="midPine.LNX.4.44.0401261422120.29962-100000@atg2000.itc.virginia.edu">
<pre wrap="">Hi Jodi,
I believe the technique they are using is representing a tree as nested
sets. It requires that the database is built with properly nested
left_id's and right_id's, and this technique is often regarded as a
efficient means for retrieving hierachical information.
Here is one reference about it:
<a class="moz-txt-link-freetext" \
href="http://www.geocrawler.com/archives/3/6/2001/10/0/6961775/">http://www.geocrawler.com/archives/3/6/2001/10/0/6961775/</a>
As for the inner join clauses they are in effect analogous to
where's but the optimizer handles them differently. That is where
(pardon the pun) my understanding dwindles. Perhaps someone else has
better insight about inner join's vs where's.
Hope this sheds some light and not too many shadows,
yuji
----
On Mon, 26 Jan 2004, Jodi Kanter wrote:
</pre>
<blockquote type="cite">
<pre wrap="">I have a biochemist telling me that this query below is a typical \
one for crawling through a taxonomic tree and that this is how I should
represent some peptide information we have. Is there anyone on this list
familiar with such data? I am weak in the science department but this
query looks like it might not be the most efficient approach.
I have not been able to run an explain analyze yet as the database
structure and data are not in place yet. We are just in the planning
stages right now.
Any comments, suggestions, concerns, etc. would be much appreciated.
Would an experienced DBA recommend a different approach? Can anyone
offer some insight into the usefulness of INNER joins and the use of
BETWEEN? I am concernec about performance as well since I expect this
table to get large.
SELECT count(*)
FROM taxon_name
INNER JOIN taxon AS tax_b USING(taxon_id)
INNER JOIN taxon AS tax_v ON (tax_v.left_id BETWEEN
tax_b.left_id AND tax_b.right_id )
INNER JOIN annot ON (tax_v.taxon_id = annot.taxon_id)
INNER JOIN protein ON (protein.prot_id= annot.prot_id)
WHERE annot.pref = 1
AND taxon_name.taxon_id=207245
;
Thanks,
Jodi
--
/_______________________________
//Jodi L Kanter
BioInformatics Database Administrator
University of Virginia
(434) 924-2846
<a class="moz-txt-link-abbreviated" \
href="mailto:jkanter@virginia.edu">jkanter@virginia.edu</a> <a \
class="moz-txt-link-rfc2396E" \
href="mailto:jkanter@virginia.edu"><mailto:jkanter@virginia.edu></a>/
/ /
/ /
</pre>
</blockquote>
<pre wrap=""><!---->
Yuji Shinozaki Computer Systems Senior Engineer
<a class="moz-txt-link-abbreviated" \
href="mailto:ys2n@virginia.edu">ys2n@virginia.edu</a> Advanced Technologies Group \
(434)924-7171 Information Technology & Communication <a \
class="moz-txt-link-freetext" \
href="http://www.people.virginia.edu/~ys2n">http://www.people.virginia.edu/~ys2n</a> \
University of Virginia
---------------------------(end of broadcast)---------------------------
TIP 4: Don't 'kill -9' the postmaster
</pre>
</blockquote>
<br>
<div class="moz-signature">-- <br>
<meta content="text/html; " http-equiv="Content-Type">
<meta content="Word.Document" name="ProgId">
<meta content="Microsoft Word 9" name="Generator">
<meta content="Microsoft Word 9" name="Originator">
<link href="./email%20sig_files/filelist.xml" rel="File-List">
<title>________________________________</title>
<!--[if gte mso 9]><xml>
<o:DocumentProperties>
<o:LastAuthor>jlk3x</o:LastAuthor>
<o:Revision>2</o:Revision>
<o:TotalTime>6</o:TotalTime>
<o:Created>2002-01-15T15:50:00Z</o:Created>
<o:LastSaved>2002-01-15T15:50:00Z</o:LastSaved>
<o:Pages>1</o:Pages>
<o:Words>27</o:Words>
<o:Characters>157</o:Characters>
<o:Company>University of Virginia</o:Company>
<o:Lines>1</o:Lines>
<o:Paragraphs>1</o:Paragraphs>
<o:CharactersWithSpaces>192</o:CharactersWithSpaces>
<o:Version>9.2720</o:Version>
</o:DocumentProperties>
</xml><![endif]-->
<style>
<!--
/* Font Definitions */
@font-face
{font-family:"MS Mincho";
panose-1:0 0 0 0 0 0 0 0 0 0;
mso-font-alt:"\FF2D\FF33 \660E\671D";
mso-font-charset:128;
mso-generic-font-family:roman;
mso-font-format:other;
mso-font-pitch:fixed;
mso-font-signature:1 134676480 16 0 131072 0;}
@font-face
{font-family:"\@MS Mincho";
panose-1:0 0 0 0 0 0 0 0 0 0;
mso-font-charset:128;
mso-generic-font-family:roman;
mso-font-format:other;
mso-font-pitch:fixed;
mso-font-signature:1 134676480 16 0 131072 0;}
/* Style Definitions */
p.MsoNormal, li.MsoNormal, div.MsoNormal
{mso-style-parent:"";
margin:0in;
margin-bottom:.0001pt;
mso-pagination:widow-orphan;
font-size:12.0pt;
font-family:"Times New Roman";
mso-fareast-font-family:"Times New Roman";}
a:link, span.MsoHyperlink
{color:blue;
text-decoration:underline;
text-underline:single;}
a:visited, span.MsoHyperlinkFollowed
{color:purple;
text-decoration:underline;
text-underline:single;}
p.MsoPlainText, li.MsoPlainText, div.MsoPlainText
{margin:0in;
margin-bottom:.0001pt;
mso-pagination:widow-orphan;
font-size:10.0pt;
font-family:"Courier New";
mso-fareast-font-family:"Times New Roman";}
@page Section1
{size:8.5in 11.0in;
margin:1.0in 65.95pt 1.0in 65.95pt;
mso-header-margin:.5in;
mso-footer-margin:.5in;
mso-paper-source:0;}
div.Section1
{page:Section1;}
-->
</style>
<div class="Section1">
<p class="MsoNormal"><i><span
style="font-size: 9pt; font-family: Arial;">_______________________________<br>
</span></i><i><span style="font-size: 10pt;">Jodi L Kanter<br>
BioInformatics Database Administrator<br>
University of Virginia<br>
(434) 924-2846<br>
<a href="mailto:jkanter@virginia.edu">jkanter@virginia.edu</a></span></i><span
style="font-size: 11pt; font-family: Arial;"><br style="">
<!--[if !supportLineBreakNewLine]--><br style="">
<!--[endif]--><o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size: 11pt; font-family: Arial;"><!--[if \
!supportEmptyParas]--> <!--[endif]--><o:p></o:p></span></p> <p \
class="MsoNormal"><i><span style="font-size: 9pt; font-family: Arial;"><!--[if \
!supportEmptyParas]--> <!--[endif]--><o:p></o:p></span></i></p> <p \
class="MsoNormal"><i><span style="font-size: 9pt; font-family: Arial;"><!--[if \
!supportEmptyParas]--> <!--[endif]--><o:p></o:p></span></i></p> </div>
</div>
</body>
</html>
[prev in list] [next in list] [prev in thread] [next in thread]
Configure |
About |
News |
Add a list |
Sponsored by KoreLogic