Comparing SQL LIKE patterns

[Guest_imported]

Is there any algorithm or function that will indicate
whether or not two search patterns (that may be used in a
LIKE instruction) such as "ab%g_" and "a%cg%" are
compatible? That is, to determine whether the set of all
results possible with one pattern is a subset of all
possible results of the other?

 

[carp]

SELECT count(*) FROM my_table
WHERE
(the_column LIKE 'ab%g_'
AND the_column NOT LIKE 'a%cg%')
OR
(the_column NOT LIKE 'ab%g_'
AND the_column LIKE 'a%cg%')

Any non-zero response indicates the two strings are not equivilent

 

[Guest_imported]

Thanks for the reply, Carp, but I should have made my question clearer. I want to determine on an abstract level (just by comparing the characters in the two pattern strings) whether or not the set of all POSSIBLE records which fit one pattern is a subset all POSSIBLE records which fit the other pattern. I have come up with a way to do this as long as no more than one % appears in each pattern, but I know of no way to handle the comparison when one or both of the patterns has more than one % in it

 

[carp]

Ah! I think we spent several weeks on that problem during a Programming Languages Theory course I took for my Masters degree. It is NOT a simple answer (as you're probably discovering!).

 

[karluk]

Hmm, this could be a fun problem. In the example you give it seems clear that neither "ab%g_" nor "a%cg%" is a subset of the other. "a%cg%" can have any value at all as the second character, so it's not a subset of "ab%g_", which requires "b" as the second character. Likewise "ab%g_" can have any character at all preceding the "g", so it's not a subset of "a%cg%", which requires a "c" immediately before the "g".

The question is whether this kind of ad hoc reasoning about specific strings can be coded into a general algorithm for all possible strings. I'm not a theoretical computer scientist, so I don't know. I'll give the matter some thought and let you know if I come up with any ideas.