Меню
Главная
Авторизация/Регистрация
 
Главная arrow Информатика arrow ИНТЕЛЛЕКТУАЛЬНЫЕ СИСТЕМЫ. ТЕОРИЯ ХРАНЕНИЯ И ПОИСКА ИНФОРМАЦИИ
Посмотреть оригинал

Допустимость информационного графа.

Покажем, что ИГ U* решает ЗИП I = (Xint2, V,pint2)L

Возьмем произвольный запрос х — (u,v,u2,v2). Возможны следующие два случая.

1) Для любого q € {1,..., М] существует такой номер г = r(q) € € {1 , ...,fca|+"+a* + 1}, что 1)Lj < U ^ V < l?. Это означает, что V: х Pint2 у} = 0- Поскольку путь к листьям ИГ U* лежит только через вершины типов 6aij, 77^, /3^, а проводимость в эти вершины

есть только в случаях когда хотя бы одна точка сетки попадает в интервал [ui, ui], то проводимость в эти вершины на запросе х равна нулю, и ответ ИГ U* на запрос х пуст.

2) Существуют такие номера у € {1 и г = r(y) Е

Е {1,..., fcai+‘"+a«}, что ui ^ ^ Vi. Пусть уо минимальный из

номеров у, обладающих таким свойством, т. е. либо = 1» либо для

любого q < qo существует такой номер г = г(у) Е {1,... ,&ai+*"+a« + + 1}, что 1я_г < Mi ^ V < /?. Возможны два подслучая.

2.1) Для любого q Е {уо,•.., М} существует такой номер г = r(q) Е € {1,..., fcai+‘"+a«}, что Iя _1 < t*i ^ I* ^ vi < Это означает, что множество {у Е V: х pint2 у} содержит не более одной записи, причем единственным кандидатом на принадлежность этому множеству яв- ляется запись (у'г{м),у?т)- Если и2 ^ У^М) ^ Ъ, то (умуУг(М)) е € {у € V : х pint2 у}у иначе Е V : х pint2 у} = 0- Непосредственно проверяется, что среди вершин типа 0^ только проводимость в вер- ШИНУ 0"м) будет ненулевой, тогда как проводимость всех вершин типа Tfijy Сij будет равна нулю, так как мы проходим в эти вершины только тогда, когда по крайней мере две точки сетки попадают в интервал [i*i,i>i]. Из вершины /3^М) исходит ребро с предикатом /уа , что соответствует проверке принадлежности интервалу [ui, Vi] точки yj(My Таким образом Ju- (х) = {у Е V: х pint2 у}-

2.2) Существуют такие номера q Е {уо,...,М} и г = г(у) Е

6 {l,...,&ai+"’+e« - 1}, что ui ^ ^ /^+1 ^ Vi- Пусть qi —

минимальный из номеров у, обладающих таким свойством, т. е. либо <7i = Уо> либо для любого q такого, что у<> ^ Я < Яи существует такой номер г = r(q) Е {1,...,&ai++a«}, что < t*i ^ ^ Vi < /®+1.

Для каждого у € {1,...,М} определим такие номера r'(q) и г"(у),

ЧТО lr'(q)-1 < Ul ^ и C'fo) ^ Vl < lr"(q) + Г ПОНЯТНО, ЧТО вСЛИ

Уо > 1, то для любого g € {1,..., уо 1} справедливо г'(у) = г"(у) — — 1 и если уо < yi, то для любого у Е {уо>-*-><71 — 1} справедливо г'(у) = г"(у), и для любого у Е {yi,...,М} справедливо г'(у) < г"(у). Отметим, что если yi > 1, то для у < yi согласно сделанному выше замечанию проводимость всех вершин типа Saij, у-, ?? будет равна нулю.

Заметим, что для того, чтобы проводимость в вершины типа Saij была равна 1, необходимо, чтобы либо у = 1, либо i*i и v принадлежали одному интервалу (у — 1)-й сетки. Поэтому, если уо < yi, то проводимость во все вершины типа 5я-, будет равна 0. Если же Яо = Я11 т0 среди вершин типа 6я- только проводимость вершины будет равна 1, где s' = 1, если yi = 1, и s' = r"(yi 1), если yi > 1, t' = r'(y) — (s' — 1)/:"*, j' = r"(y) — (s' - l)fca«. Выход к вершине 6я •, означает, что будет решаться одномерная задача интервального поиска для запроса (112,^2) среди точек из множества Км , определяемого соотношением (4.85).

Легко видеть, что если уо = yi, то проводимость всех вершин типа Vij > Сij будет равна нулю.

Для каждого q Е {max(<70 + l,

и это случится при условии, что r'(q — 1) > 1 и r'(q) < (r'(q — 1) —

- 1 а* 4- 1, при этом i"(q) = r'(q - 1) и j"(q) = r'(q) - (r'(q — 1) —

— 2)kQ* - 1. Выход к вершине у(ч) означает, что будет решаться

одномерная задача интервального поиска для запроса (u2,t>2) среди точек из множества ^•»(,)_lii«(,)+lifco,+1.

Для каждого q Е {таx(q0 + l,4i),... , Л/} среди вершин типа ??•, проводимость только одной вершины может быть равна 1,

и это случится при условии, что r"(q) > (r"(q — 1) - l)fca* + 1, при этом im(q) = r"{q — 1) и jm(q) = r"(g) - (r"(<7 - 1) - 1)A;Q«. Выход к вершине C?"(q) у"(д) означает, что будет решаться одномерная задача интервального поиска для запроса (u2,V2) среди точек из множества

И наконец, среди вершин типа , проводимость только вершины /?г^(М) будет равна 1. И в этой вершине делается проверка на принадлежность Отрезку [U2,V2 ТОЧКИ У*ч(Му

Тем самым, легко видеть, что все множество записей из V, абсциссы которых принадлежат отрезку [ui,vi], разделилось на неперссе- кающиеся части, и для каждой части решается одномерная задача интервального поиска по вторым координатам, т. е. устанавливается принадлежность ординат записей отрезку А это означает,

что ответ ИГ U* на запрос х совпадает с множеством записей из У, удовлетворяющих запросу х.

Таким образом, в силу произвольности х мы доказали допустимость ИГ U*.

 
Посмотреть оригинал
Если Вы заметили ошибку в тексте выделите слово и нажмите Shift + Enter
< Предыдущая   СОДЕРЖАНИЕ   Следующая >
 
Популярные страницы