Средства проектирования информационных систем

82 7.3. Оценка временной сложности и выбор алгоритма вы- полнения запроса При выборе пути доступа придерживаются следующих правил: 1. Последовательно шаг – за шагом выбирают отношение последова- тельности. 2. В качестве очередного отношения, сначала, если возможно, выбира- ют отношение с доступом по первичному ключу; затем, если возможно, от- ношение с доступом по вторичному ключу; и, наконец, в случае отсутствия возможности доступа по первичному и вторичным ключам, - отношение с последовательным доступом. В случае много вариантности выбора отношений производят расчеты и оценивают количество обращений к БД. По результатам оценки выбирают вариант последовательности обхода. Для определения временной сложности используется следующее вы- ражение, которое позволяет оценить количество обращений к БД при вы- полнении запроса: 49 , , ,1 ,1 1 1 i i i i i i m i i p q n nn N          N – количество обращений к БД; m – количество отношений в подсхеме; n i - количество обращений к отношению c номером i в последовательности ( i=1,m ) n 0 - количество выполнений запроса при однократном решении задачи ( n 0 =1); q i-1,i – количество обращений к отношению с номером i в последовательности, при условии одного обращения к отношению с номером i-1 (i=2,m) , q 0,1 – количество обращений к отношению с номером 1, при однократном выполнении запроса; p i-1,i – вероятность обращений к отношению с номером i в последовательности, при условии одного обращения к отношению с номером i -1 (i=2,m) ; P 0.1 – всегда равна 1.