<p>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.</p>

<p>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.</p>

<p>That's for the general case of boolean formulas, of course. For any specific <em>type</em> of query, such as just substrings, I imagine there would be various things that can be done.</p>

<p>Edit: In fact, for queries (or portions of queries) which can be represented as regular expressions, one can use the techniques presented in <a href="http://sebfisch.github.com/haskell-regexp/regexp-play.pdf" rel="nofollow">A Play on Regular Expressions</a> and take the union of these regular expressions over a semiring which counts matches to each original query.</p>

CC BY-SA 2.5
2011-01-15T21:31:15.270Z
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.
Teun D
CC BY-SA 2.5
2011-01-10T23:47:54.850Z
2011-01-11T14:43:00.867Z
2011-01-11T14:43:00.867Z
sclv
<ol>
<li>Create a new table with only one object i.e. object X</li>
<li>Execute all the queries on it.</li>
<li>Discard those which return nothing.</li>
<li>Remaining queries are the queries that match your object X.</li>
</ol>

<p>This will be faster than searching in a big table.</p>

CC BY-SA 2.5
2011-01-10T20:16:37.413Z
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.
Teun D
CC BY-SA 2.5
2011-01-10T12:36:13.397Z
2011-01-10T12:36:13.397Z
Pratik Deoghare
<p>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.</p>

<p>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 <a href="http://portal.acm.org/citation.cfm?id=42203" rel="nofollow">paper</a> , I believe there is extensive research in this problem and you won't have trouble finding related material to your question.</p>

CC BY-SA 2.5
2011-01-11T13:38:16.350Z
2011-01-11T13:38:16.350Z
chazisop
<p>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? </p>

<p>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.</p>

CC BY-SA 4.0
2021-02-25T00:47:35.583Z
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.
selig
CC BY-SA 2.5
2011-01-10T12:59:42.090Z
I believe you have better chances to get answers on http://www.stackoverflow.com/
Radu GRIGore
CC BY-SA 2.5
2011-01-10T22:41:21.357Z
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.
Kaveh
<ds.algorithms><descriptive-complexity><db.databases><finite-model-theory>
Searching for matching queries
Teun D
# Searching for matching queries

(Asked by: username_0 on 2011-01-10)

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.

**Tags:** ds.algorithms, descriptive-complexity, db.databases, finite-model-theory

> **Comments:**
> **username_2**: I believe you have better chances to get answers on http://www.stackoverflow.com/  
> **username_3**: 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.  
> **username_1**: 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.  

---

## 3 answers

### Answer by username_4 on 2011-01-10. Score: 1 | Accepted answer

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](http://sebfisch.github.com/haskell-regexp/regexp-play.pdf) and take the union of these regular expressions over a semiring which counts matches to each original query.

> **Comments:**
> **username_0**: 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.  

---

### Answer by username_5 on 2011-01-10. Score: 1

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.

> **Comments:**
> **username_0**: 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.  

---

### Answer by username_6 on 2011-01-11. Score: 0

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](http://portal.acm.org/citation.cfm?id=42203) , I believe there is extensive research in this problem and you won't have trouble finding related material to your question.


---

