MUMPS: Совмещение древовидных и битовых индексов

Рассмотрим технические детали совмещения в одной выборке битовых и древовидных индексов. Для такого совмещения следует построить модель абстрагирования от реализации, то есть рассматривать индексные операции как таковые безотносительно их реальной внутренней реализации. И, используя абстрактные операции, реализовать механизм совмещения двух разнородных структур.

В случае древовидных и битовых индексов такой абстракцией может быть абстрагирование до уровня отображения вообще, следования вообще, проверки существования вообще и другие. Составив алгоритм оперирования индексами вообще, его просто нужно адаптировать до уровня, способного использовать конкретную реализацию, не зная ее деталей.

Основной операцией выборки по индексам является операция И. Рассмотрим на ее примере данную методику. Для этого мы располагаем двумя абстрактными операциями - теоретико-множественной операцией битового И и многоиндексной шаговой выборки. Приведем операции с обоими видами индексов к одинаковым абстракциям.

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

• Упорядоченный набор имен индексов. Упорядочение требуется чтобы выбирать их из используемого набора.
• Одинаковое упорядочение (сортировка) выбираемых из индекса искомых значений.
• Наличие у абстрактного индекса операции "взять следующий идентификатор".
• Наличие у абстрактного индекса операции "проверить существование идентификатора".

Под все четыре приведенных условия мы уже можем подвести операции и с битовым и с древовидным индексом. Сам алгоритм, выполняя собственно выборку, не должен знать реальную реализацию каждого индекса, а должен оперировать каждым из индексов в обобщенной форме. Для реализации такого полиморфизма используем косвенность - будем передавать в структуру, описывающий индекс, кроме имени самого индекса, также еще два имени - один как имя функции, выполняющей получение следующего идентификатора, и второй как имя функции выполняющей проверку существования заданного идентификатора в индексе.

CreateRecords()
 k ^Index
 k ^Data
 n i,Figures,Colors,Counts,Figure,Color,Count,id
 s Figures="квадрат~круг~отрезок~треугольник"
 s Colors="красный~зелёный~синий~белый"
 s Counts="2~5~12~8"
 f i=1:1:24 d
 . s Figure=$p(Figures,"~",$r(4)+1)
 . s Color=$p(Colors,"~",$r(4)+1)
 . s Count=$p(Counts,"~",$r(4)+1)
 . s id=$$InsertRecord(Figure_"~"_Color_"~"_Count)
 q
InsertRecord(RecordValues)
 n id s id=$i(^Data)
 l +^Data(id)
 s ^Data(id)=RecordValues
 d InsertIndexRecords(id,RecordValues)
 l -^Data(id)
 q id
DeleteRecord(id)
 q:'$d(^Data(id))
 l +^Data(id)
 n RecordValues s RecordValues=$g(^Data(id))
 d DeleteIndexRecords(id,RecordValues)
 k ^Data(id)
 l -^Data(id)
 q
UpdateRecord(id,RecordValues)
 q:'$d(^Data(id))
 l +^Data(id)
 n OldRecordValues s OldRecordValues=$g(^Data(id))
 d DeleteIndexRecords(id,OldRecordValues)
 s ^Data(id)=RecordValues
 d InsertIndexRecords(id,RecordValues)
 l -^Data(id)
 q
InsertIndexRecords(id,RecordValues)
 d InsertIndexRecord("Figure",id,$p((RecordValues),"~",1))
 d SET($na(^Index("Color",$p((RecordValues),"~",2))),id)
 q
DeleteIndexRecords(id,RecordValues)
 d DeleteIndexRecord("Figure",id,$p((RecordValues),"~",1))
 d DEL($na(^Index("Color",$p((RecordValues),"~",2))),id)
 q
InsertIndexRecord(IndexName,id,Value)
 s ^Index(IndexName,Value,id)=""
 q
DeleteIndexRecord(IndexName,id,Value)
 k ^Index(IndexName,Value,id)
 q
#define BITSIZE (260000)
DEL(name,id) s bit=0 g SET+1
SET(name,id,bit=1)
 n seg,pos
 s seg=id\$$$BITSIZE s pos=id#$$$BITSIZE+1
 s $bit(@name@(seg),pos)=''bit
 q

Здесь по атрибуту Color строится обычный битовый индекс, а по атрибуту Figure простой древовидный. Теперь модернизируем алгоритм многоиндексной выборки таким образом, чтобы он использовал не предопределенные операции $O(), $D(), $BIT(), а заданные извне имена функций. И составим сами функции, реализующие соответственно выборку следующего идентификатора и проверку существования идентификатора.

Select(Figure,Color)
 n res,names
 ; ставим функцию next и data для простого индекса
 s names(1,"next")="OrderSimple"
 s names(1,"data")="DataSimple"
 s names(1)=$na(^Index("Figure",Figure))
 ; ставим функцию next и data для битового индекса
 s names(2,"next")="OrderBit"
 s names(2,"data")="DataBit"
 s names(2)=$na(^Index("Color",Color))
 s names=2
 d ANDvi($na(res),.names)
 s res="" f  s res=$o(res(res)) q:res=""  d
 . w res,!
 q
 ;
ANDvi(ret,names) g ANDi+1
ANDi(ret,names...)
 n id,i,j,place
 s id="" f  s i=1,id=$$ANDnexti() q:id=""  s @ret@(id)=""
 q
ANDnexti()
ANDrepi
 s id=$$@names(i,"next")(names(i),id)
 q:id="" ""
 f j=i+1:1:i+names-1 s place=((j-1)#names)+1 »
  i '$$@names(place,"data")(names(place),id) s i=place g ANDrepi
 q id
 ;
#define BITSIZE (260000)
OrderSimple(ref,id) q $o(@ref@(id))
DataSimple(ref,id) q $d(@ref@(id))
DataBit(ref,id) q 
$bitfind(@ref@(id\$$$BITSIZE),1,id#$$$BITSIZE+1)=(id#$$$BITSIZE+1)
OrderBit(name,from)
 n ret,seg,pos s ret=0 s from=+from
 s seg=from\$$$BITSIZE s pos=from#$$$BITSIZE+2
 f  s:(seg'="") ret=$bitfind(@name@(seg), »
     1,pos) q:(ret)!(seg="")  d
 . s seg=$o(@name@(seg)) q:seg=""
 . s pos=0
 q:ret seg*$$$BITSIZE+ret-1
 q ""

Здесь вызовы

 $$@names(i,"next")(names(i),id)
 $$@names(place,"data")(names(place),id)

выполняют косвенный вызов метки по ее имени для выполнения необходимых операций, абстрагируясь от действительного типа индекса.

Анализ показывает, что мы действительно справились с задачей совместить в одной выборке разноструктурные битовые и древовидные индексы, и при этом количество избыточных операций увеличилось не намного, а именно осталось в линейных пределах.

В действительности, нам здесь очень сильно помог тот факт, что битовые индексы оперируют идентификаторами как натуральными числами (целыми и даже не отрицательными). Для них порядок арифметического следования совпадает с индексным упорядочением. Поэтому для обоих типов индексов удалось составить достаточно небольшое число абстракций и легко и понятно их реализовать.

Для операции ИЛИ выборка из индекса сводится к простой операции выборки идентификаторов по перечню индексов в одну структуру со слиянием. Результат также может быть по своей структуре как древовидной, так и битовой структурой.

Операция вычитания может быть сделана как операция выборки первого операнда в результирующую структуру, с последующей операцией выборки по второму операнду (вычитаемому), но вместо слияния выполняется удаление из результата.

Подробнее о книге "MUMPS СУБД"