Validate whether all AIDs need to be non-null

[diffix]

Validate whether all AIDs need to be non-null

[sebastian]

The answer is: No – we do not need all AIDs to be non-null!

• Example
  • Aggregating a.value
    • All rows are non-null
    • Only A has data - B is null
    • Only B has data - A is null
  • Aggregating b.value
    • All rows are non-null
    • Only A has data - B is null
    • Only B has data - A is null
  • Consideration

Example

Consider we have a LEFT OUTER JOIN between two tables: A and B.
The JOIN results in a table such as this:

a.value	b.value	AIDs
10	20	a[1], b[1]
11	21	a[2], b[2]
12	NULL	a[3]
13	NULL	a[4]

There are two things we could do:

• aggregate a.value
• aggregate b.value

Aggregating a.value

All rows are non-null

When there is data from both tables A and B then the aggregation happens as specified
in other documents. All is good.

Only A has data - B is null

In the cases where there is no value from table B, there is also no information about
any entity from table B that we need to consider! This is OK.
It could in the extreme (if the entire table B section is empty) be the equivalent of
aggregating strictly over table A, which is fine.

Only B has data - A is null

This does not occur in this scenario.

Aggregating b.value

All rows are non-null

Same as above in "All rows are non-null"

Only A has data - B is null

null values are ignored for the purposes of aggregation, so this is fine. It's a noop.

Only B has data - A is null

Doesn't occur in this scenario

Consideration

Our algorithm reports null for an aggregator when there is insufficient data from
any of the AIDs. This behavior needs adjusting.

We now have three different modes:

• There is sufficient data for all AIDs (i.e. enough to fill the outlier and top groups): all is good
• There is insufficient data for one or more of the AIDs (i.e. we cannot form both the outlier and top groups): the aggregate value should be returned as null
• The new case: there was absolutely no data for an AID: this is also fine, and should not cause the aggregate value to be rejected!

[sebastian]

Relevant update to docs: #126

[sebastian]

Ok, revisiting this again, and the relevant pull request for docs (#126) it seems my design was broken.
The current reference is right.

So:

• For anonymizing aggregators all AIDs need to have sufficiently many AID values to produce a top and extreme value group. If this is not the case, then return null in place of the aggregate value
• For non-anonymizing aggregators the story is different and the algorithm explains the shortcuts that are taken