Tricky logic problem - how to create a set-based solution for this query?

Question

Using SQL Server 2008 and any available features of TSQL, I am trying to work out how to if a set-based solution that does not involve a temp table exists for the following problem:

Given a set of nodes that have a parent-child relationship, and a set of key-value pairs that apply to each, and given that the value (for a given key-value pair) at a deeper level of the node hierarchy will override a value with the same key that is inherited from an ancestor node, select:

1. the full set of key-value pairs that apply to a given node
2. the set of inherited values for that node

The schema is as follows:

create table Node
(
    ID bigint identity primary key,
    ParentID bigint null foreign key references Node(ID),
    Name nvarchar(100)
);

create table KeyValuePair
(
    ID bigint identity primary key,
    KeyName nvarchar(100) not null,
    Value nvarchar(1000) not null,
    NodeID bigint not null foreign key references Node(ID),

    unique (KeyName, NodeID)
);

The result set would essentially include the columns KeyName, Value, InheritedValue.

I've been trying to do this using a common table expression but the logic of it is a bit tricky.

Answer 1

You should consider using the nested set model to store your hierarchy. Here is a link that describes it: http://dev.mysql.com/tech-resources/articles/hierarchical-data.html

It supports a much more SQL friendly approach to retrieving common information about hierarchical information.

Your requirement here could then be satisfied with a query on Node and a single join to KeyValuePair.

Answer 2

Ok, I've solved it myself. There are probably other ways to do it, but this seems to work well enough:

create procedure dbo.ListDataValues
    @nodeid bigint
as
begin
    with nodes as (
        select ID, ParentID, 0 as Level
        from Node n where ID=@nodeid
        union all
        select n.ID, n.ParentID, c.Level+1 as Level
        from Node n inner join nodes c on c.ParentID = n.ID
    ),
    keys as (
        select distinct(KeyName)
        from DataValue
        where NodeID in (select ID from nodes)
    )
    select v.KeyName, v.Value, i.Value as [InheritedValue], i.NodeID as [InheritedFromNodeID]
    from keys
    left join DataValue v on v.KeyName = keys.KeyName
    left join DataValue i on i.KeyName = keys.KeyName
        and i.NodeID = (select top 1 NodeID from DataValue d
                        inner join nodes k on k.ID = d.NodeID
                        where Level > 0 and d.KeyName = i.KeyName
                        order by Level)
    where v.NodeID = @nodeid
end

Answer 3

I setup the Node and KeyValuePair tables as per the question, and populated with some sample values, such that my hierarchy was as follows:

Root
|---A
|   |---A1
|   |---A2
|
|---B
    |---B1
    |---B2

I assigned two properties, named "Property 1" and "Property 2", each defined in root with values "Root Prop 1" and "Root Prop 2" respectively. In A, I overrode "Property 1" with value "A Prop 1" and in B, I overrode "Property 2" with value "B Prop 2".

set identity_insert Node on
insert into Node(ID,ParentID,Name)
values (1,null,'Root'),(2,1,'A'),(3,1,'B'),(4,2,'A1'),(5,2,'A2'),
       (6,3,'B1'),(7,3,'B2')
set identity_insert Node off

insert into KeyValuePair(KeyName, [Value], NodeID)
values ('Property 1','Root Prop 1',1),
('Property 2','Root Prop 2',1),
('Property 1','A Prop 1',2),
('Property 2','B Prop 2',3)

Calling Nathan's solution for node A1 yields no rows!

The where clause in Nathan's solution should be a condition of the join between keys and v, resulting in the revised procedure shown below (also I've renamed DataValue to KeyValuePair to be consistent with the original question):

create procedure dbo.ListDataValues
    @nodeid bigint
as
begin
    with nodes as (
        select ID, ParentID, 0 as Level
        from Node n where ID=@nodeid
        union all
        select n.ID, n.ParentID, c.Level+1 as Level
        from Node n inner join nodes c on c.ParentID = n.ID
    ),
    keys as (
        select distinct(KeyName)
        from KeyValuePair
        where NodeID in (select ID from nodes)
    )
    select
        keys.KeyName,
        v.Value,
        i.Value as [InheritedValue],
        i.NodeID as [InheritedFromNodeID]
    from
        keys
        left join KeyValuePair v on v.KeyName = keys.KeyName
                                     and v.NodeID = @nodeid
        left join KeyValuePair i on i.KeyName = keys.KeyName
            and i.NodeID = (select top 1 NodeID from KeyValuePair d
                            inner join nodes k on k.ID = d.NodeID
                            where Level > 0 and d.KeyName = i.KeyName
                            order by [Level])
end
go

This yielded the correct results as expected:

KeyName      Value   InheritedValue    InheritedFromNodeID
------------ ------- ----------------- --------------------
Property 1   NULL    A Prop 1          2
Property 2   NULL    Root Prop 2       1

Answer 4

This is one of those cases when materialized path shines. Here is how I solved a similar problem using it:

Store your configuration settings as a hierarchy in a database.