нормализовать логическое выражение для кэширования.Есть ли более эффективный способ, чем таблицы истинности? - PullRequest
6 голосов
/ 01 мая 2011

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

funky-music and not (live or cover)

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

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

funky-music and not live and not cover

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

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

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

Таким образом, общий вопрос: существует ли практический способ реализовать распознавание эквивалентных запросов без необходимости минимизация схемы или таблицы истинности (редактировать: или любой другой алгоритм, который является NP-сложным)?

ne plus ultra будет распознавать уже кэшированные подзапросы, но это не является основной целью.

Ответы [ 3 ]

1 голос
/ 02 мая 2011

Вы можете преобразовать запросы в конъюнктивную нормальную форму (CNF). Это каноническое, простое представление булевых формул, которое обычно является основой для решателей SAT.

Скорее всего, у "больших" запросов будет много конъюнкций (а не много дизъюнкций), поэтому CNF должен хорошо работать.

1 голос
/ 01 мая 2011

Общий и эффективный алгоритм для определения того, эквивалентен ли запрос запросу "False", может эффективно использоваться для решения NP-завершенных задач, поэтому вы вряд ли найдете его.

Вы можете попытаться преобразовать ваши запросы в каноническую форму. Из-за вышеизложенного всегда найдутся запросы, которые очень дорого преобразовать в любую заданную форму, но вы можете обнаружить, что на практике некоторая форма работает довольно хорошо большую часть времени - и вы всегда можете отказаться на полпути через преобразование, если оно становится слишком сложным.

Вы можете посмотреть на http://en.wikipedia.org/wiki/Conjunctive_normal_form, http://en.wikipedia.org/wiki/Disjunctive_normal_form, http://en.wikipedia.org/wiki/Binary_decision_diagram.

0 голосов
/ 02 мая 2011

Алгоритм Quine-McCluskey должен достичь того, что вы ищете. Это похоже на Карты Карно, но проще реализовать в программном обеспечении .

...