2
$\begingroup$

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.

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ I believe you have better chances to get answers on stackoverflow.com $\endgroup$
    – Radu GRIGore
    Jan 10, 2011 at 12:59
  • 1
    $\begingroup$ It seems to me that theoretically this is related to the direct-sum problem, i.e. if $n$ queries can be computed more efficiently than $n$ times the amount of resources needed for computing a single query. $\endgroup$
    – Kaveh
    Jan 10, 2011 at 22:41
  • $\begingroup$ Within the realm of theorem proving this problem is solved by a set of techniques under the umbrella name of "Term Indexing" e.g. data structures for efficiently finding unifiers, generalisations, or instances. Structures can be perfect (return the exact answers) or imperfect (returning a superset). See substitution trees, discrimination trees, and fingerprint indexing as examples. $\endgroup$
    – selig
    Feb 25, 2021 at 0:47

3 Answers 3

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks, these are useful tips. As the queries I work with are basically collecions of filters that are AND-ed together, they are already in CNF form. $\endgroup$
    – Teun D
    Jan 15, 2011 at 21:31
1
$\begingroup$
  1. Create a new table with only one object i.e. object X
  2. Execute all the queries on it.
  3. Discard those which return nothing.
  4. Remaining queries are the queries that match your object X.

This will be faster than searching in a big table.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ This is basically the naive approach. The running time vary linearly with both the number of queries and the number of items. I was rather thinking of creating a kind of index-like structure. $\endgroup$
    – Teun D
    Jan 10, 2011 at 20:16
0
$\begingroup$

For a single query, there is of course query optimization , which allows us to plan in which order should we apply the operators that compute the query.

There is also a multi-query optimization, although to my knowledge it's not as successful as single query optimization, which is seen as a vital component of any DBMS. A quick search in google gave me this paper , I believe there is extensive research in this problem and you won't have trouble finding related material to your question.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.