axiom//cloudlog.interset Intersection Sets

Author: Temporarily Removed  (temporarily@removed.com)
Date: 25 April 2018
Repository: https://github.com/temporarily/removed
Version: 0.4.1

1    Introduction

In Axiom, mathematical sets are at the base of how we provide integrity and confidentiality. Each fact is assigned a writers set and a readers set, representing the set of users who may have stated this fact, and the set of users allowed to know about it.

To be able to efficiently reason upon theses sets, we need to find a Clojure representation that is both expressive enough, and efficient enough to represent and reason upon.

Intersets (intersection sets) are the representation we chose for Axiom. Each interset is represented as either a Clojure set (a simple interset), or a vector of such set (a canonical interset). The Clojure sets represent intersection, and the vectors represent union, so together we have a set expression that represents a union of intersections of basic components. The basic components of these sets are either strings or vectors, each representing an opaque set, i.e., a set one cannot further reason upon using interset operations. Strings represent identities (e.g., user-IDs), and vectors represent logic terms that are true for a set of users, such as a friend of some user X.

The following example interset may represent the friends of user alice in some application:

#{[:some-app/friend "alice"]}

The following interset represents the exclusive group of users who are friends with both alice and bob:

#{[:some-app/friend "alice"]
         [:some-app/friend "bob"]}

The following interset represents alice, but only if she's friends with bob (otherwise the sent is considered empty):

#{"alice" [:some-app/friend "bob"]}

The following interset includes both alice and all of alice's friends:

[#{"alice"} #{[:some-app/friend "alice"]}]

The following inteset is empty, because alice and bob are two seperate identities:

#{"alice" "bob"}

2    universe and empty-set

The universal set is the intersection of no sets. It is therefore:

interset/universe => #{}

Similarly, the empty set is a union of no sets:

interset/empty-set => []

3    intersection

Intersecting two simple intersets is a union of their underlying sets:

(interset/intersection #{[:some-app/friend "alice"]
                        [:some-app/friend "bob"]}
                      #{[:some-app/friend "alice"]
                        [:some-app/friend "charlie"]})
 => #{[:some-app/friend "alice"]
    [:some-app/friend "bob"]
    [:some-app/friend "charlie"]}

This is true because element x is a member of the intersection of intersets A and B if and only if it is a member of the both A and B. To be a member of A it needs to be a member of all the named sets composing A, and to be a member of B it needs to be a member of all of B's components. Therefore, x needs to be a member of all the named sets composing both A and B – their union (as Clojure sets).

For canonical intersets we return a union of the intersections of all simple intersets on one side, with all intersets on the other side, as long as they are not disjoint.

Consider for example two intersets containing, for alice and bob respectively, the user and his or her friends. Intersecting these two sets will result in a 3-component canonical set:

  1. Friends of both alice and bob.
  2. alice, as long as she's friends with bob, and
  3. bob, as long as he's friends with alice.The fourth combination – the intersection of alice and bob is omitted, because the set of all alices who are also bobs is empty.
(interset/intersection [#{[:some-app/friend "alice"]} #{"alice"}]
                      [#{[:some-app/friend "bob"]} #{"bob"}])
 => [#{[:some-app/friend "alice"]
     [:some-app/friend "bob"]}
   #{"bob" [:some-app/friend "alice"]}
   #{"alice" [:some-app/friend "bob"]}]

4    union

A union of two inrsets can be acheived by concatenating their canonical forms. For example, a set containing either alice or bob is derived the following way:

(interset/union #{"alice"} #{"bob"}) => [#{"alice"} #{"bob"}]

However, a union can be more minimal than that. If any of the components of the second arguments are subsets of the first argument, they are omitted.

(interset/union [#{"alice"} #{"bob"}] #{"bob" [:some-app/friend "alice"]}) => [#{"alice"} #{"bob"}]

5    subset?

The subset? predicate checks if one interset is a subset of the other. For example:

(interset/subset? #{:a} interset/universe) => true
 (interset/subset? interset/universe #{:a}) => false
 (interset/subset? #{:a} interset/empty-set) => false
 (interset/subset? interset/empty-set #{:a}) => true
 (interset/subset? (interset/intersection #{:a} #{:b}) #{:a}) => true
 (interset/subset? (interset/intersection #{:a} #{:b}) #{:c}) => false

In particular, a set is considered a subset of itself.

(interset/subset? #{:a} #{:a}) => true

For simple intersets, interset A is subset of interset B if and only if Clojure set B is a subset of Clojure set A.

(interset/subset? #{"alice" [:some-app/friend "bob"]}
                 #{[:some-app/friend "bob"]}) => true
 ;; but...
(interset/subset? #{[:some-app/friend "bob"]}
                  #{"alice" [:some-app/friend "bob"]}) => false

This is true because the set containing alice only if alice is friends with bob is a subset of bob's friends.

If the right-hand argument is a canonical interset, subset? returns true if it is true for at least one of the right-hand argument's components.

(interset/subset? #{"alice" [:some-app/friend "bob"]}
                 [#{[:some-app/friend "bob"]} #{[:some-app/friend "charlie"]}]) => true

If the left-hand argument is canonical, subset? returns true only if all components are subsets.

(interset/subset? [#{"alice" [:some-app/friend "bob"]} #{[:some-app/friend "charlie"]}]
                 [#{[:some-app/friend "bob"]} #{[:some-app/friend "charlie"]}]) => true
 ;; but...
(interset/subset? [#{"alice" [:some-app/friend "bob"]} #{[:some-app/friend "charlie"]}]
                  #{[:some-app/friend "bob"]}) => false

6    enum-groups

Sometimes we wish to iterate over all groups mentioned in an interset. enum-groups allows us to do so by returning a sequence of these groups.

For an empty or universal intersets, an empty sequence is returned.

(interset/enum-groups interset/universe) => []
 (interset/enum-groups interset/empty-set) => []

For a simple interset, all compoments are returned.

(interset/enum-groups #{[:foo "bar"] [:bar "foo"]}) => [[:foo "bar"] [:bar "foo"]]

For a cannonical interset, all components of all elements are returned.

(interset/enum-groups [#{[:foo "bar"]} #{[:bar "foo"]}]) => [[:foo "bar"] [:bar "foo"]]

7    Under the Hood

7.1    canonical

canonical takes an interset of any kind, and returns a canonical interset.

If the given interset is already canonical, it returns the interset as-is.

(interset/canonical [#{"foo"} #{"bar"}]) => [#{"foo"} #{"bar"}]

If the given interset is a simple one, it wraps it in a vector.

(interset/canonical #{"foo"}) => [#{"foo"}]

7.2    uncanonical

uncanonical inverts the effect of canonical, if it is possible.

When given a canonical interset of size 1, it returns the underlying set.

(interset/uncanonical [#{"foo"}]) => #{"foo"}

When given a canonical interset with more elements, it returns the canonical interset.

(interset/uncanonical [#{"foo"} #{"bar"}]) => [#{"foo"} #{"bar"}]

uncanonical is idempotent in the sense that calling it on a simple interset will result in the same interset.

(interset/uncanonical #{"foo"}) => #{"foo"}

7.3    disjoint?

Two simple intersets are (definitely) disjoint when each of them references a concrete user identity (a string), and these identities are different.

The disjoint? function takes two simple intersets and returns whether they are disjoint.

It will return false if at least one of the two sets does not have an identity.

(interset/disjoint? #{"foo"} #{[:some-app/friend "bar"]}) => false

In this case, disjoint? does not know for sure whether or not foo is a friend of bar, so it returns the safe answer false.

In case each inteset has a different identity we know for sure these sets are disjoint.

(interset/disjoint? #{"foo"} #{[:some-app/friend "bar"] "baz"}) => true

However, if both sets reference the same identity, they are not disjoint.

(interset/disjoint? #{"foo"} #{[:some-app/friend "bar"] "foo"}) => false