Алгоритмы выполнения селекции с одним условием сравнения: размер селекции, использование первичного индекса, использование вторичного индекса

Селекция, включающая сравнение.

До этого рассматривалась селекция, условие которой предусматривало равенство. Однако, часто селекция имеет вид s(А)<=v(r). При этом в статистике будет храниться следующая информация min(A, r) и max(A, r).

В общем случае можно утверждать, что число записей, удовлетворяющих условию А<=v, будет равно.

0, если v<min(A, r).

nr, если v>=max(A, r).

иначе

А6. Использование первичного индекса. Если условие селекции имеет вид A>v, то в индексе ищем первую запись, удовлетворяющую условию, а затем извлекаем из файла отношения все блоки, начиная с блока, включающего найденную запись и до конца файла. При условии A<v индекс не используется, а просматривается сразу файл отношения, из него извлекаются блоки до тех пор, пока записи блока соответствуют условию. Как только найдена запись, не удовлетворяющая условию, поиск прекращается. Эффективность этого алгоритма

где с – число записей, удовлетворяющих условию.

(или без первого слагаемого).

В случае, если в статистике не хранятся данные для расчета с, то вместо него используют Br (число блоков в отношении r.)

А7. Использование вторичного индекса. При этом производится просмотр самого нижнего уровня индекса с минимального значения до v при условии A<v или с v до максимального значения в противном случае.

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