Suppose you have a large set of queries (could be in SQL form, but conceivably the same problem exists for search engine query strings or Lucene expressions, etc...) stored and you want to know which of these queries matches a specific object X: is there a general approach to this problem? Naive implementation would of course be to iterate over all queries, execute them and see if object X is an element of the results found. I expect that a solution would consist of using the indexes that are useful for the operation query -> results to perform the result -> queries search to find a small superset of the correct set of queries.
Searching for matching queries
ds.algorithms;descriptive complexity;db.databases;finite model theory
Place all the queries in conjunctive normal form. Decompose the set of CNF queries into a tree (with the head simply being True), where each terminating node is labeled with the query that path represents. We now only needs to walk further down those branches of the tree for which the head is satisfied.This creates a new question -- by which criteria can we judge which trees are better than others? I tend to think a greedy algorithm will give a good approximation for minimum nodes (if the remainder of clauses of a given query are unique, they can of course be packed into a single node), but more interesting would be something which took into account the expected distribution of inputs.That's for the general case of boolean formulas, of course. For any specific type of query, such as just substrings, I imagine there would be various things that can be done.Edit: In fact, for queries (or portions of queries) which can be represented as regular expressions, one can use the techniques presented in A Play on Regular Expressions and take the union of these regular expressions over a semiring which counts matches to each original query.