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