[xquery-talk] Regular Expression search
jsnelson at sleepycat.com
Fri Dec 16 10:45:11 PST 2005
Martin Probst wrote:
>>>Are you sure? It's probably possible for simple cases (e.g. "Foo|Bar"),
>>>but for general regular expressions? How would you do that?
>>Sleepycat's Berkeley DB XML has what it calls a "substring" index which
>>is currently used to optimise fn:contains(), fn:starts-with() and
>>fn:ends-with(). This works by splitting the content down into sequential
>>three character segments, ie:
>>"abccccb" is split into "abc", "bcc", "ccc", "ccb"
>>This type of index could be used to optimise regular expression. If you
>>define a regular expression to match the string above, it might look
>> From this regular expression, you can see that the keys you need to
>>look up in the container are:
>>"abc" & ("bcb" | ("bcc" & "ccb") | ("bcc" & "ccc" & "ccb"))
> Interesting. Though of course the real general case for Regular
> Expressions is probably just out of reach.
Yes. This scheme is never going to be able to optimise regular
expressions with less than three sequential non-wilcard characters in
it. However I would suggest that quite often this sort of index
optimisation will be useful to real world applications.
John Snelson, Berkeley DB XML Engineer
Sleepycat Software, Inc
Contracted to Sleepycat through Parthenon Computing Ltd
More information about the talk