Datastructure for managing (abstract) sets I am looking for a datastructure to represent the complex relationships between a bunch of abstract sets. The "abstract" means that these sets are not defined by their elements, but by their relationship to each other. This means that for me a set is nothing more than a named thing with a relations to other named things in the same space. For two sets $A,B$ the relation can be


they represent the same set, i.e. $A=B$,
they are complementary, i.e. $\bar A=B$,
they are disjoint $A\cap B=\varnothing$ but not complementary,
they are overlapping, i.e. they are not equivalent but have a non-empty intersection,
one is a proper subset of the other set, e.g. $A\subset B$
essentially unknown, but maybe some of the former cases can be excluded.


Besides storing these relationships, I want to ask questions on the datastructure like 


Are the sets $A$ and $B$ disjoint?
Name me a subset of $A\cap\bar B\cap \bar C$.
What is the relation between the sets $X$ and $\bar Y\cap Z$?


Also the datastructure should be updatable. There will be inserted new sets all the time which must be integrated in the structure correctly. There can be lots of sets and it is no option to explicitely store the relation between any pair of sets. Instead, some relations should be deducable by the query algorithms. For example, if we have $A\subset B\subset C$, then we will not store $A\subset C$ as this follows logically from the other two relations.

I thought about lots of tree like structures or cycle-free directed graphs. But maybe someone already developed exactly what I am looking for.



One more thing: I would prefer when the datastructure does note introduce big differences between sets and their complement. This means, asking whether $A\cap B$ is empty should not invoke vastly different algorithms than asking this for $A\cap \bar B$.



Update

To answer some comments, here are some more details on my intend.

You can think about this as a big (hyper-)graph problem, where the whole graph is too big to be stored but has much structure, so maybe can be stored very efficiently in another way. The nodes of the graph are sets. The (hyper-)edges are relations between the sets. The edges are colored to represent the six possible relation types from above. In this sense, the graph is an edge-colored complete graph. Note that the edge type unknown is very important to me!

To describe the queries in general, let me introduce the following notation: given a set $A$, we write $A^+=A$ and $A^-=\bar A$. The following queries should be supported as efficient as possible:


Given a sequence of nodes $A_i$ and a sequence of signs $s_i\in\{+,-\}$. Which of the following three options is true for $\bigcap_i A_i^{s_i}$: it is empty, there is a node representing a subset of this intersection, we do not know anything.
Given two sequences $A_i$, $B_i$ of nodes and two sequences $s_i$ and $r_i$ of signs. What kind of edge is between $\bigcap_i A_i^{s_i}$ and $\bigcap_i B_i^{r_i}$?


The last query seems trivial for the graph stored with all its edges. But as I said, the graph is probably too big to be stored in this naive way.

Of course, I never stated that for sets $A_i$ and signs $s_i$ my data structure must contain the set $\bigcap_i A_i^{s_i}$, but information can be deduced in other ways. For example, assume $A$ and $B$ are sets, but $A\cap B$ is not stored. But we have a set $C\subset A,B$. So we know that $A\cap B$ $-$ despite being not stored explicitely $-$ is not empty. If we lack any of these information, then we may conclude that "we do not know anything about $A\cap B$". The fact that $A\cap B$ is empty is stored by an edge between $A$ and $B$ signalling that these sets are disjoint.

Why I wrote hyper-edge instead of just edge? It might be necessary to store that $A\cap B\cap C=\varnothing$ but no two of these sets are disjoint. This cannot be deduced from any two set relation. So we may need edges involving more than just two sets.
One simple approach: 
For each abstract set $A$ create a node. Let each node maintain a list of
1) complementary sets
2) disjoint sets
3) overlapping, i.e. they are not equivalent but have a non-empty intersection
4) proper subsets

For example, consider the following node 

NODE: 123F65
----
|  |-&gt; compls
|  |-&gt; disjoints 
|  |-&gt; overlappings
|  |-&gt; propers
----


Assume that you have created a set $A$. Allocate a new node for this set and let $A$ point to this node.

 HASH TABLE
 ______________
 |A| |-&gt; 123F65
 ______________


Then assume you add a new set $B$ with a property $A=B$. You don't create a new node, just make $B$ point to the same location $A$ points to, 123F65. 

 HASH TABLE
 ______________
 |A| |-&gt; 123F65
 |B| |-&gt; 123F65
 ______________


Then assume you add a new set $C$ which is a proper subset of $B$. Create a new node for $C$ and make $C$ point to that node. Additionally add $C$ to to the list of proper subsets of $B$ in 123F65. 

NODE: 123F65
----
|  |-&gt; compls
|  |-&gt; disjoints 
|  |-&gt; overlappings
|  |-&gt; [ C ]
----

NODE: 153F60
----
|  |-&gt; compls
|  |-&gt; disjoints 
|  |-&gt; overlappings
|  |-&gt; propers
----

HASH TABLE
 ______________
 |A| |-&gt; 123F65
 |B| |-&gt; 123F65
 |C| |-&gt; 153F60
 ______________


So for example, if I want to find out if $A$ and $B$ is disjoint, I would check if $A$ is a subset of any $B$'s complementary or if $B$ is a subset of any $A$'s complementary. If yes then the answer is "disjoint", otherwise they are not disjoint or insufficient information.

Note that this data structure is just a kick-off. You may have to change it as you will ask different questions or you want to speed up queries.