4

I'm currently designing a SQL Server database schema for an application that consists of highly structured "tree" data. So, a table might look like this:

id
parentId (references id in same table)
text

This is simple enough, but I also need to be able to update either the parentId of a node or the text of a node (or delete nodes), and access each revision of the tree at the same speed that the current revision can be retrieved. My current solution is to have two tables. First a revision table:

id
revisionDate

And then a modified node table:

id
UID (same for all revisions of a specific node)
revisionId (references id of revision table)
deleted (flag for deleted node)
parentUID (references UID of parent node)
text

So to get the tree for a specific revision, you take the revisionId and all revisionIds before it, then query the node table for all nodes with those revisionIds, then take only the highest revisionId nodes for nodes that share a UID, then delete any node that has the deleted flag set.

This works, but gets ugly fast (I'm using a simplified example) I actually have about 10 tables like this that need revision tracking, with each table having cross references to each other. This approach also breaks foreign keys, since UIDs are not unique. I cannot simply copy the full tree data for each revision, since there may be hundreds of revisions per hour.

What would the best practice be for a problem like this? I'd be willing to use a nonrelational database if it would be clearly superior.

3

Trying to do FKs will just frustrate you - you don't actually need it.

If you handle versioning by using an InsertDateTime concept, then you're basically describing a Type2 dimension as used by many data warehouses. There is quite a lot of material out there about tuning systems that sit over the top of data warehouses, but from a T-SQL perspective, consider using APPLY. Like this:

SELECT ...
FROM ... AS t
CROSS APPLY (
    SELECT TOP (1) ...
    FROM ... AS rev
    WHERE rev.UID = t.UID
    AND rev.InsertDateTime < @revdatetime
    ORDER BY rev.InsertDateTime DESC) AS something
WHERE something.IsDeleted = 'N'

This kind of construct benefits from an index on (IsDeleted, UID, InsertDateTime DESC).

Alternatively, if you want to look at the whole table as at a particular time, use ROW_NUMBER() like:

WITH numbered AS
 (  SELECT *, ROW_NUMBER() OVER (PARTITION BY UID ORDER BY InsertDateTime DESC) AS rownum
    FROM ...
    WHERE InsertDateTime < @revDateTime
),
VersionAtTime AS
(   SELECT *
    FROM numbered
    WHERE rownum = 1
    AND IsDeleted = 'N'
)
SELECT ...
FROM VersionAtTime
....

(edited from original to move the IsDeleted predicates outside the sub-queries, removing all versions at that particular time)

  • This seems like a solid approach to me. One minor nit is that it doesn't handle deleted nodes properly. If the most recent revision of a particular node is deleted, the problem statement indicates that the node should not show up in the revision ("take only the highest revisionId nodes for nodes that share a UID, then delete any node that has the deleted flag set [for the highest revisionId]"), whereas your query will return the last non-deleted version of the node instead. – Geoff Patterson Sep 14 '15 at 18:55
  • Ah yes. Move the IsDeleted predicate outside. – Rob Farley Sep 14 '15 at 21:04
1

One answer I have given for a similar situation is here:

Best way to design a database and table to keep records of changes?

The third and fourth bullet points address your request for single query access to current / historical data and preservation of foreign keys.

Sometimes it's a help just to know that what you want is possible.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.