db for a simple ontology

Questions about the MySQL, PostgreSQL, and most other databases, as well as using it with PHP can be asked here.

Moderator: General Moderators

Post Reply
rubberjohn
Forum Contributor
Posts: 193
Joined: Fri Feb 25, 2005 4:03 am

db for a simple ontology

Post by rubberjohn »

Hi,

Im in the process of making a simple ontology like system using php and js.

it works like this: a user can select a root topic >> sub-topic1 >> sub=topic2 >> interest.

For example Computing / IT >> Web Dev >> mark up >> CSS

So all I would need is four tables for each of the elements above, i can therefore code where to search for the child of a parent element? is that right?

The problem I am having is that the structure is not as static as this, ie there can be a variable amount of sub-topics. So I am having problems getting my head around how to design the db for this. is it just a case of making a db with a root topic, a number of sub topics and an interest table and then linking each child to its parent. How would I make the parent 'aware' of whether it has any children and how many?

would a suitable solution be to create a static number of sub-topics, so when a user has selected a root topic and starts moving through the 'sub-topic' tables as soon as there is a sub topic table with no results the 'interests' table is searched?


What I am after is something that resembles a feature vector for a r-tree, so that when a user has chosen a topic a vector is generated and can then be used as an index

As you can probably see i'm getting into a bit of a mess over this - any pointers would be a massive help.

thanks

rj
User avatar
feyd
Neighborhood Spidermoddy
Posts: 31559
Joined: Mon Mar 29, 2004 3:24 pm
Location: Bothell, Washington, USA

Post by feyd »

posted earlier today: viewtopic.php?t=46762
User avatar
phpScott
DevNet Resident
Posts: 1206
Joined: Wed Oct 09, 2002 6:51 pm
Location: Keele, U.K.

Post by phpScott »

nice redirect feyd.
rubberjohn
Forum Contributor
Posts: 193
Joined: Fri Feb 25, 2005 4:03 am

Post by rubberjohn »

so i don't need separate tables and can store all the values and the tree structure in one table

what if a node has multiple inheritance?
User avatar
Christopher
Site Administrator
Posts: 13596
Joined: Wed Aug 25, 2004 7:54 pm
Location: New York, NY, US

Post by Christopher »

There is a simpler way to select nodes in a hierarchy if you don't mind the limitations. It uses paths like in Unix and SQL's LIKE with wildcards. For example, if you have the following categories they would have paths like:

Code: Select all

id    path            name
1   /1/               Computing / IT
18  /1/18/            Web Dev
44  /1/18/44/         mark up
231 /1/18/44/231/     CSS
239 /1/18/44/239/     HTML
52  /1/18/52/         programming
Then you have the "article" records you want to select with matching:

Code: Select all

id    path            title
1    /1/18/44/231/    Introduction to CSS
2    /1/18/44/231/    CSS Box Model
3    /1/18/44/231/    CSS Positioning
4    /1/18/           Website Development Basics
5    /1/18/44/239/    Introduction to HTML
6    /1/18/44/        Introduction to Markup
7    /1/18/44/239/    HTML Tag Reference
8    /1/18/52/        Introduction to Programming
And if you want all the articles on "Web Dev mark up" you do a:

Code: Select all

SELECT * FROM articles WHERE path LIKE '/1/18/44/%'
If you want only articles on "CSS" then you do a:

Code: Select all

SELECT * FROM articles WHERE path LIKE '/1/18/44/231/%'
It is not as powerful as a relational solutions, but it is very simple to manage if your needs are basic.
(#10850)
rubberjohn
Forum Contributor
Posts: 193
Joined: Fri Feb 25, 2005 4:03 am

Post by rubberjohn »

thanks arborint but i think i need something like table 2 from http://www.intelligententerprise.com/001020/celko.jhtml

would this work if i added a second table for the 'leaf' nodes?

meaning there is a table for parent nodes and one for leaf nodes

so when a parent node is returned with a difference between the left and right values greater than one AND there is no other parent node with left or right values within that range the search is directed to the leaf table...
User avatar
Christopher
Site Administrator
Posts: 13596
Joined: Wed Aug 25, 2004 7:54 pm
Location: New York, NY, US

Post by Christopher »

If all you need is a simple hierarchy, the the method above is very simple and works well. If you have more complex relationships then you need more complex system. However, to build a "simple ontology" like you described, paths may be fine.
(#10850)
rubberjohn
Forum Contributor
Posts: 193
Joined: Fri Feb 25, 2005 4:03 am

Post by rubberjohn »

Thanks for all of your help, ive pretty much sorted it out now using preorder tree traversal explained here (cheers feyd):

http://www.sitepoint.com/article/hierar ... database/2

although i think i can also use your suggestion too, arborint for another part of the system, so thanks for that as well.

one last question, how could i represent multiple inheritance using preorder tree traversal, ie a leaf belonging to more than one parent?

from the example i was using above:

computing/IT >> web dev >> programming languages >> php

computing/IT >> programming >> php

**EDIT

and what if i want to incorporate a second (or third...) root topic?

computing/IT >>...
Graphic Design >>...
Journalism >>...
etc

**EDIT


any suggestions would be greatly appreciated - as usual.

rj
rubberjohn
Forum Contributor
Posts: 193
Joined: Fri Feb 25, 2005 4:03 am

Post by rubberjohn »

re incorporating more root topics - would there be too much of an overhead if the root topics were simply given a left hand number higher than the previous topic's right hand number, for example:--

using the format (root_topic, left #, right #)...

(computing / IT, 1, 78)------- (Graphic Design, 79, 150) --------- (Journalism,151, 210) and so on

By overhead i mean that if a new node was inserted, say for computing / IT, it would mean incrementing every number above it by one (in its own topic tree and all of the others belonging to the other root topics) although adding a new root topic would not be common.

is this the most efficient way of achieving this?

thanks

rj
Post Reply