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

Прошу прощения за расплывчатое название. Я не мог придумать, как лучше всего резюмировать проблему. У меня есть иерархическая таблица (например, ID int, ParentID int), и мне нужно сгенерировать поддерево для ID. Это тривиально делается с помощью рекурсивного CTE. Сложность состоит в том, что для каждого узла мне нужно вычислить выполняющееся побитовое ИЛИ для набора соответствующих значений, а затем побитовое ИЛИ, которое приводит к тому же значению для родительского узла. Это означает, что каждый узел наследует битовую маску своего родителя и может устанавливать свои собственные дополнительные биты. Я могу вычислить это значение в элементе привязки 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_

РЕДАКТИРОВАТЬ

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

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

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 |
+----+----------+---------+

person Daniel    schedule 28.04.2011    source источник
comment
вы можете привести нам несколько примеров данных?   -  person Hogan    schedule 28.04.2011
comment
@Hogan: Я обновил вопрос тестовыми данными.   -  person Daniel    schedule 28.04.2011
comment
У меня есть идея, как решить эту проблему - я смогу отправить сообщение через пару часов - мне придется ехать на работу.   -  person Hogan    schedule 29.04.2011
comment
@Hogan - Круто. Я с нетерпением жду вашей идеи. Я тоже придумал решение, но это много кода. Я не могу опубликовать его, потому что он содержит конфиденциальные данные, и их слишком много, чтобы их очистить. Если вы или кто-то другой не отправите ответ в ближайшие день или два, я могу опубликовать общие шаги, которые я предпринял.   -  person Daniel    schedule 29.04.2011


Ответы (2)


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 #.

person Hogan    schedule 29.04.2011
comment
Спасибо. Я думаю, что это можно сократить еще больше, заменив MAX(total & 1) + ... на SUM(distinct BitMask) и т. Д., Как я сделал в OUTER APPLY. - person Daniel; 29.04.2011
comment
Это не сработает - если два элемента имеют один и тот же бит дважды, он будет добавлен без добавления (есть ли слово?) - Это работает в вашем, потому что вы не ленитесь с рекурсией, как я - есть дополнительные элементы с или из элементов выше - поэтому в вашем примере идентификатор данных 2 будет иметь результат 8 (будут добавлены два из 1 бита от родителя). - person Hogan; 29.04.2011
comment
Вам нужно будет использовать CTE, например _Bits_, и присоединить его к extrarows, как я присоединил его к BitValues в OUTER APPLY. Это фактически означает бит-ИЛИ уникальный список установленных битов. - person Daniel; 29.04.2011
comment
Если я вас правильно понял: не имеет значения, дублируются ли биты, так как операция ИЛИ 0..N любого одного бита дает тот же результат. - person Daniel; 29.04.2011
comment
С моим правильным запросом, с sum(distinct bitmask) он терпит неудачу. Вы можете увидеть это даже в этом небольшом тестовом примере. Если вы замените выбор на select * from extrarows, это должно быть очищено. Для идентификатора 2 он добавит 3 и 5, чтобы получить 8. - person Hogan; 29.04.2011
comment
Может, я плохо это объясняю. Я не знал, как показать вам код, поэтому опубликовал его в качестве ответа. Я получаю те же результаты, используя этот и ваш код. - person Daniel; 29.04.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
person Daniel    schedule 29.04.2011
comment
Мне было бы интересно узнать, что быстрее, это меньше печатать, но работа должна быть такой же inner join _Bits_ y on (a.total & y.BitMask) <> 0, должно быть то же количество операций, что и уродливые MAX() вызовы в моем коде. Пожалуйста, дайте нам (мне) знать, было ли еще одно выступление. - person Hogan; 29.04.2011
comment
Ваша версия примерно на 60% быстрее, но мы говорим о разнице в 8 миллисекунд для данных тестовых данных. - person Daniel; 29.04.2011
comment
Я думаю, что расходы не будут масштабироваться с набором данных. Похоже, он получил единовременный удар за построение _Bits_ CTE. - person Daniel; 29.04.2011
comment
У меня была идея, как совместить две версии, но я не смогу протестировать ее, пока не вернусь домой сегодня вечером. - person Hogan; 29.04.2011