Graphs, 0-1 Matrices, and Usability of Statistical Databases

The motivation for this work comes from a security problem of statistical databases: In a database of n records, given k SUM queries, is it possible to answer all of them, plus another (\2)) —k distinct SUM queries, in such a way that no individual value from the database is revealed?

The corresponding mathematical problem (stated in terms of certain extensions of 0-1 matrices) is known to be NP-complete in general. We show that it remains NP-complete even when restricted to the case when each query involves four records and each record is in at most three queries. On the other hand, we identify certain cases in which the problem is solvable in polynomial time. The case when every record is contained in at most two of the given k queries is studied in detail from the graph-theoretic point of view.