Мой текущий проект - это расширенная база данных тегов с булевыми функциями поиска.Записи запрашиваются с помощью булевых выражений, таких как (например, в музыкальной базе данных):
funky-music and not (live or cover)
, которые должны давать всю классную музыку в музыкальной базе данных, но не живую или кавер-версии песен.
Когда дело доходит до кеширования, проблема в том, что существуют запросы, которые эквивалентны, но различаются по структуре.Например, применяя правило де Моргана, вышеприведенный запрос может быть записан так:
funky-music and not live and not cover
, что приведет к точно таким же записям, но с кэшированием разрыва причины, когда кэширование будет реализовано путем хеширования строки запроса, например..
Таким образом, мое первое намерение состояло в том, чтобы создать таблицу истинности запроса, которую затем можно было бы использовать в качестве ключа кэширования, поскольку эквивалентные выражения образуют одну и ту же таблицу истинности.К сожалению, это неосуществимо, так как таблица истинности растет экспоненциально с количеством входов (тегов), и я не хочу ограничивать количество тегов, используемых в одном запросе.
Другим подходом может быть обход дерева синтаксиса.применение правил, определенных булевой алгеброй, для формирования (минимального) нормализованного представления, что тоже кажется хитрым.
Таким образом, общий вопрос: существует ли практический способ реализовать распознавание эквивалентных запросов без необходимости минимизация схемы или таблицы истинности (редактировать: или любой другой алгоритм, который является NP-сложным)?
ne plus ultra будет распознавать уже кэшированные подзапросы, но это не является основной целью.