在Postgres中检查`LIKE`模式是否相交

Question

在某些请求中有两个字符串是模式，这些模式在LIKE表达式中使用（带有_和%占位符）。我想找出这些模式是否相交（是否有一些字符串与它们都匹配）。有没有办法做到这一点？...

“Like模式”对应于有限或无限的字符串集合。该集合中的每个字符串都与给定模式匹配。我想检查两个给定模式的字符串集合的交集是否为空。因此最好说模式的连接。用数学语言来说：

S-字符串集合 P-模式集合（其中每个模式都有一个或多个字符串表示） Si-子字符串集合（Si ⊂ S），其匹配pi模式（其中i可以是任何索引）。 等式形式：“Sᵢ = {s | s ∈ S, s matches pᵢ, pᵢ ∈ P}”即：“Sᵢ是字符串元素的集合，且与pᵢ模式匹配”。 另一种符号表示法：“Sᵢ ⊂ S，∀pᵢ ∈ P，∀s ∈ S（s matches pᵢ ≡ s ∈ Sᵢ）”，即：“Sᵢ是字符串的子集，如果它与pᵢ模式匹配，则任何字符串都是Sᵢ的元素”。

让我们定义模式的连接：“p₁ ∧ p₂ = p₃ ≡ S₁ ∩ S₂ = S₃”，这意味着：“与模式p₁和p₂的连接匹配的字符串集合是匹配p₁模式的字符串集合和匹配p₂模式的字符串集合的交集”。

例如： ab_d和%cd-相交 k%n和kl___-相交

- Timofey Gorshkov

---

你想知道它们在给定的字符串上是否相交，还是在已知的一组字符串上实际相交吗？ - Klas Lindbäck

要对一个字符串进行多个模式的测试，可以使用 LIKE ALL，例如：SELECT 'comm' LIKE ALL (ARRAY['_omm', 'co%']);。然而，找出任何两个模式是否有一个或多个字符串都匹配这两个模式...那就很难了。一种方法可能是从一个模式中创建候选字符串，并将其与另一个模式进行匹配，但这会相当缓慢和不完美。我怀疑你不会轻易在SQL中解决这个问题。 - Craig Ringer

在我的回答中（我现在已经删除了），Errandir发表了评论：“但是是否可能存在一个与'_omm'和'co％'相交而不是'comm'的'%mm'字符串？”我不明白你在问什么。您是否要查找仅匹配一个公共字符串的模式，其中没有两个或更多的字符串同时匹配？请编辑您的问题以更好地解释您的问题，并添加更多符合您想要实现规则的模式示例和不匹配的模式示例 - 以及原因。 - Craig Ringer

你能定义一下“交集”吗？a% 与 %b 会有交集吗？我问这个问题是因为你的例子中都有非占位符。如果有，那么我们是否可以假设 % 与所有内容都有交集？ - Chris Travers

@ChrisTravers 是的：a% ∧ %b = a%b ≠ ∅。其中 ∅ 表示没有与之匹配的字符串的模式。 - Timofey Gorshkov

Answer 1

我希望找到这些模式是否相交（有一些字符串与它们匹配）。有没有办法做到这一点？... (...) 我想检查给定两个模式的字符串集的交集是否不为空。

所以，如果我理解正确，给定两个类似的模式p1和p2，您想知道是否存在一个（尚未确定）字符串既与p1匹配又与p2匹配。

E.g.:

select check_pattern('a%', 'b_'); -- false
select check_pattern('a%', '_b'); -- true ('ab')

您确定首先有这个问题的一般解决方案吗？

假设存在，纯SQL不是找到解决方案的正确工具，因为您无法轻松地用“这是我的（有限）数据集，连接/筛选它们并基于此产生一个集合”的术语来表达这一点。 要以SQL术语找到解决方案，您需要生成源自您的数据的集合，而当涉及到无限集时，显然这不是一个选项。

我认为您希望将问题分解成较小的部分，并使用过程语言（如C，Perl，Lisp等）。

一个潜在的解决方案可能是：

• 如果p1和p2两端都是开放的或者不同的端点，那么答案显然是肯定的：匹配“%foo%”的字符串将与匹配“%bar%”的字符串相交，就像匹配“foo%”的字符串将与匹配“%bar”的字符串相交一样。

• 如果p1产生一个有限集合（即它不包含%），你可以想象使用generate_series()或for/while/whatever循环迭代p1的所有潜在匹配，并在每个字符串上尝试p2。这很丑陋而低效，但最终可以解决问题。

• 如果p1和p2都是锚定的（例如abc%和def%或%abc和%def），或者相对锚定的（例如_abc%和abcd%），则通过考虑锚定部分并按照前面的情况进行操作，解决方案也是显而易见的。

• 如果还有其他情况，请列举并解决...

我认为关键在于确定模式中锚定部分产生的有限字符串集，并坚持检查它们匹配的（有限）字符串集是否相交。

- Denis de Bernardy