Datastructure for managing (abstract) sets

Question

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:

1. 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.
2. 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.

Answer 1

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
----
|  |-> compls
|  |-> disjoints 
|  |-> overlappings
|  |-> 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| |-> 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| |-> 123F65
 |B| |-> 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
----
|  |-> compls
|  |-> disjoints 
|  |-> overlappings
|  |-> [ C ]
----

NODE: 153F60
----
|  |-> compls
|  |-> disjoints 
|  |-> overlappings
|  |-> propers
----

HASH TABLE
 ______________
 |A| |-> 123F65
 |B| |-> 123F65
 |C| |-> 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.

Answer 2

I suggest you maintain a knowledge base of constraints on sets and translate the knowledge base to a formula on boolean variables. The knowledge base will consist of constraints of the form $A=B$, $A=\overline{B}$, $A =B \cap C$, $A=\emptyset$, $A \ne \emptyset$.

Each of the operations you mentioned can be implemented by adding constraints of these form to your knowledge base. For instance, to require that $A$ is a proper subset of $B$, require that $A \cap \overline{B} \ne \emptyset$ and $\overline{A} \cap B = \emptyset$; this can be done by introducing new sets $C,D,E,F$ and constraining $C=\overline{B}$, $D = A \cap C$, $E = \overline{A}$, $F=E \cap B$, $D \ne \emptyset$, and $F = \emptyset$. And so on. This part is mechanical.

To answer queries about the knowledge base, we'll translate the knowledge base to a boolean formula. Introduce abstract elements $a_1,\dots,a_n$, where $n$ counts the number of abstract sets in the knowledge base. Also, introduce boolean variables $x_{S,i}$ (one for each abstract set $S$ and each $i$ with $1 \le i \le n$). We'll generate a formula $\varphi$ that is a conjunction of constraints on the boolean variables . The intended meaning is that $x_{S,i}$ is true if $a_i \in S$, and that $x$ will satisfy $\varphi$ only if the corresponding sets are consistent with the knowledge base.

Here is how you translate the constraints in the knowledge base to boolean formulas:

• To constrain $A = B$, add the constraints $x_{A,i}=x_{B,i}$ for all $i$.

• To constrain $A = \overline{B}$, add the constraints $x_{A,i}=\neg x_{B,i}$ for all $i$.

• To constrain $A = B \cap C$, add the constraints $x_{A,i}= x_{B,i} \land x_{C,i}$ for all $i$.

• To constrain that $A = \emptyset$, add the constraints $x_{A,i}=\text{False}$ for all $i$.

• To constrain that $A \ne \emptyset$, add the constraint $x_{A,1} \lor \cdots \lor x_{A,n}$.

You can check whether the constraints are simultaneously satisfiable by checking whether the resulting formula $\varphi$ is satisfiable. This could be done using a SAT solver (using bit-blasting to convert these boolean constraints to CNF clauses).

You can answer the query "is $A$ empty?" (i.e., do the constraints imply that $A = \emptyset$?) by temporarily adding $A = \emptyset$ to the knowledge base, generating a new formula $\varphi'$, and testing whether $\varphi'$ is satisfiable using the SAT solver. If $\varphi'$ is satisfiable, then the answer to the query is "yes", otherwise the answer is "no".

You can translate the other kinds of queries you are interested in into this form by adding some additional constraints. For instance to answer the query "are $A,B$ disjoint?", you create a new set, add the constraint $C = A \cap B$, then answer the query "is $C$ empty?" (using the SAT solver). To respond to the query "name me a subset of $A$", create a new set $B$, add the constraint that $\overline{A} \cap B = \emptyset$, and return $B$ (no need to invoke the SAT solver).

To support a streaming sequence of queries, you could use a SAT solver that supports incremental solving (i.e., the ability to push and pop clauses onto a stack). See, e.g., https://stackoverflow.com/q/16422018/781723.

This might look pretty straightforward. The one technical trick is how I chose $n$, and in particular, that the number of abstract elements needed is upper-bounded by the number of $A \ne \emptyset$ constraints. I haven't tried to carefully prove that this is enough, but I think it suffices. I actually suspect it is possible to reduce $n$ further, specifically, to the number of $A \ne \emptyset$ constraints plus one. If true, this would improve efficiency -- but I haven't thought carefully about whether that's actually a valid optimization.

There are no guarantees that this scheme will be efficient. Your problem is at least as hard as SAT (i.e., NP-hard), so it follows that there will be some sequences of operations and queries that will very hard to answer in any reasonable amount of time. Given that your problem is at least as hard as SAT, my thinking is that translating to SAT and then using existing SAT solvers (and benefiting from all of the work that has gone into improving SAT solvers) might be your best hope for a solution that is often efficient in practice.