Data Inheritance in C#

Question

Is there a known pattern to inherit data in a hierarchical object structure? I have a hierarchical 'Item' structure which needs to inherit its 'Type' from its 'Parent' (have the same data as default). The type of sub item can be modified by its own, and when the type of parent Item changes, all sub items which their type is not changed, should get the new type of parent.

Note that I cannot fake it like

public string Type
{
    get
    {
        if (type == null)
            return Parent != null ? Parent.Type : null;

        return type;
    }
}

'cause I have to fill the values in the database, and the structure is too deep to use recursion and not worry about the performance.

The only way I can think of it now is

public string Type
{
    set
    {
        type = value;
        UpdateUnchangedChildren(value);
    }
}

public int AddChild(Item item)
{
    item.Type = Type;
    return Items.Add(item);
}

Is there a better way? Thanks.

Answer 1

I'm not 100% sure what it is you are trying to do... but you could use generics to pass the type of a parent object into a child object... But having a setter there doesn't really make sense... The Parent object's type will be set when it's instantiated, so why would you have a setter there to change it.

Assuming you have something like this...

public class Child<T>
{
   public string Type
   {
       get { return typeof(T).ToString(); }
   }
}

So then, when you have a Parent Object of any type, you can pass that to your Child Property...

public class ParentA
{
   public Child<ParentA> ChildObj { get; set; }
}

public class ParentB
{
   public Child<ParentB> ChildObj { get; set; }
}

public class ParentC
{
   public Child<ParentC> ChildObj { get; set; }
}

Calling any of those ChildObj.Type Properties will return ParentA, ParentB & ParentC respectively.

Buit I've a funny feeling you haven't fully explained what it is you're trying to do. Can you post some more code examples showing a Parent Class & Child/Item Class

Answer 2

"...the structure is too deep to use recursion and not worry about the performance."

Have you actually measured this? How many items are you dealing with, how deep is the structure, and how common is it for items to not have their own "Type" value? What are your performance goals for the application, and how does the recursive solution compare with those goals?

It is very common for people to think that recursion is slow and therefore eliminate it from consideration without ever trying it. It is NEVER a good idea to reject the simplest design for performance reasons without measuring it first. Otherwise you go off and invent a more complicated solution when the simpler one would have worked just fine.

Of course, your second solution is also using recursion, just going down the hierarchy instead of up. If the child inserts are happening at a different time and can absorb the possible performance hit, then perhaps that will be more acceptable.

Answer 3

It's a common problem, usually related to maintenance of various hierarchical settings/configurations. So, I guess a solution to it can be considered "a pattern".

Anyways, from the internal architecture perspective you have 2 major options:

• normalized structure
• denormalized structure

"Normazlied" is the one implemented with recursion. A particular piece of data is always stored in one place, all the other places have references to it (e.g., to parent). The structure is easily updated, but readng from it may be a problem.

"Denormalized" means that every node will store the whole set of settings for its level and whenever you update a node it takes some time to go down the hierarchy and corect all the children nodes. But the reading operation is instant.

And so the "denormalized" version seems to be more widely used, because the common scenario with settings is that you update them rarely, while read them often, hence you need better read performance. For example, Windows ACL security model uses the "denormalized" approach to make security checks fast. You can read how they resolve conflicts between the "inherited" and explicit permissions (ACEs) by checking them in a specific order. That might be an overkill for your particular system though, you can simply have a flag that a particular value was overriden or, on the opposite, reset to "default"...

Further details depend on your system needs, you might waht to have a "hybrid" architecture, where some of the fields would be "normalized" and some others won't. But you seem to be on the right way.

Answer 4

An obvious optimization would be to cache the value obtained from the parent when reading the type. That means you will only traverse each path at most once (whereas the naive solution means you'll be traversing each subpath again and again for each path containing it, which means up to O(h^2) instead of O(h)). That would work great if you have more reads than writes.

Consider this:

class Node
{
    string _cachedParentType = null;
    string _type;
    string Type 
    {
        get { return _type ?? _cachedParentType ?? (_cachedParentType = Parent.Type); }
        set 
        { 
            _type = value; 
            foreach (var child in Children) { child._cachedParentType = null; }
        }
    }
}

This means with enough reads and few writes, reading becomes O(1) in the best case or, at worst, a "cache miss" will cost you O(h) with h being the height of the tree; while updating is O(k) with k being the branching level (because we only update one layer down!). I think this will generally be better than the UpdateUnchangedChildren solution (which I presume updates nodes recursively all the way to the leafs), unless you're doing WAY more reads than writes.