How do you store a trie in a relational database?

Question

I have a prefix trie. What is the recommended schema for representing this structure in a relational database? I need substring matching to remain efficient.

Multiple

Yes, trie not tree. See en.wikipedia.org/wiki/Trie – Jett

Are you storing and retrieving the trie to/from DB to be used in your code ? Because for DB lookup there are built-in tools like full-text indexing (based on similar principles) – Triennium

Answer 1

How about the Materialized Path design?

CREATE TABLE trie (
  path VARCHAR(<maxdepth>) PRIMARY KEY,
  ...other attributes of a tree node...
);

To store a word like "stackoverflow":

INSERT INTO trie (path) VALUES
  ('s'), ('st'), ('sta'), ('stac'), ('stack'),
  ('stacko'), ('stackov'), ('stackove'), ('stackover'),
  ('stackover'), ('stackoverf'), ('stackoverflo'),
  ('stackoverflow');

The materialized path in the tree is the prefixed sequence of characters itself. This also forms the primary key. The size of the varchar column is the maximum depth of trie you want to store.

I can't think of anything more simple and straightforward than that, and it preserves efficient string storage and searching.

Gap

The link redirects to nothing of interest. Here's an archived version: web.archive.org/web/20071019044908/http://www.dbazine.com/… – Eugenaeugene

@Howie, thanks, I answered this 5.5 years ago, so it's not a surprise that some links go stale. – Gap

Can you give an example of how will you query this table for say "st" and there are more words like "stackoverflowone" – Earleanearleen

SELECT path FROM trie WHERE path='st'. If this returns a non-empty set, then "st" is in the Trie. I don't know what you're talking about on the second point. – Gap

I feel like the point of the trie is to find all words starting with st, but this only would return the one item 'st', not the strings starting with st. so is this answer not incomplete? would it be better to use like instead of =? – Perni

@avatarofhope2, Correct, one would use LIKE. – Gap

Answer 2

The above accepted answer to use the materialized path is awesome, but I think the table needs 2 more columns to be complete:

CREATE TABLE trie (
  path VARCHAR(<maxdepth>) PRIMARY KEY,
  **node_id NUMBER,**
  **parent_node_id NUMBER,**
  ...other attributes of a tree node...
);

The parent_node_id is a foreign key reference to the same table "trie", and references column "node_id". So suppose you search for the prefix "stack", if you have two matching suffix paths "overflow" and "underflow", you can find both of these child nodes using the query:

SELECT * FROM trie WHERE parent_node_id =
    (select node_id from trie where path='stack')

This will give us all the child nodes of a matching path and maintains the relations between the nodes.

Tocology

Answer 3

Does any of your entities have a relationship with any other? If not, that is, not relational, a hash table with a serialization would do it.

Deathbed

That's really not a trie... I agree that it probably makes sense to keep it out of the db, but turning it into a hashtable? – Jilli