Sunday, July 10, 2005

Querying for Hierachies

Storing Hierarchical Data in a Database "Whether you want to build your own forum, publish the messages from a mailing list on your Website, or write your own cms: there will be a moment that you’ll want to store hierarchical data in a database. And, unless you’re using a XML-like database, tables aren’t hierarchical; they’re just a flat list. You’ll have to find a way to translate the hierarchy in a flat file."

"If you want to display the tree using a table with left and right values, you’ll first have to identify the nodes that you want to retrieve. For example, if you want the ‘Fruit’ subtree, you’ll have to select only the nodes with a left value between 2 and 11. In SQL, that would be:

SELECT * FROM tree WHERE lft BETWEEN 2 AND 11;"

It struct me how complicated either of these solutions are.

In iTQL it would be using walk:
"select $subject
...
where walk($subject <rdfs:subClassOf> <food:fruit>
and $subject <rdfs:subClassOf> $object);

Or in Sesame's SeRQL (concrete example here):
"SELECT DISTINCT _fruit
FROM _fruit serql:directSubClassOf <food:fruit>"

They aren't quite the same query - Sesame is inferring new statements and walk is not. In designing iTQL we were always deciding between magical predicates or functions (like walk) and sometimes slavishly sticking to triple patterns. Combining the walk and trans operations using a predicate, like in SeRQL, seems like a good approach to take.

Also, interesting in a fairly recent Sesame release are the ANY and ALL, EXISTS and MINUS features.

No comments: