星期三, 4月 24, 2013

[Challenge] 從字串中產生關係樹狀結構

Beyond Relational TSQL Challenge 60

An ETL application receives product and category information in a text file. The category hierarchy is specified as a string. Your job is to read the hierarchy information and generate a relational table (result set) representing the hierarchy of categories.

  • Sample Data
Categories
---------------------------
food/biscuits/britania
food/milk
food/baby/icecream
food/baby/milk powder
detergents/liquids/handwash
  • Expected Results
id  name        parent
--- ----------- -------
1   detergents  null
2   food        null
3   liquids     1
4   baby        2
5   biscuits    2
6   milk        2
7   handwash    3
8   icecream    4
9   milk powder 4
10  britania    5
  • Rules
    1. Pay attention to the order of the output table. The "ID" values of the categories are generated in a special way. The values are ordered by "parent" and then by "name".
    2. There is no limit in the number of levels in the hierarchy.
    3. Each hierarchy node will have at most one parent.
    4. Each category ends in a terminal node of a hierachy and begins with the main parent node of the hierarchy.
    5. There will be no duplicate entries.

  • 個人解法
IF OBJECT_ID('TC60','U') IS NOT NULL BEGIN
  DROP TABLE TC60
END
GO

CREATE TABLE TC60(
  Categories VARCHAR(MAX)
)
GO

INSERT INTO TC60(Categories)
SELECT 'food/biscuits/britania' UNION ALL
SELECT 'food/milk' UNION ALL
SELECT 'food/baby/icecream' UNION ALL
SELECT 'food/baby/milk powder' UNION ALL
SELECT 'detergents/liquids/handwash' 

;
WiTH CTE AS
(
  SELECT 
    Categories , 
    CAST(NULL AS int) AS ParentStartPos ,
    CAST(NULL AS int) AS ParentEndPos ,
    CAST(1 AS int) AS StartPos , 
    CHARINDEX('/',Categories) AS EndPos , 
    0 AS lvl
  FROM TC60
  UNION ALL
  SELECT 
    Categories , 
    CAST(StartPos AS int),
    CAST(EndPos AS int),
    CAST(EndPos + 1 AS int), 
    CHARINDEX('/',Categories , EndPos + 1) , 
    lvl +1 
  FROM CTE
  WHERE EndPos > 0
)
,
CTE2 AS 
(
  SELECT Categories ,
    SUBSTRING(Categories,StartPos,ISNULL(NULLIF(EndPos,0),LEN(Categories) + 1) - StartPos) AS Child ,
    SUBSTRING(Categories,ParentStartPos, ParentEndPos - ParentStartPos) AS Parent ,
    lvl
  FROM CTE
)
,
CTE3 AS
(
  SELECT * , 
    ROW_NUMBER() OVER (ORDER BY lvl , Categories , Child) AS ID
  FROM
    (
      SELECT 
        Categories ,
        lvl , 
        Parent , 
        Child , 
        ROW_NUMBER() OVER (PARTITION BY Lvl , Parent , Child ORDER BY  Lvl , Parent , Child) AS RowNO
      FROM CTE2
    ) AS T2
  WHERE T2.RowNO = 1
)
SELECT 
  T3.id , 
  T3.Child AS name , 
  T4.id AS Parent
FROM CTE3 AS T3 
  LEFT JOIN CTE3 AS T4 ON T3.Parent = T4.child
這個挑戰題的 Solution 似乎都被隱藏起來,沒有辦法參考其他人的作法 ~~

沒有留言:

張貼留言