Определение 3.1 (R Filter-Join S)
R называется внешним отношением, а S – внутренним отношением метода Filter-Join. Создается надмножество (без дубликатов) значений атрибута соединения R и используется как фильтр для ограничения кортежей S, к которым производится доступ. Ограниченное отношение из кортежей S затем соединяется с отношением R (с использованием любого другого доступного алгоритма соединения).
Этот метод соединения похож на хорошо известную операцию полусоединения [BGW+81], и эта схожесть используется в разд. 7 при моделировании магических множеств с использованием операции ?-полусоединения. Важным отличием является то, что полусоединения обычно применяются к хранимым отношениям, в то время как перезапись на основе магических множеств работает с представлениями.
Предположим, что оптимизатор запросов, дополненный возможностью рассмотрения Filterjoin как метода соединения, вызывается для обработки запроса с соединением N отношений. На некоторой промежуточной стадии оптимизатор оценивает стоимость некоторого соединения. Внешнее соединение является составным отношением вида (R1 ?? R2 ?? … ?? R(k-1)), и внутренним является одиночное отношение Rk, для которого можно применить перезапись на основе магических множеств (т.е. Rk является представлением). Наименьшее фильтрующее множество будет происходить из проекции (без дубликатов) всего составного внешнего отношения. Менее ограничительные фильтрующие множества могли бы создаваться путем использования в качестве PartialResult соединения любого подмножества таблиц составного внешнего отношения. После того как сделан конкретный выбор PartialResult, само фильтрующее множество может быть представлено точно или с некоторыми потерями (т.е. взамен может использоваться некоторое надмножество фильтрующего множества) путем опускания некоторых атрибутов соединения.
Имеется много различных вариантов выбора для PartialResult и для фильтрующего множества. Как мы показали в Примере 2, фильтрующее множество используется для ограничения внутреннего отношения путем добавления этого множества в раздел FROM внутреннего блока запроса. Даже после выбора некоторого PartialResult и некоторого фильтрующего множества модифицированная версия внутреннего реляционного представления (LimitedDepAvgSal на рис. 2) нуждается в планировании. Ясно, что если эти варианты выбора исследуются для каждого возможного соединения, включающего Rk, то мы проанализируем все возможные комбинации SIPS. Однако мы не склонны к тому, чтобы подвергать риску сложность оптимизатора ради оптимизирующей перезаписи на основе магических множеств. Из этого следует, что если мы предлагаем анализировать возможные варианты выбора для каждого Filterjoin, то это должно делаться за константное время. Поэтому наша следующая задача состоит в сокращении пространства поиска до некоторых приемлемых размеров.
