Monday, May 13, 2013

Handling Hierarchies with the SQL HierarchyId datatype

Traditionally when we’ve dealt with hierarchical data in SQL we’ve need to jump through a few hoops to query it. Usually we’d set up a our data table with a parent Id reference, and to query it we would use a temp table and populate it in a recursive loop. This isn’t very efficient.

The new HierarchyId data type introduced in SQL 2008 simplifies querying this data hugely.

Let’s start with a scenario. Consider the hierarchical category list in any popular auction website.

|  |--Art Supplies
|  |--Carvings & Sculptures
|  |--Drawings
|  |--Paintings
|  \--Photographs
   |--Audio Books
   |--Childrens Books
   |--Comic Books
   \--Non fiction
      |  |--Ancient
      |  |--Asia
      |  |--Australia
      |  |--Britain
      |  |--Europe
      |  \--New Zealand

This is only a tiny segment of the categories. You can imagine the hierarchy could be both wide and deep. SQL 2008 introduces the new HierarchyId SQLCLR data type that stores the information about where the node lies within the tree of categories, as well as providing various methods which we can use to find information about the node.

First we’ll create a table to store our categories:

      CategoryId INT IDENTITY(1,1) NOT NULL,
      CategoryName VARCHAR(200) NOT NULL,
      [CategoryId] ASC

Next we’ll populate our root node:

INSERT INTO Categories (OrgNode, CategoryName)
VALUES (hierarchyid::GetRoot(), 'Home')

HierarchyId::GetRoot() is a static method that returns the root of the hierarchy tree. If we want to add a child node to this then we’ll need to grab the next available node value.

We can do this with the GetDescendant() method on an existing HierarchyId value. If we pass two NULL values, it’ll give you a new child node value one level deeper.

DECLARE @ChildOrgNode HierarchyId

SELECT @parentOrgNode = OrgNode
FROM Categories WHERE CategoryId=1

INSERT INTO Categories (OrgNode, CategoryName)
VALUES (@parentOrgNode, 'Art')

We can only add the first child node like this however. If there are existing child nodes then we’ll need to pass different values in to determine which existing child node it’s going before/after.

GetDescendant(@nodeX, NULL) will get a new node value after child node X.
GetDescendant(@nodeX, @nodeY) will get a new node value between child nodes X and Y.
GetDescendant(NULL, @nodeY) will get a new node value before child node y.

We can turn this into a stored procedure to simplify inserts in the future:

      @ParentCategoryId INT,
      @CategoryName VARCHAR(200)
      DECLARE @childOrgNode HierarchyId
      DECLARE @parentOrgNode HierarchyId
      -- Get the OrgNode value of our parent node
      SELECT @parentOrgNode = OrgNode
      FROM Categories
      WHERE CategoryId=@ParentCategoryId
            -- Determine the last child node below our parent
            -- (this could be null if no child nodes yet exist)
            SELECT @childOrgNode = max(OrgNode)
            FROM Categories
            WHERE OrgNode.GetAncestor(1) =@parentOrgNode;

            -- insert our new node after the existing last child
            INSERT INTO Categories (OrgNode, CategoryName)
            VALUES (@parentOrgNode.GetDescendant(@ChildOrgNode, NULL), @CategoryName)


And we can call this quite simply:

EXEC @BooksId = AddCategory 1, 'Books'
EXEC AddCategory @BooksId, 'Audio Books'
EXEC AddCategory @BooksId, 'Comic Books'

Now, let’s have a look at our data.

SELECT * FROM Categories;

SELECT * FROM Categories;

As you can see, our OrgNode value looks like a hexadecimal value.  We can see a friendlier view if we use the ToString() method

SELECT CategoryId, OrgNode, OrgNode.ToString()AS OrgNodeString, CategoryName FROM Categories

SELECT CategoryId, OrgNode, OrgNode.ToString()AS OrgNodeString, CategoryName FROM Categories

We can get even fancier if you need, and determine the ParentId for each category and a bit more information.  This makes it look more like the old mechanisms that we used to use for hierarchical lists, and can sometimes be useful in our front end code.

      C.OrgNode.ToString() AS OrgNodeString,
      P.CategoryId AS ParentId,
      C.OrgNode.GetLevel() AS Depth,
FROM Categories C
LEFT JOIN Categories P ON P.OrgNode = C.OrgNode.GetAncestor(1)

Select more details

The GetAncestor method will return the HierarchyId value of the nth parent.  GetAncestor(1) will return the immediate parent, GetAncestor(2) will return the parents parent, etc.

Let’s generate a whole bunch more data, just so that we can see how querying larger trees works

DECLARE @categoryId INT;
SELECT @categoryId = CategoryId FROM Categories WHERE CategoryName = 'Art'
EXEC AddCategory @categoryId, 'Art Supplies';
EXEC AddCategory @categoryId, 'Carvings & Sculptures';
EXEC AddCategory @categoryId, 'Drawings';
EXEC AddCategory @categoryId, 'Paintings';
EXEC AddCategory @categoryId, 'Photographs';
SELECT @categoryId = CategoryId FROM Categories WHERE CategoryName = 'Books'
EXEC AddCategory @categoryId, 'Fiction';
EXEC AddCategory @categoryId, 'Magazines';
EXEC @categoryId = AddCategory @categoryId, 'Non fiction';
EXEC AddCategory @categoryId, 'Biography';
EXEC AddCategory @categoryId, 'Cooking';
EXEC AddCategory @categoryId, 'Crafts';
EXEC AddCategory @categoryId, 'Hobbies';
EXEC @categoryId = AddCategory @categoryId, 'History';
EXEC AddCategory @categoryId, 'Ancient';
EXEC AddCategory @categoryId, 'Asia';
EXEC AddCategory @categoryId, 'Australia';
EXEC AddCategory @categoryId, 'Europe';
EXEC AddCategory @categoryId, 'New Zealand';

SELECT CategoryId, OrgNode, OrgNode.ToString()AS OrgNodeString, CategoryName FROM Categories

SELECT CategoryId, OrgNode, OrgNode.ToString()AS OrgNodeString, CategoryName FROM Categories

Now comes the really clever part.  What if we want to know all of the categories that are in the books section?

DECLARE @parentOrgNode HierarchyId;

-- Get the OrgNode value of our parent category
SELECT @parentOrgNode = OrgNode
FROM Categories
WHERE CategoryName='Non Fiction';

      OrgNode.ToString() AS OrgNodeString,
FROM Categories
      OrgNode.IsDescendantOf(@parentOrgNode) = 1

Select Non Fiction branch

The IsDescendantOf method will return a Boolean value (1 = true) if the given node is a descendant of the parameter node provided.  Any node is considered a descendant of itself, which is why we can see the Books category as well.

The beauty of this is that it is '''FAST'''.  Compare this with our traditional method where we would use a ParentId field, and recursively walk through the list of categories adding them to a temporary table.

If we want to build a breadcrumb trail of our category we could do something similar:

DECLARE @parentOrgNode HierarchyId;

-- Get the OrgNode value of our parent node
SELECT @parentOrgNode = OrgNode
FROM Categories
WHERE CategoryName='Non Fiction';

      OrgNode.GetLevel() AS Depth
FROM Categories
      @parentOrgNode.IsDescendantOf(OrgNode) = 1
ORDER BY OrgNode.GetLevel()

Select Non Fiction breadcrumb chain

Imagine that we also have a table called Products.  Each product would belong to a Category.  Querying all products that were in any of the book categories would be simple:

FROM Categories C
      ON C.CategoryId = P.CategoryId
      OrgNode.IsDescendantOf(@parentOrgNode) = 1

For our Windows and Web applications the HierarchyId data type is a full CLR type, so we can use all of these methods in our .NET projects simply by adding a reference to the Microsoft.SqlServer.Types class library and using the SqlHierarchyId type.

One tip for people using Entity Framework (which doesn’t natively support the HierarchyId type) is that you need to query it with a .ToString() method to get the string representation, and then use the Parse() method to turn this string back into a HierarchyId.  This can be used for updates in both directions, ie: both in SQL and in C#.

For example, this will return a valid HierarchyId value:

SELECT HierarchyId::Parse('/23/4/')

Now, all of this simplicity on querying the data does come with a downside. If you want to shuffle entire branches of your hierarchy around, then you need to do a lot more work re-parenting the HierarchyId values. We can certainly achieve this with a stored procedure, but I’m not going to get into here because it does get a lot more complex.

It can however be simpler to just provide simple Add and Delete methods, and Edits will only allow you to edit the non-hierarchy details such as title etc.

Monday, August 20, 2012

Kinect SDK Development

At the end of last year I did a bit of work with the Kinect SDK.  I built a Kinect plugin to control Microsoft Power Point presentations.  I wrote up my notes at the time, but I've just realised that I never posted a blog about it.

Although this was written months ago, and I know that the Kinect SDK has been updated since then, most of this information is still relevant.

The Kinect unit can provide 4 different streams of data at:
  1. Skeletal Tracking.
  2. “Depth” data stream.
  3. “Depth and Player” data stream.
  4. Colour video.

You can subscribe to events which are fired on every refresh (approx. 30 FPS) to handle changes to each of these data streams.

Skeletal Tracking

This data stream allows us to track the 3D position of 20 skeletal joints of up to 2 people standing in front of the Kinect unit.

The joints tracked include:
  • Head
  • Shoulders
  • Elbows
  • Wrists
  • Hands
  • Spine centre
  • Hips
  • Knees
  • Ankles
  • Feet

It is a fairly simple task to interrogate these joint positions.  

“Depth” data stream

This is a 320x240 data stream that we can display as video showing depth information, ie how far away from the Kinect camera each pixel in the view is.  It is fairly easy to create a grey scale video with dark pixels in the background, and light pixels in the foreground 

“Depth and Player” data stream

This is a copy of the Depth video stream, however a couple of bits in each depth byte are used to mark which Player each pixel belongs to.  This means that we could, for instance, render a video showing grey scale depth information (as before) but the pixels that relate to different players shown in different colours, or we could just render the depth image that relates to the current player, ignoring the background.

Colour video

This is another simple video stream, simply showing the full colour video from the Kinect unit at a 640x480 pixel resolution.

For our PowerPoint controller application I Built a WPF application with a Standard MVVM structure, and with the Kinect code in a separate code library.

I used these data streams mentioned above to perform our various forms of gesture recognition.  For the most part I used the Skeletal Tracking system, but we also attempted some recognition with the Depth and Player data stream, which I’ll mention later.

Skeletal Feedback

In our WPF application I have drawn the current skeleton layout on a canvas by simply updating line elements (and an ellipse for the head) with the current Joint positions translated from 3D coordinates into screen coordinates.

Movement Gestures

For the main gesture recognition I simply stored the last 20 recorded repositions of all of the skeletal joints.  This allows us to make and compare gestures of just under a second long.

To record a gesture I stored the recorded positions of one joint (eg: the right hand) relative to the centre of the shoulders.  I recorded multiple gestures this way, for instance:

Gesture Name
Hand Left
Hand Right
This move is simply a wave of your left or right hand extended directly in front of yourself at shoulder level (Swimming).
Hand Right
Bring your arm up to the right of your head at about a 45 degree angle with your elbow slightly forward.
Hand Left
Hand Right
Draw a half circle in front of your body (Karate Kid).
Flap Up/Down
Hand Left
Hand Right
Extend your arm out to the side and wave up or down (Flap your wings).

To check if a gesture has been triggered, I just do a comparison of the recorded gesture positions with the most recent positions of each relevant Joint.  We calculate the 3D direction and distance between the centre of the shoulders and the Joint for each of the 20 historical positions and compare them with the recorded positions and allow a small margin of error.

If the last 20 positions match up fairly closely to a recorded gesture then we fire an event to say that the gesture has been observed.

We also don’t allow the same gesture to occur more than once a second because the difference between the first 19 recorded positions and the last 19 positions is often negligible.

Simple Positional Movement

Here we simply converted a Joint position into screen coordinates.  An event is fired every frame updating the position of the Joint.  This can be used to move the mouse pointer with our right hand for example.

Positional Gestures

The second gesture type that we record are Joint proximity triggers.  This is basically recording when two joints move within a certain distance of each other.  For instance we can have a trigger when we touch our head

Joint #1
Joint #2
Hand Right
Touch your Head with your Right Hand
Shoulder Left
Hand Right
Touch your Left Shoulder with your Right Hand
Hip Left
Hand Left
Put your Left Hand on your Hip

Events are fired when one of these gestures is enabled, and again when it is disabled.  This allows us to control the mouse with our hands using the Simple Positional Movement (described above), and putting your hand on your hip to trigger a mouse up/down.  While your hand is on your hip, the mouse button is held down, and when we remove our hand, the mouse button is released.

Open/Closed fist tracking.

I tried using the depth and player data stream as well as skeletal joint positions to draw a view of one of the hands, and attempted to determine from this whether the players’ hand was open or closed.  The plan was to use this in conjunction with Simple Positional Movement to move the mouse around and open and close the fist to toggle the mouse button.  

Unfortunately due to the low resolution of the depth information, as well as it being extremely difficult to visualise the fingers at all angles, this wasn’t very successful.  I have left the code in that draws the hand movement for others to see.

I also had a couple of ideas for other Gesture tracking methods 

Multiple Joint Gestures

Another method which I haven’t built, but which would be fairly simple, would be to extend the Movement Gestures to track multiple Joints.  This would allow us to record a clapping gesture for instance, or a salute that actually required the elbow to be in a certain position, or a short dance involving the whole body.

Posture Gestures

This method would be to record the relative positions of some or all joints at a point in time.  This would allow us to record the “Menu” position seen in various games of standing up stock straight with the left arm raised 45 degrees to the side.

Wednesday, May 23, 2012

Changing CRM form properties in Javascript doesn't trigger onChange

I've just learnt the hard way that when you change a field value on a MS CRM 2011 form via JavaScript it doesn't automatically trigger any onChange event which is wired up to that field.
To manually trigger any onChange event you do the following


or better yet, if you use a custom library to simplify your read

SetAttributeValue = function (attributeString, value) {
 var attribute = Xrm.Page.getAttribute(attributeString);
 if (attribute) {
  // manually fire the onChange event.

Tuesday, October 25, 2011

Isometric Coordinate Calculation Tutorial

Here we’ll look at how to calculate a map coordinate from a screen coordinate in an isometric game.

Friday, September 9, 2011

Creating Entities with dates in MS CRM 2011

MS CRM stores date values internally in UTC date format, so when I was programmatically creating appointments earlier this week I was getting weird date issues.

The solution is really simple

Thursday, August 11, 2011

Getting MSN Messenger out of the Taskbar in Windows 7

I hate having the clutter of extra background apps sitting in my taskbar in Windows 7, and MSN Messenger is a good example of this.  A messenger app should sit out of the way in the notification tray when it's not in use.

I found out that you can do this if you set the compatibility mode for the Messenger app to Vista, it will not take up space in your taskbar unless you're actually using it. To do this go to

32bit: C:\Program Files\Windows Live\Messenger
64bit: C:\Program Files (x86)\Windows Live\Messenger

in there, right click on msnmsgr.exe and click on properties. Select the compatibility tab, select Windows Vista as the operating system for compatibility.  Next time you open Messenger it should minimize to the tray.