11.25. Теорема

Если два корректных каркаса

SKEL⚪ = <T⚪, SH⚪, COM⚪, SEL⚪> и

SKEL◎ = <T◎, SH◎, COM◎, SEL◎>

находятся в отношении К-проекции, то применение к ним алгоритма 11.5 порождает ряд каркасов, в котором:

1. соседние члены сами находятся в отношении К-проекции
2. последний член совпадает с SKEL⚪

Доказательство

Второй пункт следует из того, что:

• те деревья рассматриваемых каркасов, на которых они построены по алгоритму 9.8, образуют требуемый ряд, последний член которого совпадает с деревом последнего каркаса
• множество унаследованных ключей каждого такого каркаса образуется на каждом шаге согласно алгоритму 11.2, совпадая с требуемым как результат от одного и того-же множества ключей.

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

• типом А – в лемме 11.4А2
• типом Б – в лемме 11.4Б2
• типом В – в лемме 11.4В2
• типом Г – в теореме 11.4Г2

доказывается, что в паре каркасов SKELi и SKELi+1, у которых

• деревья Ti и Ti+1 связаны элементарным шагом одного из указанных типов
• каркас SKELi является корректным

каркас SKELi+1 также является корректным, то есть, связан с SKELi соответствующим элементарным шагом.

Иначе говоря, для заданной пары корректных каркасов SKEL⚪ и SKEL◎, находящихся в отношении проекции-прообраза, построен требуемый ряд связывающих их каркасов, где каждая пара соседних каркасов SKELi и SKELi+1:

• связана одним из элементарных шагов
• находится в отношении К-проекции

что и требовалось доказать. █

Назад Вперёд