Horton

Thread

  1. Re: [HACKERS] Tree type, how best to impliment?

    Tom Lane <tgl@sss.pgh.pa.us> — 1998-11-17T15:25:31Z

    Terry Mackintosh <terry@terrym.com> writes:
> CREATE TABLE categories (
>    category       char(30)    NOT NULL,
>    pcatid         char(255)   NOT NULL,
>    cat_id         char(255)   PRIMARY KEY,
>    nidsufix       int4        DEFAULT 1 NOT NULL,
>    UNIQUE ( category, pcatid ));

OK, let me get this straight ...

1. cat_id is the unique object identifier for the current table row.
   You provide an index on it (via PRIMARY KEY) so it can be used for
   fast lookup.
2. pcatid is a child node's back-link to its parent node.
3. nidsufix exists to allow easy generation of the next child ID for
   a given node.
4. category is what?  Payload data?  It sure doesn't seem related to
   the tree structure per se.

Why is "category, pcatid" unique?  This seems to constrain a parent
to have only one child per category value --- is that what you want?
If so, why not use the category code as the ID suffix, and not have to
bother with maintaining a next-ID counter?

In theory pcatid is redundant, since you could form it by stripping the
last ".xxx" section from cat_id.  It might be worth storing anyway to
speed up relational queries --- eg you'd do
	SELECT ... WHERE pcatid = 'something'
to find the children of a given node.  But without an index for pcatid
it's not clear that's a win.  If you make a SQL function parent_ID() to
strip the textual suffix, then a functional index on parent_ID(cat_id)
should be as fast as an indexed pcatid field for searches, and it'd save
storage.

> The only limit on both depth and width is the amount of numbers and dots
> that will fit into a char(255) field.

If you use type text instead of a fixed-width char() field, there's no
limit to the depth ... and for normal not-too-deep trees it'd save
much storage compared to a fixed-width char(255) field...

A purely stylistic suggestion: IDs of the form "1.2.3.4" might be
mistaken for IP addresses, which of course they ain't.  It might save
confusion down the road to use a different delimiter.  Not slash either
unless you want the things to look like filenames ... maybe comma or
colon?

			regards, tom lane

  2. Re: [HACKERS] Tree type, how best to impliment?

    Terry Mackintosh <terry@terrym.com> — 1998-11-17T20:21:11Z

    On Tue, 17 Nov 1998, Tom Lane wrote:

> Terry Mackintosh <terry@terrym.com> writes:
> > CREATE TABLE categories (
> >    category       char(30)    NOT NULL,
> >    pcatid         char(255)   NOT NULL,
> >    cat_id         char(255)   PRIMARY KEY,
> >    nidsufix       int4        DEFAULT 1 NOT NULL,
> >    UNIQUE ( category, pcatid ));
> 
> OK, let me get this straight ...
> 
> 1. cat_id is the unique object identifier for the current table row.
>    You provide an index on it (via PRIMARY KEY) so it can be used for
>    fast lookup.
> 2. pcatid is a child node's back-link to its parent node.
> 3. nidsufix exists to allow easy generation of the next child ID for
>    a given node.

Yes to all.

> 4. category is what?  Payload data?  It sure doesn't seem related to
>    the tree structure per se.

Yes, this will be a tree of categories for a search engine, could also be
a message id in a threaded message database.

Example:             Things (1)
                   /       \
                Big (1.1)   Small (1.2)
             /          \
        Cars (1.1.1)   Boats (1.1.2)


> Why is "category, pcatid" unique?  This seems to constrain a parent
> to have only one child per category value --- is that what you want?

Yes.
It is very much like a directory structure, one would not want two
directories of the same name both off the same point in the file system.

> If so, why not use the category code as the ID suffix, and not have to
> bother with maintaining a next-ID counter?

category is human readable, for display, the id is not, and when deciding
what the next child's name should be, if not for the next-ID one would
have to go count all the other records that have the same parent.

> In theory pcatid is redundant, since you could form it by stripping the
> last ".xxx" section from cat_id.  It might be worth storing anyway to
> speed up relational queries --- eg you'd do
> 	SELECT ... WHERE pcatid = 'something'

Yes, I soon realized this :-) but as per my other post, could not figure
out how to do this for the UNIQUE constraint.

> to find the children of a given node.  But without an index for pcatid

I had planed to index it.

> ...
> > The only limit on both depth and width is the amount of numbers and dots
> > that will fit into a char(255) field.
> 
> If you use type text instead of a fixed-width char() field, there's no
> limit to the depth ... and for normal not-too-deep trees it'd save
> much storage compared to a fixed-width char(255) field...

Yes, I just was not sure how well indexes work with text fields?

> A purely stylistic suggestion: IDs of the form "1.2.3.4" might be
> mistaken for IP addresses, which of course they ain't.  It might save
> confusion down the road to use a different delimiter.  Not slash either
> unless you want the things to look like filenames ... maybe comma or
> colon?

Actually a directory structure is probably the closest analogy, and for
that reason I had thought about using slashes.

I had also though about one field only (text), where the categories would
be all chained together delimited with slashes and have a PRIMARY KEY
index.  That would automate by design all of the above problems.  But it
would creat new ones:-)  Like for many deep records, the table would be
much bigger.

Also, I wanted to use this same concept in other projects, and a one field
approch would only be good (maybe) for this project.  And if worked out,
this could be usefull to others as well.
 
Thanks, and have a great day
Terry Mackintosh <terry@terrym.com>          http://www.terrym.com
sysadmin/owner  Please! No MIME encoded or HTML mail, unless needed.

Proudly powered by R H Linux 4.2, Apache 1.3, PHP 3, PostgreSQL 6.4
-------------------------------------------------------------------
Success Is A Choice ... book by Rick Patino, get it, read it!

  3. Re: [HACKERS] Tree type, how best to impliment?

    Mark Hollomon <mark.hollomon.mhh@nt.com> — 1998-11-23T14:34:28Z

    Tom Lane wrote:
> A purely stylistic suggestion: IDs of the form "1.2.3.4" might be
> mistaken for IP addresses, which of course they ain't.  It might save
> confusion down the road to use a different delimiter.  Not slash either
> unless you want the things to look like filenames ... maybe comma or
> colon?
> 
>                         regards, tom lane

But the 'dot' notation also looks like an entry in an SNMP MIB.
I've been thinking about a similar structure for psql storage
of a MIB.

-- 

--------------
Mark Hollomon
mhh@nortelnetworks.com

  4. Re: [HACKERS] Tree type, how best to impliment?

    Terry Mackintosh <terry@terrym.com> — 1998-11-24T02:04:33Z

    Hi

On Mon, 23 Nov 1998, Mark Hollomon wrote:

> Tom Lane wrote:
> > A purely stylistic suggestion: IDs of the form "1.2.3.4" might be
> > mistaken for IP addresses, which of course they ain't.  It might save
> > confusion down the road to use a different delimiter.  Not slash either
> > unless you want the things to look like filenames ... maybe comma or
> > colon?
> > 
> >                         regards, tom lane
> 
> But the 'dot' notation also looks like an entry in an SNMP MIB.
> I've been thinking about a similar structure for psql storage
> of a MIB.

Well, as it logically mimics a directory structure, I finally went with a
'/' and full names instead of numbers.
And as there were no takers to help improve my understanding of how to
work with the SPI stuff, and as the docs on it are not very extensive, I
finally did the referincial integrity stuff for cross linking categories 
at the application lever, where it was realatively simple to write.
'cross links' == symbolic links in a file system.  In fact, logically
speaking, it is a file system.

I don't know what an 'MIB' is, but if this sort of thing is what you need,
then I can work with you, as I already have the details worked out, and I
would love to impliment some of the now-app-level-details on the database
side, where they belong.

Have a great day
Terry Mackintosh <terry@terrym.com>          http://www.terrym.com
sysadmin/owner  Please! No MIME encoded or HTML mail, unless needed.

Proudly powered by R H Linux 4.2, Apache 1.3, PHP 3, PostgreSQL 6.4
-------------------------------------------------------------------
Success Is A Choice ... book by Rick Patino, get it, read it!

  5. Re: [HACKERS] Tree type, how best to impliment?

    Mark Hollomon <mark.hollomon.mhh@nt.com> — 1998-11-24T13:43:22Z

    Terry Mackintosh wrote:
> 
> Hi
> 
> Well, as it logically mimics a directory structure, I finally went with a
> '/' and full names instead of numbers.

Can't say I blame you.

> And as there were no takers to help improve my understanding of how to
> work with the SPI stuff, and as the docs on it are not very extensive, I
> finally did the referincial integrity stuff for cross linking categories
> at the application lever, where it was realatively simple to write.
> 'cross links' == symbolic links in a file system.  In fact, logically
> speaking, it is a file system.
> 
> I don't know what an 'MIB' is, but if this sort of thing is what you need,
> then I can work with you, as I already have the details worked out, and I
> would love to impliment some of the now-app-level-details on the database
> side, where they belong.

MIB stands for Managemnet Information Base.
The Simple Network Management Protocol defines a 'database' of
information
about the devices that are to managed called a MIB. Each device as a
'OID'
that represents a traversal of a tree structure.
http://www.dordt.edu:457/NetAdminG/snmpC.smi.html
is a very short intro to the tree structure.
Each node gets a numerical label and an optional alpha label. The
'official'
OID for the node is the numeric labels for all ancestor nodes starting
at
the root, strung together with dots between them. (sound familiar?).
You can string together the alpha labels to create a symbolic OID. If
the
alpha label is unique, it is even permitted to use just the alpha label
of
the node of interest. This is actually useful. The top layers of the
tree
are set by the standards commitees. The local MIB is almost always a
proper
subtree of the 'internet' node of the standard tree. So, you can start
your
naming at 'internet' instead of having to alwas specify [ iso org dod
internet ... ]

We have a PostgreSQL database that keeps our inventory of routers,
desktops,
etc. The MIB however, is editted by hand. My ultimate goal is to be able
to generate the MIB from data stored in the database.

I'm afraid I am somewhat time constrained at the moment. Haven't even
upgraded
to 6.4 yet. My boss seems to think I ought to do what _he_ wants me to
do.
Oh, well.


--------------
Mark Hollomon
mhh@nortelnetworks.com