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?


migrated from cstheory.stackexchange.com Mar 4 '13 at 15:18

This question came from our site for theoretical computer scientists and researchers in related fields.

  • $\begingroup$ 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? $\endgroup$ – adrianN Feb 26 '13 at 14:30
  • $\begingroup$ 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. $\endgroup$ – JeffE Feb 26 '13 at 14:48
  • $\begingroup$ 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. $\endgroup$ – yilmazhuseyin Feb 26 '13 at 15:30
  • $\begingroup$ 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. $\endgroup$ – Kaveh Mar 2 '13 at 7:43
  • $\begingroup$ @Kaveh that explains why I am getting down votes. Thank You for showing me the right direction. I will try Computer Science next. $\endgroup$ – yilmazhuseyin Mar 3 '13 at 12:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.