Choice of Database schema for storing folder system

1. Your first schema will work just fine.When you put an index on the FullPath column, use either the case-sensitive BETWEEN operator for queries, or use LIKE with either COLLATE NOCASE on the index or with PRAGMA case_sensitive_like.

   Please note that this schema also stores all parents, but the IDs (the names) are all concatenated into one value.

   Renaming a directory would require updating all its subtree entries, but you mention history, so it's possible that old entries should stay the same.

2. Your second schema is essentially the Closure Table mentioned in Dan D's comment.Take care to not forget the entries for depth 0.

   This will store lots of data, but being IDs, the values should not be too large.

   (You don't actually need RelationshipID, do you?)

3. Another choice for storing trees is the nested set model, or the similar nested interval model.The nested set model allows to retrieve subtrees by querying for an interval, but updates are hairy.The nested interval model uses fractions, which are not a native data type and therefore cannot be indexed.

I'd estimate that the first alternative would be easiest to use.I should also be no slower than the others if lookups are properly indexed.

My personal favourite is the visitation number approach, which I think would be especially useful for you since it makes it pretty easy to run aggregate queries against a record and its descendants.