# Algorithm for query comparison

Lets say I have a global dataset and I run queries over those data set. For example my dataset would be

• #id, #Name, #Employee, #Birthdate, #number_of_children
• 1, Nick, Nasa, 1982, 1
• 2, Jack, Exon, 1985, 5
• 3, Tom, ABCD, 1978, 0

And I can run queryies on those dataset. sample queries would be * #Query => #Result_ids * (Name starts with A) => [1] * (Birthdate before 1983 and have children ) => [1]

I want to store those queries on a data structure and I want to be able to do set operations on those queries like intersection and union. So an example union operation would be.

(Birthdate before 1983) intersection (have children) => (Birthdate before 1983 and have children)

I also want to be able to findout if one query is subset or superset of another one. For example.

(Birthdate before 1983) is superset of (Birthdate before 1980) (Have 3 children) is subset of (Have more than 1 children)

(Name = Jack and born in 1980) is subset of (Born before 1990)

I will have a program that will have thousands of queries. And it will combine those queries to make more variety of queries. When I have a new query, I will compare it with existing queries to see if I have an exact query in store or have a superset.

Can anybody suggest me a data structure that is fast enough to store and operate on those data?

• Checking whether a query selects a superset of another query is at least NP-hard. You can encode SAT problems with your queries. Besides this problem, why not simply encode queries as their expression trees? – adrianN Feb 26 '13 at 14:30
• It can't be NP-hard; we can compute the answer by brute force in O(n) time, where n is the size of the database. – JeffE Feb 26 '13 at 14:48
• Queries looks like spatial data. At least some of the parameters (like birthdate) of the query can be expressed as spatial dimensions. therefore I might be able to use something like r* tree. en.wikipedia.org/wiki/R*_tree . But this is still looks like a partial solution to me since there might be some query parameters that cannot be expressed as spatial data. – yilmazhuseyin Feb 26 '13 at 15:30
• Welcome to cstheory, a Q&A site for research-level questions in theoretical computer science (TCS). Your question does not appear to be a research-level question in TCS. Please see the FAQ for more information on what is meant by this. Your question might be suitable for Computer Science which has a broader scope. – Kaveh Mar 2 '13 at 7:43
• @Kaveh that explains why I am getting down votes. Thank You for showing me the right direction. I will try Computer Science next. – yilmazhuseyin Mar 3 '13 at 12:53