CODEWITHSUNDEEP
sqlsql-servertreesql-server-2012
David S.
David S.

Reputation: 6105

Find the common ancestor in a tree-structured table

I have a table structure like this (there are actually more levels):

------------------------------------------
|region1|region2|region3|region4|postcode|
|-------|-------|-------|-------|--------|
|a      |x      |i      |       |1       |
|a      |y      |i      |       |2       |
|a      |y      |j      |       |2       |
|a      |z      |k      |       |3       |
|b      |u      |m      |       |4       |
|b      |       |n      |       |4       |
|c      |       |       |       |5       |
|c      |q      |       |       |6       |
------------------------------------------

So for example, a => x => i and a => y => i are different places but both are in the same region1 a.

I want to know which region each postcode can cover.

For example, code 2 covers areas a => y => i and a => y => j, so the common ancestor for those are a => y.

Here is the desired output of the query run on the example:

------------------------------------------
|postcode|region1|region2|region3|region4|
|--------|-------|-------|-------|-------|
|1       |a      |x      |i      |       |
|2       |a      |y      |       |       |
|3       |a      |z      |k      |       |
|4       |b      |       |       |       |
|5       |c      |       |       |       |
|6       |c      |q      |       |       |
------------------------------------------

I don't really know how to attack this problem. I thought about partitioning by the postcode, but that still leaves the problem of finding the common ancestor within each partition...

Upvotes: 1

Views: 108

Answers (2)

Elliveny
Elliveny

Reputation: 2203

This question rather intrigued me and I came up with an alternative, which you might find useful:

-- Setup test table
DECLARE @InputTable TABLE (region1 varchar(2), region2 varchar(2), region3 varchar(2), region4 varchar(2), postcode varchar(2))

INSERT INTO @InputTable (region1, region2, region3, region4, postcode)
          SELECT 'a','x','i',null,'1' 
UNION ALL SELECT 'a','y','i',NULL,'2'
UNION ALL SELECT 'a','y','j',NULL,'2'
UNION ALL SELECT 'a','z','k',NULL,'3'
UNION ALL SELECT 'b','u','m',NULL,'4'
UNION ALL SELECT 'b',NULL,'n',NULL,'4'
UNION ALL SELECT 'c',NULL,NULL,NULL,'5'
UNION ALL SELECT 'c','q',NULL,NULL,'6'

-- Find the common ancestors
;with totals as (
  select postcode, count(*) as postcodeCount from @InputTable group by postcode
)
, region4group as (
  select postcode, region1, region2, region3, region4 from @InputTable in1 
  group by postcode, region1, region2, region3, region4 having count(*)=(select postCodeCount from totals where totals.postcode=in1.postcode)
)
, region3group as (
  select * from region4group
  union
  select in1.postcode, in1.region1, in1.region2, in1.region3, null from @InputTable in1 
  left outer join region4group on region4group.postcode=in1.postcode
  where region4group.postcode is null
  group by in1.postcode, in1.region1, in1.region2, in1.region3 
  having count(*)=(select postCodeCount from totals where totals.postcode=in1.postcode)
)
, region2group as (
  select * from region3group
  union
  select in1.postcode, in1.region1, in1.region2, null, null from @InputTable in1
  left outer join region3group on region3group.postcode=in1.postcode
  where region3group.postcode is null
  group by in1.postcode, in1.region1, in1.region2 
  having count(*)=(select postCodeCount from totals where totals.postcode=in1.postcode)
)
, commonancestors as (
  select * from region2group
  union
  select in1.postcode, in1.region1, null, null, null from @InputTable in1 
  left outer join region2group on region2group.postcode=in1.postcode
  where region2group.postcode is null
  group by in1.postcode, in1.region1 
  having count(*)=(select postCodeCount from totals where totals.postcode=in1.postcode)
)
select * from commonancestors

Upvotes: 1

Alan
Alan

Reputation: 3002

This is a really messy solution, but it does seem to give the correct answer. It would no doubt need quite a bit of work to fit your actual requirement, but maybe this could help point you in some sort of direction!

-- Setup a test table

DECLARE @tbl AS TABLE(R1 NVARCHAR(10), R2 NVARCHAR(10), R3 NVARCHAR(10), R4 NVARCHAR(10), PC NVARCHAR(10));

INSERT INTO @tbl(R1,R2,R3,R4,PC) VALUES ('a','x','i',NULL,'1');
INSERT INTO @tbl(R1,R2,R3,R4,PC) VALUES ('a','y','i',NULL,'2');
INSERT INTO @tbl(R1,R2,R3,R4,PC) VALUES ('a','y','j',NULL,'2');
INSERT INTO @tbl(R1,R2,R3,R4,PC) VALUES ('a','z','k',NULL,'3');
INSERT INTO @tbl(R1,R2,R3,R4,PC) VALUES ('b','u','m',NULL,'4');
INSERT INTO @tbl(R1,R2,R3,R4,PC) VALUES ('b',NULL,'n',NULL,'4');
INSERT INTO @tbl(R1,R2,R3,R4,PC) VALUES ('c',NULL,NULL,NULL,'5');
INSERT INTO @tbl(R1,R2,R3,R4,PC) VALUES ('c','q',NULL,NULL,'6');

-- Calculate the result:

SELECT 
    PC,
    CASE WHEN LVL1 = 1 THEN R1 ELSE NULL END AS R1,
    CASE WHEN LVL2 = 1 THEN R2 ELSE NULL END AS R2,
    CASE WHEN LVL3 = 1 THEN R3 ELSE NULL END AS R3,
    CASE WHEN LVL4 = 1 THEN R4 ELSE NULL END AS R4
FROM
(
    SELECT
      PC,
      MAX(R1) AS R1, 
      MAX(R2) AS R2,
      MAX(R3) AS R3, 
      MAX(R4) AS R4,
      COUNT(DISTINCT ISNULL(R1,'.')) AS LVL1, 
      COUNT(DISTINCT ISNULL(R1,'.') + ISNULL(R2,'.')) AS LVL2, 
      COUNT(DISTINCT ISNULL(R1,'.') + ISNULL(R2,'.') + ISNULL(R3,'.')) AS LVL3,
      COUNT(DISTINCT ISNULL(R1,'.') + ISNULL(R2,'.') + ISNULL(R3,'.') + ISNULL(R4,'.')) AS LVL4
    FROM @tbl
    GROUP BY PC
) A

The end result matches the table in the question.

Upvotes: 2

Related Questions