Posted on 2 Comments

Hierarchies in SQL? OQGRAPH engine backend preview

Dealing with hierarchies in a relational database is a pest. There’s Oracle’s CONNECT BY PRIOR, and the SQL standard defines IBM’s recursive UNION, but still… wouldn’t it be nice if a hierarchy (or even a full-on graph, like social networks have) could just be managed cleanly relationally?

This is something Kim and I have been dabbling with. The engine is called OQGRAPH (OQ for Open Query) now because just graph caused some symbol conflict hassles. Anyway, following is a brief demo of how it works.

First, let’s insert some data…

mysql> INSERT INTO gstest (origid,destid) VALUES (1,2),(1,3),(2,4);

Get it back out plain…

mysql> SELECT origid AS node, destid AS edge FROM gstest;
+-------------+
| node | edge |
+-------------+
|    1 |    3 |
|    1 |    2 |
|    2 |    4 |
|    3 | NULL |
|    4 | NULL |
+-------------+

(Hey, notice something? the engine automatically added nodes 3 and 4: because there’s edges going there, they must exist!)

Now for a more fancy trick: show me any (not shortest per-se, just any) path from 1 to 4 (2 hops)…

mysql> SELECT GROUP_CONCAT(linkid ORDER BY seq) AS path FROM gstest
    ->  WHERE latch=1 AND origid=1 AND destid=4;
+-------+
| path  |
+-------+
| 1,2,4 |
+-------+

Same from 3 to 2…

mysql> SELECT GROUP_CONCAT(linkid ORDER BY seq) AS path FROM gstest
    ->  WHERE latch=1 AND origid=3 AND destid=2;
Empty set

(Presuming uni-directional edges here, there is no possible path from 3 to 2)

How does it work? What else can it do? Does it make my morning coffee? Can I get it?
Well, for more info, background and discussion, come to the “dealing with hierarchies and graphs” BoF at the MySQL Conf, or contact me directly.

Oh, and you may ask: what’s with the “any path” thing? Well, that was easier to implement than a shortest path algorithm, being 2am at the time 😉 But the system could do shortest path, and whatever else you might need.

Posted on 2 Comments

2 thoughts on “Hierarchies in SQL? OQGRAPH engine backend preview

  1. […] Stewart, Brian, Mark, Paul, and others) who answered questions and looked things up, the earlier backend demo can now be executed from a MySQL 5.1 server with the OQGRAPH Engine plugin loaded. In other words, […]

  2. The data sets that Arjen has entered into the table describe points in a graph (nodes) and connections between the nodes (called edges.)

    1,2 describes two nodes and a connection between them, as do 1,3 and 2,4.

    The graph of these connections is just a simple line with 4 points.

    (3)-(1)-(2)-(4)

    For more information on graph theory, see:

    http://en.wikipedia.org/wiki/Graph_(mathematics)

Comments are closed.