How can a tree be stored in a database?

Question

If one were to implement a tree using a 4GL like C#, and storing it in a database, such as SQL Server 2008, what would the schema/design look like?

In other words, what role would the database play in such an implementation?

Answer 1

Storing the Tree

There are several options:

1. It is just a tree, after all, so you could store it the same way you would store any other tree (essentially via a recursive FOREIGN KEY).
2. Or, convert the suffix tree into suffix array and store that into the the database.
3. Or, you could serialize it to (say) XML, then store it to a single CLOB.
4. Or, since a suffix tree is roughly 20 times larger than the "target" string it indexes, you could simply store the string and calculate the suffix tree on as-needed basis (e.g. using Ukkonen's algorithm).

NOTE: In the case of the suffix array, you won't be storing any characters, you'd just store the indexes describing each element, something like this:

CREATE TABLE SUFFIX_ARRAY (
    ORDER INT PRIMARY KEY, -- Position in the suffix array.
    START INT NOT NULL, -- Position of the starting character of the suffix within the target string.
    LONGEST_COMMON_PREFIX INT NOT NULL -- If useful for your application.
)

You'd also have to separately store the "target" string (e.g. in a CLOB in another table).

Using the Tree

1. If you store the suffix tree directly, you should be able search it directly using SQL.
2. If you store it as suffix array, you'll have to juggle a bit to implement the binary search through the SQL, but should be possible.
3. (and 4) If you store it in CLOB (or don't store it at all and just store the target string), then obviously you won't be able to access it directly in the database (not efficiently anyway) - your only option would be to load (or re-create) it in memory.