为缓存原因规范化布尔表达式.有没有比真值表更有效的方法？

Question

我当前的项目是一个带有布尔检索功能的高级标签数据库.正在使用类似的布尔表达式查询记录(例如在音乐数据库中):

funky-music and not (live or cover)

这应该会产生音乐数据库中所有时髦的音乐,但不能播放歌曲的现场或封面版本.

当涉及到缓存时,问题是存在等同但结构不同的查询.例如,应用de Morgan的规则,上面的查询可以这样写:

funky-music and not live and not cover

例如,当通过散列查询字符串实现缓存时,它将产生完全相同的记录,但会产生中断缓存.

因此,我的第一个目的是创建查询的真值表,然后可以将其用作缓存键,因为等效表达式构成相同的真值表.不幸的是,这是不切实际的,因为真值表随着输入(标签)的数量呈指数增长,我不想限制一个查询中使用的标签数量.

另一种方法可以是遍历语法树,应用由布尔代数定义的规则来形成(最小的)规范化表示,这似乎也很棘手.

因此,整体问题是:是否有一种实用的方法来实现等效查询的识别,而无需电路最小化或真值表(编辑:或任何其他NP难的算法)？

ne plus ultra将识别已经缓存的子查询,但这不是主要目标.

Answer 1

一种确定查询是否等价于“False”的通用且高效的算法可用于有效地解决 NP 完全问题，因此您不太可能找到一个算法。

您可以尝试将查询转换为规范形式。由于上述原因，总会有一些查询转换成任何给定的形式都非常昂贵，但您可能会发现，在实践中，某些形式在大多数情况下都工作得很好 - 并且您总是可以中途放弃如果转型变得太难。