Datastructure for managing (abstract) 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.