THE SQL Server Blog Spot on the Web

Welcome to SQLblog.com - The SQL Server blog spot on the web Sign in | |
in Search

Microsoft OLAP by Mosha Pasumansky

Finding lowest common ancestor in set

This thread on MSDN forums asks seemingly easy question – given a multiple selection of elements in the parent-child hierarchy – how to find lowest common ancestor among them ? While it is fairly easy to do using stored procedure, it turned out to be far from trivial using pure MDX. Here is my solution to this puzzle, it isn’t fully optimized, I cared more to keep it simple to understand instead.

Below is my solution, applied to the example of set

{
  [Employee].[Employees].&[289]
 ,[Employee].[Employees].&[281]
 ,[Employee].[Employees].&[296]
}

The right answer for this example is Brian Welcker (of Reporting Services fame). If you have simpler or more elegant solution – I invite the competition ! My solution follows:

WITH 
  // This is example set 
  SET SelectedEmployees AS 
    {
      [Employee].[Employees].&[289]
     ,[Employee].[Employees].&[281]
     ,[Employee].[Employees].&[296]
    }
  // We compute the highest level in the set, since
  // lowest common ancestor has to be at or above this level
  MEMBER HighLevel AS 
    Min
    (
      SelectedEmployees
     ,[Employee].[Employees].CurrentMember.Level.Ordinal
    ) 
  // Set of all common ancestors
  SET CommonAncestors AS 
    Filter
    (
      // go over ancestors of the first element in the set
      Ascendants(SelectedEmployees.Item(0)) AS iter
     ,
        // discard those below lowest possible common level
        [Employee].[Employees].CurrentMember.Level.Ordinal <= HighLevel
      AND 
        // Check that all the ancestors at given level
        // are the same
          Generate
          (
            SelectedEmployees
           ,Ancestors
            (
              [Employee].[Employees].CurrentMember
             ,iter.Current.Item(0).Level
            )
          ).Count
        = 1
    )
  // Pick lowest common ancestor among all common ancestors
  SET LowestCommonAncestor AS 
    // get first element
    Head
    (
      // ...of the reversed hierarchization
      Hierarchize
      (
        CommonAncestors
       ,POST
      )
     ,1
    )
SELECT 
  LowestCommonAncestor ON 0
FROM [Adventure Works];

Update: Gerhard Brueckl has offered another, more elegant solution. It has clever use of the fact that EXISTING over the parent-child hierarchy is going to bring all of the ancestors too, so there is no need to do extra Generate(…, Ascendants()). Here is Gerhard solution:

WITH 
  SET selected_employees AS 
    {(EXISTING [Employee].[Employees].MEMBERS)}
  SET common_ancestors AS 
    {
      Filter
      (
        selected_employees
       ,
          Intersect
          (
            [Employee].[Employees].CurrentMember.Level.MEMBERS
           ,selected_employees
          ).Count
        = 1
      )
    }
  MEMBER [Measures].LCA AS 
    Tail
    (
      common_ancestors
     ,1
    ).Item(0).Name 
SELECT 
  [Measures].LCA ON COLUMNS
FROM [Adventure Works]
WHERE 
  {
    [Employee].[Employees].&[289]
   ,[Employee].[Employees].&[281]
   ,[Employee].[Employees].&[296]
  };
Published Tuesday, September 02, 2008 10:02 PM by mosha
Anonymous comments are disabled
Powered by Community Server (Commercial Edition), by Telligent Systems
  Privacy Statement