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

77 7.2. Определение возможных путей обхода отношений подсхемы и вида доступа Пусть найдено множество S отношений, входящих в подсхему запроса БД. Будем рассматривать такие запросы, когда к каждому отношению при выполнении запроса обращаются однократно. Тогда, очевидно, что макси- мальное количество различных путей доступа, последовательностей «обхо- да» отношений будет определяться величиной факториала мощности множе- ства S : p= |S|! . Однако на практике число различных возможных путей доступа оказы- вается значительно меньше величины p , так как при доступе к отношениям используются индексы, наличие которых определяются связями между от- ношениями в логической модели БД. Использование тех или иных индексов задается структурой (схемой доступа), под которой будем понимать неориен- тированный граф H , с множеством вершин R . Множество ребер W графа H соответствует связям между отношениями логической схемы, использован- ных при выполнении запроса (см. пример подсхемы на рис. 7.2). Для нахождения возможных путей обхода сначала определим виды до- ступа, а затем возможные последовательности доступа к отношениям БД (таблицы 7.1 и 7.2).