Интернет-журнал «FORS» Архив номеров На Главную

Решение логических задач с помощью рекурсивного SQL

к.т.н. Леонид Борчук,
член RuOUG,
г.Череповец

Источник: статья предоставлена автором, 5 Апрель 2013

Содержание

  1. Дедуктивные базы данных
  2. Алгоритм вычисления наименьшей неподвижной точки
  3. Задача "Ошеломляющая головоломка"
  4. Решение задачи с использованием рекурсивных условий
    1. Формализация задачи
    2. Формирование дедуктивной БД
    3. Поиск решения
  5. Заключение

Аннотация

В задачах, подобных "головоломке Эйнштейна", основная сложность заключается в пестроте и сложности формализации условий, которые зачастую попросту сбивают с толку. Как правило, формализовать их удается с помощью логики высказываний. Однако реляционные базы данных и язык SQL, в частности, оперируют отношениями и предикатами, а не высказываниями и формулами. Выходом могло бы стать использование языка Datalog, однако он по-прежнему не находит широкого применения в промышленных системах. Вместе с тем, рекурсивные расширения языка SQL стандарта SQL:92 позволяют использовать при решении основные приемы языка Datalog. Тем самым становится возможным на основе имеющегося массива данных и известных закономерностей сделать логические выводы, получив новые данные, т.е. создать так называемую дедуктиную базу данных. В работе приведен пример решения одной частной задачи с использованием алгоритма вычисления наименьшей неподвижной точки.

  1. Дедуктивные базы данных

Дедуктивная БД — БД, состоящая из 2-х частей: экстенциональной, т.е. тех фактов, которые уже известны, и интенциональной, т.е. правил логического вывода для получения новых знаний на основе имеющихся фактов [1]. И если о работе с экстенциональной частью в реляционных базах данных накоплен огромный багаж знаний [2], то работа с интенциональной частью по-прежнему остается прерогативой научного сообщества, не находя широкого практического применения при обработке данных в реляционных СУБД. Вместе с тем, использование приемов по работе с интенциональной частью [3] может существенно сократить трудоемкость решения множества задач, требующих логических выводов, предоставив готовые инженерные приемы работы с данными. Т.е. решать такие задачи известными, заранее изученными, шаблонными методами, как это делается в дедуктивных БД, а не рассматривать каждую задачу как уникальную и требующую для своего решения особого математического аппарата.

  1. Алгоритм вычисления наименьшей неподвижной точки.

Математически как для решения рекурсивных уравнений реляционной алгебры, так и для вычисления целей Дейталога используется теория неподвижной точки [4]. Идея использования приемов по работе с интенциональной частью состоит в особым образом сформулированных рекурсивных выражений на языке SQL.

Для решения полученных на основе SQL-выражений рекурсивных уравнений используется алгоритм LFP вычисления наименьшей неподвижной точки [4]. Неформально его можно определить как итерационное вычисление рекурсивных выражений до тех пор, пока удается получить новый результат. Как только ни одно из выражений не позволяет получить новые кортежи, вычисление неподвижной точки считается завершенным, как и формирование интенциональной части на основе рекурсивных выражений.

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

  1. Задача "Ошеломляющая головоломка".

В мае 2012 года в журнале NoCOUG Iggy Fernandez опубликовал [5] интересную задачку под названием "ошеломляющая головоломка". По его словам [6], идею задания ему подсказала статья Кристофера Дейта 1995 года "Functional Dependencies are Fun: An Informal Look at the Formal World of FDs". Вот краткий перевод этого задания:

"Злая Ведьма с Запада пригласила 6-х друзей на третий ежегодный бал колдунов и волшебников. Burdock Muldoon и Carlotta Pinkstone сказали, что они бы пришли, если бы пришел Albus Dumbledore. Albus Dumbledore и Daisy Dodderidge сказали, что они бы пришли, если бы пришла Carlotta Pinkstone. Albus Dumbledore, Burdock Muldoon и Carlotta Pinkstone сказали, что они бы пришли, если бы пришла Elfrida Clagg. Carlotta Pinkstone и Daisy Dodderidge сказали, что они бы пришли, если бы пришел Falco Aesalon. Burdock Muldoon, Elfrida Clagg и Falco Aesalon сказали, что они бы пришли, если бы пришли Carlotta Pinkstone и Daisy Dodderidge (оба). Daisy Dodderidge сказала, что она бы пришла, если бы пришли Albus Dumbledore и Burdock Muldoon (оба). Определите, кого нужно убедить принять приглашение на бал Злой Ведьмы, чтобы пришли все приглашенные."

Чуть позже были опубликованы [7] пояснения к заданию и дополнительные тесты для самостоятельной проверки, которые в явном виде описывали требования к решению. Вообще говоря, эти требования были в исходном задании, но в виде неявных посылок, как это принято в подобного рода [8] логических задачах:

  • Не ограничивайте количество приглашенных;
  • Не предполагайте, что нужно убедить только одного приглашенного;
  • Не предполагайте, что каждый приглашенный упоминается только в одном условии;
  • Не предполагайте, что каждый приглашенный упоминается по меньшей мере в одном условии;
  • Не ограничивайте количество участников в условии;
  • Не предполагайте, что условия независимы;
  • Не включайте участника в решение, если его присутствие гарантируется присутствием в решении остальных участников;
  • Перечислите все решения, если их больше одного;
  • Не предполагайте, что все решения содержат одинаковое количество участников.

При формализации задачи и попытках записи решения на SQL сбивает с толку пестрота и сложнота формализации условий.

  1. Решение задачи с использованием рекурсивных условий

   4.1.  Формализация задачи

Для решения задачи необходимо как-то формализовать условия. Традиционно это делают в терминах логики высказываний.

Разберём первое предложение: "Burdock Muldoon и Carlotta Pinkstone сказали, что они бы пришли, если бы пришел Albus Dumbledore ". Обозначим:

  • В — Burdock Muldoon придёт на бал;
  • С — Carlotta Pinkstone придёт на бал;
  • А — Albus Dumbledore придёт на бал.

Из предложения мы не можем ничего сказать о взаимосвязи В и С. Но можем связать А с С и А с В. Более точно, А −> В и A −> C.

Аналогичным образом записываются в виде высказываний остальные условия. Для утверждения "Daisy Dodderidge сказала, что она бы пришла, если бы пришли Albus Dumbledore и Burdock Muldoon (оба)" условие будет выглядеть: А&M −> D.

Получим систему фактов или базу знаний. Которая составляет основу дедуктивной базы данных и с использованием которой мы далее сможем выводить новые формулы. Например, из формул A−>B и B −>C следует, что A −> C, т.е. для того, чтобы пришли A, B и C нам достаточно убедить придти только A.

Представим базу знаний в реляционном виде. Каждое высказывание может принимать значение 0 или 1 и для его представления достаточно 1 бита. В одной формуле может участвовать несколько высказываний, так что определим за каждым высказыванием своё место. 1-й бит будет отвечать за то, придёт ли B, второй — придёт ли C и т.д. Все возможные комбинации высказываний создаются скриптом

CREATE TABLE  name_combination (CODE  primary   key,
                               Description ,    lvl )   as 
SELECT   all_combinations.code,
     LISTAGG(name_decode.Description,    ',_')
     WITHIN GROUP   (ORDER BY name_decode.code ),
     COUNT(*)   AS   lvl 
FROM
     (SELECT   level   AS  code FROM DUAL CONNECT BY LEVEL <   64)
     all_combinations,
     (select    1   code , 'Burdock Muldoon'   Description   from   dual   union  all
     select     2, 'Carlotta Pinkstone'   from   dual   union   all
     select     4, 'Albus Dumbledore'     from   dual   union   all
     select     8, 'Daisy Dodderidge'     from   dual   union   all
     select    16, 'Elfrida Clagg'        from   dual   union   all
     select    32, 'Falcow Aesalon'       from   dual         ) name_decode
WHERE BITAND (all_combinations.code, name_decode.code ) > 0 
GROUP BY  all_combinations.code;

Дополнительно к кодам списка комбинаций в таблицу для удобства было добавлено поле lvl — количество истинных высказываний или количество волшебников, которые придут на бал.

Все формулы имеют вид (А&В&...) −> (C&D&...), Выражение слева от −> сохраним в поле LCODE, справа — в поле RCODE. Значения LCODE и RCODE могут быть формулой, т.е. списком волшебников.

Скрипт создания и наполнения таблицы фактов (для удобства в таблицу были добавлены правила вида A −> A):

CREATE TABLE  facts (LCODE NUMBER.CONSTRAINT LCODE_ref REFERENCES  name_combination (code), 
                     RCODE NUMBER.CONSTRAINT RCODE_ref REFERENCES  name_combination (code) );

insert   into   facts
select  (select code   from   name_combination   where   Description='Burdockw Muldoon'),
        (select code   from   name_combination   where   Description='Burdockw Muldoon')  from dual;

insert   into   facts
select  (select   code from   name_combination   where   Description='Albusw Dumbledore'),
        (select   code from   name_combination   where   Description='Albusw Dumbledore') from dual;

insert   into   facts
select  (select code   from   name_combination   where   Description='Carlottaw Pinkstone'),
        (select code   from   name_combination   where   Description='Carlottaw Pinkstone') from dual;

insert   into   facts
select  (select   code   from   name_combination   where   Description='Daisy Dodderidge'),
        (select   code   from   name_combination   where   Description='Daisy Dodderidge')  from dual;

insert   into   facts
select  (select   code   from  name_combination   where   Description='Elfridaw Clagg'),
        (select   code   from   name_combination   where   Description='Elfridaw Clagg') from dual;

insert   into   facts
select  (select  code  from   name_combination  where Description='Falco Aesalon ') ,
        (select  code  from   name_combination   where Description='Falco Aesalon')   from   dual ;

insert   into   facts
select (select  code from name_combination   where Description='Albus  Dumbledore'),
       (select  code from name_combination   where Description='Burdock Muldoon, Carlotta Pinkstone')
                                                                              from   dual;

insert   into   facts
select  (select code  from  name_combination   where Description='Carlotta Pinkstone'),
        (select code  from  name_combination   where Description='Albus Dumbledore, Daisy Dodderidge')
                                                                              from   dual;

insert   into   facts
select  (select code  from  name_combination where Description='Elfrida Clagg'), 
        (select code  from name_combination where  Description=
                              'Burdock Muldoon, Carlotta Pinkstone, Albus Dumbledore')
                                                                              from   dual;

insert   into   facts
select (select  code   from   name_combination  where   Description='Falco Aesalon'),
       (select  code   from   name_combination  where   Description=
                                 'Carlotta Pinkstone, Daisy Dodderidge')
                                                                              from   dual;

insert   into   facts
select  (select code from name_combination  where Description='Carlotta Pinkstone, Daisy Dodderidge'), 
        (select code from name_combination  where Description=
                                 'Burdock Muldoon, Elfrida Clagg, Falcow Aesalon')
                                                                              from   dual;

insert   into   facts
select  (select code from name_combination where Description='Burdock Muldoon,  Albus Dumbledore'), 
        (select code from name_combination where Description='Daisy Dodderidge')   from   dual;
commit ;

   4.2.  Формирование дедуктивной БД

После такой основательной подготовки можно приступать к решению задачи (формально, можно было бы не создавать структуры данных, а прописать их прямо в секции with, но это ничего нового в решение не добавит).

Во первых, хотелось бы научиться выводить новые формулы и таким образом формировать дедуктивную базу данных. Делается это традиционно с использованием теоремы о центральной точке, которая реализуется с использованием рекурсивного with. Технически это означает, что таблица соединяется сама с собой и таблицей фактов до тех пор, пока в ней появляются новые строки. На языке SQL это записывается как:

WITH cycle_tree (lcode, rcode, mark) AS
  (SELECT lcode, rcode, 0 AS mark FROM facts WHERE lcode = 2
  UNION ALL
  SELECT cycle_tree.lcode,
    facts.rcode,
    mark + 1
  FROM facts.rcode,
    cycle_tree
  WHERE bitand (facts.lcode, cycle_tree.rcode) = facts.lcode
  ) CYCLE lcode,rcode
  SET is_cycle TO 'Y' DEFAULT 'N'
SELECT * FROM cycle_tree

Результат выполнения запроса:

№ lcodercodemark is cycle
1 220 N
2 2120 N
3 221 Y
4 2121 N
5 241 N
6 281 N
7 231 N
8 242 N
... ......... ...

Однако вывод этого запроса достаточно обширен и некоторые строки встречаются в нём несколько раз, т.к. одну и ту же формулу можно вывести разными способами. Так, строки 3 и 4 дублируют строки 1 и 2. Строка 3 была получена из строки 1 путем применения правила вывода 2 −> 2, что является циклом, о чем нам и сигнализирует значение поля is_cycle. Строка же 4 была получена применением к строке 1 правила 2 −> 12. И хотя такое правило уже встречается ранее, формально это новое правило, полученное путем применения цепочки правил 2 −> 2 −> 12.

Нас же интересуют только новые формулы, а путь ввода неинтересен, так что добавляем условие bitand(facts.rcode,cycle_tree.rcode) != facts.rcode, говорящее о том, что в правиле есть новые волшебники, в рекурсивную часть запроса:

union    all
select   cycle_tree.lcode,   facts.rcode,   mark +  1   from   facts, cycle_tree
where   bitand (facts.lcode, cycle_tree.rcode)   =  facts.lcode
and   bitand(facts.rcode,cycle_tree.rcode)   !=   facts.rcode

Для Carlotta Pinkstone получим такой результат:

№ lcodercodemark is cycle
1 220 N
2 2120 N
3 2121 N
4 231 N
5 232 N
6 2122 Y
7 2123 Y

В выводе по-прежнему есть циклы и некоторые строки повторяются, хотя теперь повторяющихся строк значительно меньше. Например, из 1-й строки сформировалась 3-я, хотя она уже была известна на 0-м цикле. Избежать повторений позволяет группировка. Действительно, если сложить все строки 0-го цикла, то получим маску 001110 и для этой маски уже правильно сработает условие bitand(facts.rcode,cycle_tree.rcode) != facts.rcode и отсечёт все уже выведенные ранее формулы. Кроме того, группировка нужна для того, чтобы имея на шаге 0 маски 001100 и 000010, стало возможным использовать на шаге 1 правило вывода 001010. В запросе выше такие правила вывода использованы быть не могут.

Сложение выполняется группировкой, однако здесь есть 2 проблемы, из-за которых напрямую выполнить группировку невозможно:

  1. Складывать нужно функцией OR. В Oracle Database такой функции нет, поэтому была изобретена конструкция из max и bitand, реализующая сходный с OR алгоритм работы:
    2. select  lcode, max(bitand (rcode,1)) 
          + max( bitand (rcode,2 )) + max( bitand(rcode,4)) + max( bitand(rcode,8)) 
          + max( bitand(rcode,16))  + max(bitand(rcode,32)) as   rcode 
     from   facts where   lcode  = 2 group   by   lcode;
  2. Рекурсивное выражение не может содержать следующих элементов:
    • Выражений DISTINCT или GROUP BY;
    • Выражений model;
    • Функций агрегации.

Однако можно использовать:

  • аналитические функции;
  • Подзапросы, содержащие рекурсивную таблицу;
  • Внешние соединения, в правой части которых упоминается рекурсивная таблица.

Надежду дают только аналитические функции. Как реализовать операцию группировки с помощью аналитических функций? Использовать какой-нибудь признак конца расчёта аналитики, т.к. в самой последней строке и будет искомое итоговое значение. В результате в запрос добавилась следующая конструкция:

select ...
+ MAX(decode(bitand(facts.rcode,2),2,2,bitand(cycle_tree.mask,2))) over (partition BY cycle_tree.lcode
                    order by facts.rcode) + ... as mask,
lead(facts.rcode, 1, null) over (partition by cycle_tree.lcode order by facts.rcode) as mark2
from facts,cycle_tree
where ...
and cycle_tree.mark2 is null

Здесь mark2 — признак конца группы.

Итого запрос по расчёту дедуктивной базы данных стал выглядеть так:

WITH cycle_tree(lcode, rcode, real_lcode, mark, mask, mark2) AS
  (SELECT lcode,
    rcode,
    rcode,
    0 AS mark,
      MAX(bitand(rcode,1)) over (partition BY lcode order by rcode)
    + MAX(bitand(rcode,2)) over (partition BY lcode order by rcode)
    + MAX(bitand(rcode,4)) over (partition BY lcode order by rcode)
    + MAX(bitand(rcode,8)) over (partition BY lcode order by rcode)
    + MAX(bitand(rcode,16))over (partition BY lcode order by rcode)
    + MAX(bitand(rcode,32)) over (partition BY lcode order by rcode) AS mask,
    lead(rcode, 1, NULL) over (partition BY lcode order by rcode)    AS mark2
  FROM facts
  UNION ALL
  SELECT cycle_tree.lcode,
    facts.rcode,
    facts.lcode,
    mark + 1,
      MAX(decode(bitand(facts.rcode,1),1,1,bitand(cycle_tree.mask,1))) over 
                  (partition BY cycle_tree.lcode order by facts.rcode)
    + MAX(decode(bitand(facts.rcode,2),2,2,bitand(cycle_tree.mask,2))) over 
                  (partition BY cycle_tree.lcode order by facts.rcode)
    + MAX(decode(bitand(facts.rcode,4),4,4,bitand(cycle_tree.mask,4))) over 
                  (partition BY cycle_tree.lcode order by facts.rcode)
    + MAX(decode(bitand(facts.rcode,8),8,8,bitand(cycle_tree.mask,8))) over 
                  (partition BY cycle_tree.lcode order by facts.rcode)
    + MAX(decode(bitand(facts.rcode,16),16,16,bitand(cycle_tree.mask,16)))over 
                  (partition BY cycle_tree.lcode order by facts.rcode)
    + MAX(decode(bitand(facts.rcode,32),32,32,bitand(cycle_tree.mask,32))) over 
                  (partition BY cycle_tree.lcode order by facts.rcode) AS mask,
    lead(facts.rcode, 1, NULL) over (partition BY cycle_tree.lcode order by facts.rcode)  
                  AS mark2
  FROM facts,
    cycle_tree
  WHERE bitand(facts.lcode,cycle_tree.mask) = facts.lcode
  AND bitand(facts.rcode,cycle_tree.mask)   != facts.rcode
  AND cycle_tree.mark2                     IS NULL)
  CYCLE lcode, rcode  SET is_cycle TO 'Y' DEFAULT 'N'
select * from cycle_tree;

В результатах этого запроса уже нет лишних строк, а столбцы представляют собой:

  • lcode — кому посылают приглашение; rcode кто пойдет;
  • real_lcode — какое правило было использовано для вывода новой формулы;
  • mark — шаг вывода, 0 означает формулы таблицы фактов, т.е. исходные данные;
  • mask — расчёт нового значения rcode; mark2 признак окончания расчёта;
  • is_cycle — признак цикла.

Отсутствие циклов в процессе вывода означает, что мы правильно реализовали алгоритм. Тот же самый вывод для Carlotta Pinkstone теперь будет выглядит так:

№ lcodercodereal_lcodemarkmaskmark2 is cycle
12220212N
2 21212014 N
3 23411549N
4 24910163 N

   4.3.  Поиск решения

Дедуктивная база данных — это еще не решение задачи. Весь процесс вывода для ответа на вопрос в действительности не нужен, а нужны только итоговые значения для каждого уникального правила таблицы фактов, так что группируем результат:

reach_tree   as
(select  lcode, max(mask) as mask, max(mark) as  mark from cycle_tree   group by lcode)

Далее, что мы получили к этому моменту. Для каждого уникального кода lcode из таблицы фактов мы вывели, кто согласится пойти на бал, если пойдёт lcode. Важно, что это не только отдельные волшебники, но и более сложные случаи, когда непременно должна пойти пара, тройка и т.д. волшебников, т.е. для всех уникальных комбинаций левой части формул списка фактов.

Осталось выполнить этап перебора вариантов. Мы пробуем посылать все возможные комбинации приглашений. Для каждой комбинации суммируем список тех, кто придёт. На SQL это записывается так:

perm_tree AS
  (SELECT code,
    MAX(description) AS dsc,
    MAX(lvl)         AS lvl,
    MAX(mark)        AS mark,
    MAX(bitand(mask,1)) + MAX(bitand(mask,2)) + MAX(bitand(mask,4)) + MAX(bitand(mask,8)) 
  + MAX(bitand(mask,16)) + MAX(bitand(mask,32)) AS mask
  FROM name_combination,
    reach_tree
  WHERE bitand(reach_tree.lcode,name_combination.code) = reach_tree.lcode
  GROUP BY code)

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

SELECT *
FROM perm_tree a
WHERE mask = 63
AND NOT EXISTS
  (SELECT 1
  FROM perm_tree b
  WHERE b.mask               =63
  AND a.code                != b.code
  AND bitand(a.code, b.code) = b.code
  )
ORDER BY mark ASC

Результатом решения задачи будет таблица:

CodeDesclvl markmask
2Carlotta Pinkstone1 163
32 Falco Aesalon11 63
16Elfrida Clagg 12 63
4 Albus Dumbledore12 63

В ней каждая строчка представляет собой один из вариантов рассылки приглашений. Т.е. нам достаточно послать приглашение Albus Dumbledore или Carlotta Pinkstone или... Поле mark показывает, как быстро остальные волшебники согласятся пойти. Всё-таки некоторые из них весьма сварливы и хотят, чтобы их немного поуговаривали. Итоговое решение:

WITH cycle_tree(lcode, rcode, real_lcode, mark, mask, mark2) AS
  (SELECT lcode,
    rcode,
    rcode,
    0 AS mark,
      MAX(bitand(rcode,1)) over (partition BY lcode order by rcode)
    + MAX(bitand(rcode,2)) over (partition BY lcode order by rcode)
    + MAX(bitand(rcode,4)) over (partition BY lcode order by rcode)
    + MAX(bitand(rcode,8)) over (partition BY lcode order by rcode)
    + MAX(bitand(rcode,16))over (partition BY lcode order by rcode)
    + MAX(bitand(rcode,32)) over (partition BY lcode order by rcode) AS mask,
    lead(rcode, 1, NULL) over (partition BY lcode order by rcode)    AS mark2
  FROM facts
  UNION ALL
  SELECT cycle_tree.lcode,
    facts.rcode,
    facts.lcode,
    mark + 1,
      MAX(decode(bitand(facts.rcode,1),1,1,bitand(cycle_tree.mask,1))) over 
                  (partition BY cycle_tree.lcode order by facts.rcode)
    + MAX(decode(bitand(facts.rcode,2),2,2,bitand(cycle_tree.mask,2))) over 
                  (partition BY cycle_tree.lcode order by facts.rcode)
    + MAX(decode(bitand(facts.rcode,4),4,4,bitand(cycle_tree.mask,4))) over 
                  (partition BY cycle_tree.lcode order by facts.rcode)
    + MAX(decode(bitand(facts.rcode,8),8,8,bitand(cycle_tree.mask,8))) over 
                  (partition BY cycle_tree.lcode order by facts.rcode)
    + MAX(decode(bitand(facts.rcode,16),16,16,bitand(cycle_tree.mask,16)))over 
                  (partition BY cycle_tree.lcode order by facts.rcode)
    + MAX(decode(bitand(facts.rcode,32),32,32,bitand(cycle_tree.mask,32))) 
                  over (partition BY cycle_tree.lcode order by facts.rcode) AS mask,
    lead(facts.rcode, 1, NULL) over (partition BY cycle_tree.lcode order by facts.rcode)  
                  AS mark2
  FROM facts,
    cycle_tree
  WHERE bitand(facts.lcode,cycle_tree.mask) = facts.lcode
  AND bitand(facts.rcode,cycle_tree.mask)   != facts.rcode
  AND cycle_tree.mark2                     IS NULL)
  CYCLE lcode, rcode  SET is_cycle TO 'Y' DEFAULT 'N',
reach_tree as
(select lcode, max(mask) as mask, max(mark) as mark from cycle_tree group by lcode),
perm_tree as
(select code, max(description) as dsc, max(lvl) as lvl, max(mark) as mark,
max(bitand(mask,1)) + max(bitand(mask,2)) + max(bitand(mask,4)) + max(bitand(mask,8)) 
                    + max(bitand(mask,16)) + max(bitand(mask,32)) as mask
from name_combination, reach_tree
where bitand(reach_tree.lcode,name_combination.code) = reach_tree.lcode
group by code)
SELECT *
FROM perm_tree a
WHERE mask = 63
AND NOT EXISTS
(select 1 from perm_tree b where b.mask=63 and a.code != b.code and bitand(a.code, b.code) = b.code)
ORDER BY mark ASC;
  1. Заключение

Задача в исходной формулировке NP-трудна по входу. Действительно, нет никаких ограничений на количество записей таблицы фактов. Так что для n волшебников можно сформулировать 2^n правил. Без каких-либо дополнительных ограничений улучшить предложенное выше решение невозможно.

Впрочем, это не означает, что не существует лучших решений этой конкретной задачи. По результатам соревнований [6] лучшим решением было признано решение Lukasz Pluta, рекурсивно вычитающее по одному приглашенному, пока еще удается улучшить результат. А можно вообще подойти к проблеме системно и использовать математические методы [9]. Ценность использования дедуктивной базы данных состоит в простоте проверки правильности вывода, гибкости модели и универсальности подхода. Что может быть особенно актуально на этапах формализации задачи и построения прототипа будущего промышленного решения.

Список литературы

[1] Кузнецов, С.Д. Основы современных баз данных, http://citforum.ru/ database/osbd/contents.shtml

[2] Matthias Jarke, Jurgen Koch. Query Optimization in Database Systems. Computing Surveys, Vol. 16, No. 2, June 1984

[3] Datalog https://en.wikipedia.org/wiki/Datalog

[4] Марков А.С, Лисовский К.Ю. Базы данных. Введение в теорию и методологию, ISBN: 978-5-279-02298-4

[5] NoCOUG Jornal vol. 26, May 2012, http://www.nocoug.org/Journal/ NoCOUG_Journal_201205.pdf">

[6] Results of the Third International NoCOUG SQL Challenge http://iggyfernandez.wordpress.com/2012/ll/19/results-of-the-third-international-nocoug-sql-challenge

[7] Additional rules to the challenge

[8] Задача Эйнштейна

[9] Lukasz Wycislik, Lukasz Warchal: Using Oracle 11.2g Database Server in Social Network Analysis Based on Recursive SQL. CN 2012:139-143 http://link.springer.com