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?

  • $\begingroup$ If you are using a relational database, you could use something like SQL to form such queries. $\endgroup$ – Paresh Mar 3 '13 at 15:43
  • $\begingroup$ I don't think the answer would be a data structure but a normal form as is used with a calculus, e.g. labmda calculus. Since the queries would reduce to a normal form you could then compare them for duplicates. As for set operations I don't know if you can do those and get back a normal form. $\endgroup$ – Guy Coder Mar 3 '13 at 21:33
  • $\begingroup$ How expressive is the language? Besides and, or and comparison predicates, what operations does it allow. Would it, for example, allow you to select people with a prime number of children (a complex predicate)? Would it allow to select people for whom number of children*10 > age (comparisons involving several columns)? $\endgroup$ – Karolis Juodelė Mar 4 '13 at 7:16
  • $\begingroup$ @KarolisJuodelė I do not need a really expressive language. I haven't thought of a language to express form queries yet. But for now, simple comparisons with single columns would be fine I guess. (I will decide the language after I figured out the limitations of the algorithm I will use.) $\endgroup$ – yilmazhuseyin Mar 4 '13 at 9:49
  • $\begingroup$ @Paresh Using a relational db will not really help me in this situations. I want to use this as a cache so, There will be a lot of data that will be inserted into the system and invalidated every second. io rate of this would be alot for a relational db. $\endgroup$ – yilmazhuseyin Mar 4 '13 at 9:50

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.