Data structure that allow efficient tag based lookups I am looking for a highly efficient data structure for storage of data similar to the following.


Id    Tags   Order1 Order2 
--------------------------
1     1,2     1      1
2     2,5     2      3
3     1,7     4      7
4     6       3      0


I need to be able to query this structure in such a way that it would give me a list of all ids containing an expression of tags - supporting AND and OR and NOT operations. Eg. ((1 or 2) and not 7)

I also need to be able to specify the ordering of the results (Order1 or Order2) and be able to specify maximum rows returned with an optional offset. Performance for the fetch of the first 30-100 results is key. 

Finally, I need a cheap way to lookup "tag relations" for example I want to know which tags "relate" to tags (1 OR 2) and in what frequency. Meaning which tags appear in the same set as 1 OR 2 ... ordered by frequency. 

Any idea of what data structure (or set of structures) would be highly efficient for this kind of work?

(I would like to use this as a proof of concept for redesigning the tagged pages of the SE family of sites)
This is not exactly an answer of an efficient data structure, but rather an elaboration on the comments of @bbejot and @Kaveh giving a hand-waving argument for why given the current question we should not expect something that does a lot better than searching the whole database. The argument is based on a reduction from SAT, the exponential time hypothesis, and a lot of hand-waving.

Assume we have upto $n$ different tags, then we can think of each id as being associated with a bitvector $x$ of length $|x| = n$ where $x_j = 1$ if we have the $j$-th tag, and $x_j = 0$ otherwise. Since there is no real restrictions on what the database looks like, I can assume it has ids $1$ through $2^n$ with the $k$-th id having an associated tag vector of $k$ written in binary. The order fields can be arbitrary, since they only make the problem harder. Now, if we are given an arbitrary query of $AND$, $OR$, and $NOT$s then this is just asking a SAT question on $n$ variables. By the exponential time hypothesis, we can't expect this to be much faster than $2^n$... or in other words, we can't expect this to be much faster than searching the whole database.

We shouldn't expect efficient search in the length of the query (by reduction to SAT). We also shouldn't expect much better than looking at all the items in the database by the exponential time hypothesis.

To hope for an efficient data-structure for this question, we will have to make some serious assumptions on the structure of the database that are not made in this question. For instance, if we assume a special structure on the queries (such as CNF) then we can hope for something more efficient. An alternative assumption is on the structure of the database. We could probably assume that given $n$ tags, only a small fraction of the tags will be present on any given id (say a logarithmicly few $1$s). This is not an unreasonable assumption given the application of tagged questions (what use are tags if almost every single tag is used for a question).