Инвертированные списки

Cтраница 1

Инвертированные списки для дескрипторных полей содержатся в ассоциаторе и используются для разрешения поисковых запросов последовательной логической обработки И установления связей между файлами. Логические записи данных содержат значения полей и размещаются в области хранения данных БД. [1]

Рис, 27.9. Инвертированные списки ( представленные битовыми строками, Эта организация файла подобна тойв которая представлена на рис. 27.7, Исключением здесь является то, что битовая строка используется для индикации содержимого участка. Использование битовой строки приводит к более компактному индексу по сравнению с рис. 27.7. Однако это не всегда так. Экономичность этого способа ( по сравнению с предыдущим) зависит от общего числа участков записей и от доли тех участков, в которых присутствуют значения всех вторичных ключей ( рис. 18.9), Использование индекса в виде совокупности битовых строк отличается тем, что в этом случае сортировка и разбиение записей данных на связанные множества ( рис. 27.8) не дает выигрыша в использовании памяти, но уменьшает число участков записей, которые необходимо просматривать при ответе на конкретный запрос. [2]

Структура обработки данных. [3]

Сеть связи содержит инвертированные списки, необходимые для эффективной обработки запросов пользователей. [4]

Ассоциативная сеть содержит инвертированные списки значений, необходимых для эффективной обработки поисковых запросов к БД. Поля, используемые в качестве ключа поиска, в СУБД Спектр называются дескрипторными. Для каждого дескрипторного поля создается и хранится список инвертированных значений. Этот список содержит для каждого значения дескриптора список номеров ISN, в которых это значение встречается. Объем внешней памяти для ассоциатора БД составляет 30 - 40 % объема области хранения данных. Зти расходы компенсируются за счет сжатия данных в базе. Объем внешней памяти для БД обычно меньше, чем объем пгрвоначальных ( исходных) данных. [5]

Для атрибута, определенного как ПОИСКОВЫЙ, система строит инвертированные списки, которые ускоряют поиск требуемого подмножества записей. [6]

Естественно, что списки указателей для каждого значения вторичного ключа ( инвертированные списки) имеют переменную длину, причем такие списки перемешаны: среди большого числа коротких списков изредка встречаются очень длинные, что обусловливает неравномерность их статистического распределения. Например, среди множества немецких слов, согласно известному экспериментальному закону Зин-фа, примерно 50 % всех слов появляется всего один раз ( длина инвертированного списка равна единице), причем это практически не зависит от мощности множества. Слова, появляющиеся два раза, составляют примерно 1 / 4 всех слов; слова, появляющиеся п раз, будут составлять не более 1 / гс2 всех слов. С другой стороны, наибольшая частота появления всех слов, естественно, пропорциональна величине множества, однако слова с высокой частотностью появляются всего лишь один раз на 10 литературных источников. [7]

Нслп для всех записей, хранящихся в базе данных, созданы инвертированные списки для возможных вариантов запросов, то такая база данных называется инвертированной. Инвертированные БД широко используются в информационно-поисковых системах ( ИПС), предназначенных в основном для хранения текстовых документов. Признаки, по которым отыскивается необходимый документ в ИПС, называются дескрипторами. Для каждого дескриптора в ИПС строится инвертированный список, содержащий все возможные значения дескриптора и соответствующие им множества указателей на документы. Запрос в ИПС имеет вид логического высказывания относительно значений дескрипторов и их взаимосвязи. [8]

Ассоциатор содержит системные управляющие таблицы, формируемые для управления БД, преобразователь адреса, а также инвертированные списки и списки связи. [9]

Для ускорения операций поиска некоторые атрибуты файла могут быть определены как поисковые и по их значениям система сформирует инвертированные списки. [10]

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

Физически база данных разделена на две области: область данных, куда вводится информация в уплотненном формате по мере поступления в СУБД, и область ассоциатора, куда вносятся инвертированные списки и адресный преобразователь, позволяющий определить физическое местонахождение записи. Любое изменение местонахождения записей приводит только к изменению адресного преобразователя. [12]

АССОЦИАТОР [ associator ] В некоторых СУБД - справочник базы данных, содержащий управляющие таблицы, необходимые для управления базой данных: таблицы описания полей, преобразователь адреса, инвертированные списки, списки связи. [13]

Некоторые атрибуты логической структуры файла могут быть определены как поисковые. По значениям этих атрибутов формируются инвертированные списки, используемые для ускорения поиска требуемого подмножества записей. [14]

Кроме механизма межфайловых связей, некоторые атрибуты записи в логической схеме могут быть определены как поисковые атрибуты. По значению этих атрибутов формируются инвертированные списки, значительно ускоряющие процесс поиска затребованных записей. Все файлы в СУБД ДИСОД доступны для вхождения и поиска необходимой информации. [15]

Страницы: 1 2