×

Graphs, 0-1 matrices, and usability of statistical databases. (English) Zbl 0901.05071

Summary: 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 \(\left(\begin{smallmatrix} n\\ \lfloor{n\over 2}\rfloor\end{smallmatrix}\right)- 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.

MSC:

05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
68P15 Database theory
68R10 Graph theory (including graph drawing) in computer science
68Q25 Analysis of algorithms and problem complexity
PDFBibTeX XMLCite