Showing entries 1 to 4
Displaying posts with tag: trees (reset)
Rendering Trees with Closure Tables

I got a comment from a reader about the Naive Trees section of my presentation SQL Antipatterns Strike Back. I've given this presentation at the MySQL Conference & Expo in the past.I'd also like to mention that I've developed these ideas into a new book, SQL Antipatterns: Avoiding the Pitfalls of Database Programming. The book is now available in Beta and for pre-order from Pragmatic

OQGRAPH engine on MySQL University – 5 Nov 2009 10:00 UTC

Only a few weeks after Walter’s session on Multi-Master Replication with MMM and thanks to the great gang at MySQL Docs (my colleagues from long ago!) I’ll be doing a MySQL University session in a few days, about the GRAPH computation engine. From talks/demos I’ve done about it so far, I’ve learnt that people love it but there are lots of interesting questions. After all, it’s a pretty new and in a way exotic thing.

MySQL University uses DimDim, an online presentation service. You’ll see slides, and hear my voice. You can also type questions in a live chat room. We actually even got desktop sharing working so a live demo is possible, we’ll see how that goes on the day (I’ll make sure to have static slides for the same also

For session details and the exact link to DimDim, see the …

[Read more]
GRAPH engine – Mk.II

The GRAPH engine allows you to deal with hierarchies and graphs in a purely relational way. So, we can find all children of an item, path from an item to a root node, shortest path between two items, and so on, each with a simple basic query structure using standard SQL grammar.

The engine is implemented as a MySQL/MariaDB 5.1 plugin (we’re working on a 5.0 backport for some clients) and thus runs with an unmodified server.

Demo time! I’ll simplify/strip a little bit here for space reasons, but what’s here is plain cut/paste from a running server, no edits

-- insert a few entries with connections (and multiple paths)
insert into foo (origid, destid) values (1,2), (2,3), (2,4), (4,5), (3,6), (5,6);
-- a regular table to join on to
insert into people values (1,"pearce"),(2,"hunnicut"),(3,"potter"), …
[Read more]
Trees in SQL

The problem of how to handle trees in SQL has been talked about alot. The basic 3 ways are:

  • store the full path for each entry
  • store the parent for each node
  • use nested tree

Nested tree is good for read-many-write-less applications where the tree doesn't check over time too much as a write-operation is heavy-weight most of the time.

Referencing the Parent through the full path

Using the variant of the path involves a lot of string handling and is always slow. See below:

# use a full path to each node
CREATE TABLE tree_path (
  node_path VARCHAR(1024) PRIMARY KEY,
  name VARCHAR(32) NOT NULL,
  INDEX (name)
) ENGINE = innodb;

  ( '/0',     'Earth' ),
  ( '/0/0',   'Europe' ),
  ( '/0/0/1', 'Germany' ),
  ( '/1',     'Moon' ),
  ( '/0/1',   'Asia' );

# search for parent of 'Asia'
  FROM tree_path AS t1
 WHERE t1.node_path = ( …
[Read more]
Showing entries 1 to 4