Построение поддерева с коррелированным агрегатом - PullRequest
Новая
       50

Построение поддерева с коррелированным агрегатом

0 голосов
/ 28 апреля 2011

Прошу прощения за смутное название. Я не мог придумать, как лучше подвести итог проблемы. У меня есть иерархическая таблица (например, ID int, ParentID int), и мне нужно создать поддерево для ID. Это тривиально делается с помощью рекурсивного CTE. Сложность состоит в том, что для каждого узла мне нужно вычислить работающее побитовое ИЛИ набора соответствующих значений, а затем побитовое ИЛИ, которое приводит к тому же значению для родительского узла. Это означает, что каждый узел наследует битовую маску своего родителя и может устанавливать свои собственные дополнительные биты. Я могу вычислить это значение в элементе анкера КТОС с использованием OUTER APPLY и методика упоминается в ранее вопрос Я спросил. К сожалению, я не могу вычислить его таким же образом в рекурсивной части CTE, потому что он использует SUM, а агрегаты там не разрешены.

Есть ли способ реструктурировать это, чтобы сделать то, что я хочу? 

declare @ID int
set @ID = 1

;with _Bits_(RowNum, BitMask) as
(
  select
    1,
    1
  union all select
    RowNum + 1,
    BitMask * 2
  from
    _bits_
  where
    RowNum < 31
),
_Tree_ as
(
  select
    a.ID,
    a.ParentID,
    b.BitMask
  from
    Tree a
    outer apply
    (
      select
        sum(distinct y.BitMask) as BitMask
      from
        BitValues x
        inner join _Bits_ y
          on (x.Value & y.BitMask) <> 0
      where
        x.ID = a.ID
    ) b
  where
    a.ID = @ID
  union all select
    a.ID,
    a.ParentID,
    c.BitMask | b.BitMask
  from
    Tree a
    inner join _Tree_ b
      on b.ID = a.ParentID
    outer apply
    (
      select
        sum(distinct y.BitMask) as BitMask
      from
        BitValues x
        inner join _Bits_ y
          on (x.Value & y.BitMask) <> 0
      where
        x.ID = a.ID
    ) c
)
select * from _Tree_

EDIT

Если это помогает осмыслить проблему: иерархия очень похожа на структуру каталогов, а битовые маски похожи на разрешения, которые наследуются от родительских папок.

Пример данных 

create table Tree (ID int primary key, ParentID int null foreign key references Tree (ID))

insert Tree values (1, null)
insert Tree values (2, 1)
insert Tree values (3, 1)

create table BitValues (ID int not null foreign key references Tree (ID), BitMask int not null)

insert BitValues values (1, 1)
insert BitValues values (2, 2)
insert BitValues values (2, 4)
insert BitValues values (3, 8)
insert BitValues values (3, 16)
insert BitValues values (3, 32)

Для @ID 1 я ожидаю, что запрос вернется: 

+----+----------+---------+
| ID | ParentID | BitMask |
+----+----------+---------+
|  1 |   NULL   |       1 |
|  2 |        1 |       7 |
|  3 |        1 |      57 |
+----+----------+---------+

Ответы [ 2 ]

0 голосов
/ 29 апреля 2011

Небольшое уточнение (ИМО) ответа Хогана: 

declare @ID int;
set @ID = 1;

with _Bits_(RowNum, BitMask) as
(
  select
    1,
    1
  union all select
    RowNum + 1,
    BitMask * 2
  from
    _bits_
  where
    RowNum < 31
),
extrarows as
(
   select t.id, null as parent, v.BitMask as total
   from tree t
   join BitValues v on t.id = v.id
   where t.id = @ID

   union all 

   select t.id, r.id, v.BitMask | r.total
   from extrarows r
   join Tree t on r.id = t.parentid
   join BitValues v on t.id = v.id
)
select a.id, a.parent, sum(distinct y.BitMask) as BitMask
from extrarows a
  inner join _Bits_ y
    on (a.total & y.BitMask) <> 0  
group by a.id, a.parent
0 голосов
/ 29 апреля 2011 
declare @ID int;
set @ID = 1;

with extrarows as
(
   select t.id, null as parent, v.BitMask as total
   from tree t
   join BitValues v on t.id = v.id
   where t.id = @ID

   union all 

   select t.id, r.id, v.BitMask | r.total
   from extrarows r
   join Tree t on r.id = t.parentid
   join BitValues v on t.id = v.id
)
select id, parent, 
  MAX(total & 1) +
  MAX(total & 2) +
  MAX(total & 4) +
  MAX(total & 8) +
  MAX(total & 16) +
  MAX(total & 32) +
  MAX(total & 128) +
  MAX(total & 256) +
  MAX(total & 512) +
  MAX(total & 1024) +
  MAX(total & 2048)  -- more if you want em.
     as BitMask 
from extrarows   
group by id, parent

Некоторые заметки:

  • Я предполагаю, что входящий @id является "корнем" дерева. (Не стесняйтесь ползти по дереву, чтобы найти начальную битовую маску корня, если это не соответствует вашим потребностям.)

  • Хотя суммирование MAX битов работает, оно может быть неэффективным для больших битовых строк по многим записям. Я не знаю, сколько у вас битов, но меньше 16 или около того, все должно быть хорошо - хотелось бы услышать о ваших выводах.

  • Для повышения производительности перейдите на пользовательский агрегат C #.

...