БД, позволяющая получать агрегированную информацию о больших подмножествах некоторого множества объектов, называется статистической. Примерами могу служить БД переписи населения, налоговых деклараций либо пациентов госпиталя. Кроме обычных проблем предотвращения несанкционированного доступа к БД или ее модификации, в статистической БД существуют проблемы, связанные с тем, что допускаются запросы в виде: «Напечатать средний доход всех жителей Томска», но в тоже время запрещается доступ к данным о доходах, конкретного человека, например Иванова.
Не так просто запретить запросы, которые требуют информации, относящейся к единственной записи. Например, Петров может запросить средний доход для множества {Петров, Иванов}, из которого, зная свой собственный доход, он может вычислить доход Иванова. Не решает проблему также и требование, чтобы информация запрашивалась относительно множества, состоящего из m человек. Действительно, в этом случае Петров мог бы взять множество S из m-1 или более человек, доходы которых ему не нужно узнавать, и запросить средний доход этих людей вместе с Ивановым. Затем он получил бы средний доход для множества, включающего его самого и людей из множества S. Зная свой собственный доход, он смого бы теперь легко определить доход Иванова на основе двух ответов системы. Поэтому необходимо ввести огранечения на запросы, сильно пересекающиеся друг с другом и таким образом можно если не предотвратить раскрытие индивидуальных данных, но сделать это достаточно трудным делом.
Будем считать для простоты, что статистическая БД содержит единственный файл записей. Каждая запись состоит из нескольких полей. Пусть v = (v