我当前的项目是一个带有布尔检索功能的高级标签数据库.正在使用类似的布尔表达式查询记录(例如在音乐数据库中):
funky-music and not (live or cover)
这应该会产生音乐数据库中所有时髦的音乐,但不能播放歌曲的现场或封面版本.
当涉及到缓存时,问题是存在等同但结构不同的查询.例如,应用de Morgan的规则,上面的查询可以这样写:
funky-music and not live and not cover
例如,当通过散列查询字符串实现缓存时,它将产生完全相同的记录,但会产生中断缓存.
因此,我的第一个目的是创建查询的真值表,然后可以将其用作缓存键,因为等效表达式构成相同的真值表.不幸的是,这是不切实际的,因为真值表随着输入(标签)的数量呈指数增长,我不想限制一个查询中使用的标签数量.
另一种方法可以是遍历语法树,应用由布尔代数定义的规则来形成(最小的)规范化表示,这似乎也很棘手.
因此,整体问题是:是否有一种实用的方法来实现等效查询的识别,而无需电路最小化或真值表(编辑:或任何其他NP难的算法)？
ne plus ultra将识别已经缓存的子查询,但这不是主要目标.