Раздельная обработка двух подвыражений запроса and

Наша реализация and в виде последовательной комбинации запросов (рисунок 4.5) изящна, но неэффективна, поскольку при обработке второго запроса приходится просматривать базу данных для каждого кадра, порожденного первым запросом. Если в базе данных N записей, а типичный запрос порождает число записей, пропорциональное N (скажем, N/k ), то проход базы данных для каждого кадра, порожденного первым запросом, потребует N²/k вызовов сопоставителя. Другой подход может состоять в том, чтобы обрабатывать два подвыражения запроса and по отдельности а затем искать совместимые пары входных кадров. Если каждый запрос порождает N/k кадров, то нам придется проделать N²/k² проверок на совместимость — в k раз меньше, чем число сопоставлений при нашем теперешнем методе.

Постройте реализацию and с использованием этой стратегии. Вам придется написать процедуру, которая принимает на входе два кадра, проверяет связывания в этих кадрах на совместимость и, если они совместимы, порождает кадр, в котором множества связываний слиты. Эта операция подобна унификации.

Рис. 4.5. Комбинация двух запросов через and осуществляется последовательной обработкой потока кадров.

---