тимся к примеру на рис. 16.2. Если b = 2, то в таком случае будут разрешены запросы только с кардинальностью с, находящейся в диапазоне 2 < с < 8. Это значит, что следующее логическое выражение использовать нельзя.

SEX = М AND OCCUPATION = Programmer

Теперь рассмотрим приведенную ниже последовательность запросов 7-10.

7. WITH ( STATS WHERE SEX = М ) AS X : COUNT ( X )

Результат: 4.

8. WITH ( STATS WHERE SEX = M AND NOT

( OCCUPATION = Programmer ) ) AS X :

COUNT ( X ) Результат: 3.

Ha основании запросов 7 и 8 пользователь U может сделать вывод, что существует только один мужчина-программист, следовательно, его зовут Alf (поскольку пользователь и уже знает из других источников, что сотрудник по имени Alf является мужчиной и программистом). Зарплата этого сотрудника может быть определена следующим образом.

9. WITH ( STATS WHERE SEX = М ) AS X : SUM ( X, SALARY )

Результат: 328 ООО.

10. WITH ( STATS WHERE SEX = M AND NOT

( OCCUPATION = Programmer ) ) AS X : SUM ( X, SALARY )

Результат: 278 ООО; 328 ООО - 278 ООО = 50 ООО.

Логическое выражение SEX = М AND OCCUPATION = Programmer называется трекером (охотником) за индивидуальными данными (individual tracker) для человека по имени Alf [16.6], поскольку оно позволяет отыскать индивидуальную информацию о человеке по имени Alf. В общем случае, если пользователю известно некоторое логическое выражение BE, идентифицирующее некоторого человека I, и если логическое выражение BE может быть выражено в виде ВЕ1 AND ВЕ2, логическое выражение ВЕ1 AND NOT ВЕ2 является трекером за индивидуальными данными человека по имени I (при условии, что в системе разрешено использовать выражения ВЕ1 и ВЕ1 AND NOT ВЕ2, т.е. оба они приводят к результату, кардинальность (с) которого находится в диапазоне b < с < N - Ь). Причина этого заключается в том, что определенное с помощью BE множество идентично разнице между множеством, определенным с помощью ВЕ1, и множеством, определенным с помощью BE 1 AND NOT ВЕ2, что наглядно представлено на рис. 16.3.

set { BE ) = set ( BEl AND BE2 )

= set (BEl) - set (BEl AND NOT BE2)

Множество, идентифицированное булевым выражением ВЕ1

Множество, идентифицированное булевым выражением ВЕ1 AND NOT ВЕ2

Множество, идентифицированное булевым выражением BE1ANDBE2 -т.е.{П

Множество, идентифицированное булевым выражением ВЕ2

Рис. 16.3. Трекер за индивидушгьными данными ВЕ1 AND ЮТ ВЕ2

В [16.6] упомянутые здесь идеи обобщены и показано, что практически для любой статистической базы данных всегда может быть определен общий трекер (в отличие от множества индивидуальных трекеров). Общий трекер (general tracker) - это логическое выражение, которое может быть использовано для поиска ответа на любой запрещенный запрос, т.е. запрос, включающий недопустимое логическое выражение. (В противоположность этому индивидуальный трекер работает только на основе запросов, включающих конкретные запрещенные выражения.) Фактически оказывается, что любое логическое выражение с результирующим набором данных с кардинальностью с в диапазоне 2Ь < с < N - 2Ь является общим трекером (здесь b должно быть меньше, чем N/4, что обычно всегда выполняется на практике). Как только такой трекер будет найден, сразу же можно будет получить ответ на запрос, включающий запрещенное логическое выражение BE, что наглядно показано в следующем примере. (Для определенности рассмотрим случай, в котором кардинальность результирующего множества логического выражения BE меньше Ь. Случай, когда Ь больше N-b, обрабатывается аналогично.) Обратите внимание, что по определению Т является общим трекером тогда и только тогда, когда NOT Т также является общим трекером.

Пример. Предположим снова, что b = 2; тогда общим трекером будет любое логическое выражение с кардинальностью результирующего множества с в диапазоне 4 < с < 6. Еще раз предположим, что пользователю U известно из внешних источников, что сотрудник по имени Alf является мужчиной и программистом, т.е. запрещенное логическое выражение BE выглядит так, как показано ниже.

SEX = М AND OCCUPATION = Programmer

Допустим также, что пользователь U хочет узнать размер зарплаты сотрудника Alf. В этом случае общий трекер придется применить дважды: сначала, чтобы удостовериться, что BE действительно идентифицирует сотрудника по имени Alf (этапы 2-4), а затем непосредственно для того, чтобы определить размер зарплаты сотрудника Alf (этапы 5-7).

Этап 1. Попробуем найти выражение для общего трекера Т. В качестве первого приближения выберем следующее выражение.

AUDITS = О

Этап 2. С помощью выражений Т и NOT Т определим общее количество сотрудников, сведения о которых содержатся в базе данных.

WITH ( STATS WHERE AUDITS = О ) AS X : COUNT ( X )

Результат: 5.

WITH ( STATS WHERE NOT ( AUDITS = 0 ) ) AS X : COUNT ( X )

Результат: 5; 5 + 5 = 10.

Теперь легко видеть, что выбранное выще выражение Т действительно оказалось общим трекером.

Этап 3. Найдем результат сложения общего количества сотрудников в базе данных с количеством сотрудников, для которых удовлетворяется неразрешенное выражение BE, для чего используем выражения BE OR Т и BE OR NOT Т.

WITH ( STATS WHERE ( SEX = M AND

OCCUPATION = Programmer OR AUDITS = 0 ) AS X :

COUNT ( X ) Результат: 6.

WITH ( STATS WHERE ( SEX = M AND

OCCUPATION = Programmer OR NOT ( AUDITS = 0 ) ) AS X :

COUNT ( X )

Результат: 5; 6 + 5 = ]\.

Этап 4. Из полученных выше результатов можно сделать заключение, что количество сотрудников, которые удовлетворяют логическому выражению BE, равно единице (результат этапа 3 минус результат этапа 2), т.е. логическое выражение BE единственным образом идентифицирует сотрудника по имени Alf.

Теперь на этапах 5 и б повторим запросы, использованные на этапах 2 и 3, но вместо функции COUNT укажем функцию SUM.

Этап 5. С помощью выражений Т и NOT Т найдем размер зарплаты всех сотрудников.

WITH ( STATS WHERE AUDITS = О ) AS X : SUM ( X, SALARY )

Результат: 438 ООО.

WITH ( STATS WHERE NOT ( AUDITS = 0 ) ) AS X : SUM ( X, SALARY )

Результат: 290 ООО; 438 ООО + 290 ООО = 728 ООО.