Содержание к диссертации
Введение
ГЛАВА I
1. Основные определения 14
2 Алгебраическая модель информационной системы . 18
ГЛАВА II
I. Алгебраические свойства релевантных векторов . 21
2. Алгебраическая Ж - структура 28
3. Свойства Z- структуры 33
4. Продолжение Ж. - структуры 37
5. Переход к новому дескрипторному словарю 44
6« Метод Кодда сокращения размерности при решении поисковых уравнений (Модели поиска в библиотеке проблемно ~ ориентированных архивов) 50
7. Преобразования архива и линейные операторы 58
8. Псевдорелевантные векторы 62
ГЛАВА III
I. Алгебраические модели поиска в системах с нетривиальными коэффициентами 71
2. Построение псевдорелевантных подмножеств 78
8. Расширение множества запросов для систем с нетривиальными коэффициентами 82
4. Геометрическое описание поисковых функций в системах с непрерывными коэффициентами 91
5. Информационный поиск на многопроцессорных вычислительных средах 96
Список литературы
- Алгебраическая модель информационной системы
- Алгебраическая Ж - структура
- Метод Кодда сокращения размерности при решении поисковых уравнений (Модели поиска в библиотеке проблемно ~ ориентированных архивов)
- Построение псевдорелевантных подмножеств
Введение к работе
Информация является важным фактором, необходимым для деятельности любой системы - научной, технической, экономической, социальной и т.д. Совокупность информационных потоков, средств сбора, обработки и управления данными составляет информационную систему. Если эта система базируется на электронной технике, то мы получим автоматизированную информационно-поисковую систему (АИПС). Так как темпы роста объема информации во всех областях человеческой деятельности значительно опережают темпы повышения производительности труда персонала, занятого обработкой данных» то решение информационных проблем может осуществляться за счет использования мощной высокопроизводительной вычислительной техники, в том числе и многопроцессорных ЭВМ, новых средств и систем сбора, передачи и обработки информации. При разработке больших АИПС на одно из первых мест выдвигается задача минимизации времени реакции системы на запрос пользователя. Так поиск в архиве, содержащем 1Сг до-кументов, со скоростью 1,8-10 сек. на просмотр одного документа методом последовательного просмотра всех записей массива продолжается 5 часов. Увеличение скорости поиска невозможно только за счет увеличения быстродействия ЭВМ, необходимо искать новые методы обработки информации, ее поиска и хранения. С другой стороны, учитывая высокую стоимость труда создателей математического обеспечения и т.flv необходимо научиться разрабатывать достаточно простые по структуре методы обработки, уметь сравнивать между собой различные методы поиска, на основе которых можно было бы принимать обоснованные решения о выборе архитектуры вычислительной среды и методов обработки информации при проектировании конкретных АИПС.
Информационный поиск по запросу пользователя есть задача определения релевантного запросу подмножества документов в архиве АИПС. Каждое сравнение признаков, заданных в запросе, с признаками в описании документов, требует доступа к массиву, скорость обмена с массивом больших систем мала по сравнению со скоростью обработки. Таким образом при оценке эффективности поиска необходимо учитывать и время обмена данными между внешними запоминающими устройствами и центральным процессором.
Для общения пользователя с АИПС необходим язык максимально полно описывающий данные архива, достаточно простой для пользователя и воспринимаемый ЭШ, такой язык называется информационно-поисковым языком (ИПЯ). Каждому элементу словаря информационной системы естественно поставить в соответствие некоторый шифр, который назовем поисковым образом данного элемента словаря. Процесс сопоставления элементов словаря соответствующему шифру называется индексацией. Используя процесс индексации можно построить индексный язык - поисковый образ ИПЯ, индекс документа - поисковый образ документа (ПОД). Принято отождествлять понятия "индекс" и "поисковый образ".
Мы сознательно сузили понятие поискового образа только на числовые множества. Исторически термин "поисковый образ ИПЯ" возник в библиотечных ИПС и означал утвержденный словарь с малым количеством слов - дескрипторов для описания краткого содержания документов архива. С появлением ИПС на базе ЭШ и записью документов на магнитные носители естественно перенесли понятие "поисковый образ" на числовые множества. Таким образом элементом информации, хранящейся в архиве АИПС, является код (шифр) дескриптора. Элементы ИПЯ называются дескрипторами, множество дескрипторов с соответствующим синтаксисом называется дескрипторннм словарем; индекс дескриптора будем называть значением дескриптора.
Далее будем предполагать, что запрос формулируется на языке описания документов - ЙПЯ. Это условие можно ослабить, допустив существование взаимнооднозначного транслятора с языка запросов на язык описания документов.
Существующие АИПС имеют, как правило, два массива информации: массив данных - архив системы, назовем его поисковый образ архива (ПОА), где проводится поиск релевантного подмножества, и массив дескрипторного словаря, с помощью которого ведется дешифровка и анализ информации. Большинство современных больших АИПС имеют массив данных, состоящий из двух подмножеств, размещенных в ЗУ:
1) Поисковый образ архива (ПОА) - записи на ИПЯ самих документов.
2) Поисковый образ записей архива (ПОЗА).
Суть такого двойного архива заключается в следующем: если в архиве запись некоторого документа представляет набор шифров дескрипторов и их связей, то в ПОЗА запись, соответствующая этому документу, представляет собой вектор из нулей и единиц, построенный по следующему правилу. Упорядочим элементы дескрипторного словаря и отождествим номер дескриптора с номером координаты вектора - поискового образа записи документа (ПОЗД). Соответствующая координата вектора равна нулю, если данный дескриптор отсутствует в описании документа, и единице, если он присутствует. ПОЗА обладает рядом преимуществ:
1) для его хранения в ЗУ требуется память меньшего объема, т»к., например, векторы можно хранить в упакованном виде;
2) алгоритмы поиска в ПОЗА более просты и работают с большей скоростью. Информационный поиск сначала ведется в ПОЗА, где отбираются ПОЗД, содержащие дескрипторы, указанные в запросе, далее на множестве отобранных записей, происходит сравнение критериев запроса с ПОД, т.е. построение релевантного множества. Построение ПОЗА увеличивает общий объем занимаемой памяти, но, как правило, дает возможность сократить время поиска релевантных документов.
Исследования задач и методов информационного поиска привели к построению различных моделей ИПС ([б] , (, [46], [54J, [55}). Необходимо отметить теоретико-множественную модель Сэлтона ([45] ), теоретико-множественную основу имеют многие последующие модели, так Сибли Э. и Хардгрейв Т. ([43І, [5) считают, что "теория множеств оказывается наиболее верным кандидатом в качестве технологии выражений моделей данных". Основным недостатком теоретико-множественных моделей является либо их абстрактность, либо их громоздкость.
Наибольшее распространение получила реляционная модель Кодда ([54], [55]). В этой модели между отдельными элементами информации, как элементами множества различных данных в архиве, строится алгебра отношений. Знание образующих и операций в этой алгебре позволяет получать релевантные документы или интересующие части этих документов (Й - \10\9 Ц31» L47J» С56!) Показано, что всякий запрос в терминах реляционной модели полиномиально вычислим ([23J )• Концепция реляционной модели Кодда предполагает существование однозначных отношений между отдельными частями ПОД и возможность при помощи этих отношений получить искомую информацию. Громоздкость программного обеспечения является одним из недостатков реляционной модели. Последнее время для совершенстваования моделей АИПС привлекают теорию нечетких множеств ([43], [ь&\).
Построение математической модели, которая дает возможность сравнивать между собой различные архитектуры массива данных и свя занных с ними стратегий поиска, строить новые методы поиска информации, является важной задачей теории информационного поиска. Решая задачу сокращения времени поиска, разработчики обратили внимание на изменение времени поиска одной и той же информации при изменении структуры множества ПОА или ПОЗА, За образец была выбрана прямая структура архива и поиск последовательным перебором всех записей. Построение новых архитектур и методов поиска ставит задачу улучшить количественные характеристики, оптимизировать методы хранения и поиска информации для больших массивов. Так появились инвертированные массивы, многосписковые структуры, кластерные архитектуры и т.д. ([44]). Наибольший интерес, с нашей точки зрения представляет кластерная архитектура ([44J , 4б, \&&[), которая относится к классу многоуровневых архитектур. Основная идея заключается в следующем: множество Т - поисковый образ архива или ПОЗА разбивается на несколько подмножествТ1э...,,Т1 , векторы каждого из подмножеств рассматриваются как векторы одного вещественного линейного пространства и строятся множества Т-, , нормированных векторов (переход от вектора "t к вектору jWih )• Каждому подмножеству Т „ ставится в соответствие вектор с - ffc-ll» где С;, является центром тяжести множества T-v (еслиТ\,- 4: ... j , то С-= г- Е. "t; ). По запросу строится вектор запроса \ и среди векторов (-і ищутся те, которые наименее отклоняются от , т.е. решается задача минимизации агссоь о \\ по всем = і,к . Поиск релевантных векторов проводится только в тех подмножествах Tv , центроидальные векторы - с-и которых являются решениями задачи минимизации. Поиск внутри отобранных множеств \, , как правило, ведется прямым перебором. Недостатком кластерной организации массива данных являются потери релевантных векторов. Данные, полученные при эксплуатации АИПС SIV7ART( (4, (бЗ]), показывают, что потери релевантных документов достигают 50$, что не может считаться удовлетворительным•
Эксплуатация АИПС, особенно библиотечных, показала, что оценка полноты множества выданных документов наталкивается на несоответствие потребностей пользователя сформулированному запросу. Это может происходить или из-за недостаточного опыта общения с АИПС, или нечетких собственных критериев (например, в библиотеке часто встречаются утверждения типа и... автор, кажется, Иванов"). Отсюда возникла задача: не меняя запроса пользователя расширить предлагаемое ему релевантное множество, т.е. найти не только документы, релевантные запросу, но и похожие на них. Одним из подходов к решению такой задачи является "поиск с обратной связью" ((44() • Пользователь, после просмотра предложенного ему релевантного запросу множества, отмечает документы, если они присутствуют, действительно, удовлетворяющие его информационным потребностям, и на основании анализа этих документов строится подправленный запрос, который вводится в систему и т.д. Другой подход заключается в том, что фиксируется некоторая мера подобия f и выбирают такие "t векторы ПОА, а чаще всего векторы ПОЗА, которые минимизируют ffc, \)» где а вектор запроса. Для поиска бинарных векторов в ПОЗА использовали меры, так например:
Мера Танимото ([65]) rr\ p(±, \) = izi .Z, + 2- - Z VІ1 Мера Евклида - Сэлтона (\44І, [б з[): ? -і 1,-1 .=.( Мера Мэрона (\ЪЭ\): m , vv\ — _ #л - — бинарные векторы, причем «fy - • Однако использование этих мер не дало существенного расширения релевантного множества, а поиск с их применением происходит медленно, в основном методом перебора всего архива. Очевидно, что без построения соответствующей математической модели информационного поиска в широком смысле и привлечения современного математического аппарата невозможно найти решение задачи построения эффективных мер подобия и соответствующих алгоритмов поиска векторов, похожих на релевантные.
Выше были рассмотрены пути повышения эффективности информационного поиска за счет разработки новых методов хранения и обработки информации» Другой путь связан с созданием многопроцессорных ЭВМ, Многопроцессорные вычислительные среды позволяют сократить время поиска, обработки информации и снизить затраты на поиск. Для успешного применения такой электронной техники необходимо создать свои методы и алгоритмы, позволяющие полностью использовать преимущества параллельных вычислений. Формальное распараллеливание существующих алгоритмов, как правило, не дает линейного ускорения по числу процессоров среды и не обеспечивает полной загрузки процессоров при проведении информационного поиска. Разработка соответствующего математического обеспечения для АИПС на базе многопроцессорных ЭВМ является одной из важнейших проблем в настоящее время.
Таким образом решение задачи повышения эффективности информационного поиска базируется на сочетании двух подходов: I) разработке соответствующих математических моделей информационного поиска, привлечение к их анализу современного математического аппарата и на этой основе получении обоснованных рекомендаций по организации поиска, построении новых методов хранения и обработки информации, 2) использовании многопроцессорных ЭВМ для работы АИПС, создание методов организации и поиска, ориентированных на такую вычислительную среду.
В настоящей диссертации предлагается математическая модель информационного поиска, которая сводит задачу организации и поиска данных к поиску решений системы линейных алгебраических уравнений на конечном множестве конечномерного линейного пространства. Система линейных алгебраических уравнений строится по входному запросу, размерность линейного пространства совпадает с числом элементов дескрипторного словаря. Показано), что между известными архитектурами поискового образа архива и различными методами поиска, с одной стороны, и, с другой стороны, методами решения системы линейных алгебраических уравнений на конечном множестве существу ет взаимнооднозначное соответствие. Для решения поисковой системы линейных алгебраических уравнений на конечном множестве предлагается метод Ж - структуры» Для случая поиска в ПОЗА, когда поисковая задача решается в линейном пространстве над полем Ж & (далее мы его назовем - системы с тривиальными коэффициентами), подробно исследованы свойства 2 - структуры, условия её оптимальности, как по числу элементов разбиения, так и различных способов разбиения на фиксированное число подмножеств. Предложены модель и алгоритм сокращения размерности при проведении поиска, когда отдельные группы данных имеют собственную проблемную ориентацию и могут обрабатываться как в совокупности, так и раздельно. Использование алгебраических свойств векторов позволило определить псевдорелевантные векторы через псевдорешения поисковой системы, тем самым найти решение задачи поиска документов, "похожих" на релевантные, предложен алгоритм поиска псевдорелевантных векторов. При моделировании поиска в ПОА векторы - поисковые образы документов принадлежат линейному пространству либо над конечным полем 2.р , р?2 t либо с вещественными коэффициентами, этот случай мы далее будем называть "системы с нетривиальными коэффициентами". На системы с нетривиальными коэффициентами перенесен метод Z -структуры, а для вещественного случая построена геометрическая интерпретация информационного поиска, в которой задача поиска релевантных векторов сводится к проверке на совместность поисковой системы линейных алгебраических уравнений и неравенств. Дія АИПС на базе многопроцессорных ЭЕМ предложены: метод физической организации 2d - структуры в памяти ЭВМ и стратегия поиска, позволяющие при обработке любого запроса добиться полной загруженности всех процессоров системы и линейного, по числу процессоров, уско рения информационного поиска.
Основные положения диссертации
В работе построена алгебраическая модель информационного поиска, которая сводит задачу организации и поиска к задаче решения поисковой системы линейных алгебраических уравнений на конечном множестве; предложен метод решения таких систем - метод Ж -структуры, который позволяет строить релевантные и псевдорелевантные множества и который эффективен при организации информационного поиска на многопроцес -сорных ЭВМ.
Методы, предложенные в диссертации, были использованы:
1. При разработке автоматизированной информационной системы "Подготовительное отделение", которая работает в МГУ с 1975 г. ;
2. При разработке автоматизированной системы регистрации землетрясений, внедренной на геологическом факультете МГУ в 1979 г. ;
3. При создании автоматизированной системы "Олимпийский арбитр-80", разработанной по заказу Оргкомитета "Олим-пиада-80" ;
4. При создании информационного обеспечения для автоматизации планирования производства и раскроя трикотажного полотна на МПТО "Красная заря".
Результаты, изложенные в диссертации, являются основой курса лекций "Алгебраические модели информационного поиска", читаемого на факультете вычислительной математики и кибер -нетики МГУ с 1978 г.
По теме диссертации опубликовано 17 работ.
2 Алгебраическая модель информационной системы
Пусть А-{а±у, Я. ,] конечное множество, задано отображение г Т— г , где Р - некоторое числовое множество, d определяющий дескриптор. Предположим, что элементы множеств А и і упорядочены таким образом, что сКа-и)= "Ьи } ІєІ,
Пусть с . ,.. ., 0 i - элементарные дескрипторы, порождающие сА . Рассмотрим такое отображение, которое обозначим 4 j что tod » jn AM— ""vP!L jLp и поставим в соответствие каждому О-с -А . І--ІЛ, вектор H Cii,!;,..-, "ti.m) » где Ощ?едедение. Вектор и ъ называется поисковым образом элемента CL\, t = i,vu . Множество поисковых образов объектов &l /v=l.vt обозначим через , т.е. Т=0М)ҐА). Множество і называется поисковым образом архива 1 .
Обозначим через Р минимальное поле, содержащее Р и пусть V -линейное пространство размерности гтг над полем I . По построению, векторы ТІ, ,1=1,И/ , принадлежат линейному пространству у над полем і , а множество I является конечным множеством линейного пространства над полем Г . Если i , e-m канонический базис линейного пространства V над г , то каждый вектор Х и можно предста-I = 2» t r - , t=4., . Линейное пространство V называется линейным пространством архива I . Далее мы будем считать, по определению, что \ ( ) = О . Пусть дан запрос о \ \.di. , t г. ); і є Н J » поставим в соответствие с поисковый образ запроса 3 = Множество отображений fd u А— Т обозначим Х и назовем его поисковым образом дескрипторного словаря 3 . Запросу с/ поставим в соответствие вектор % i% - -j ) линейного пространства "V над полем Р , где о = J r ) если Кя1І ІбН 1 0 в остальных случаях. Вектор CL называется вектором запроса о .
Множество поисковых образов всевозможных запросов їх является множеством всех подмножеств в где !«! = \ f Ji, Д- Ъ).
Пусть V - линейное пространство архива, с, - вектор запроса, причем \/if » для t 1 . =0 для ї-е-І 2 где 1± - множество индексов дескрипторов, содержащихся в запросе CL без знака логического отрицания, I $ - множество индексов дескрипторов, содержащихся в \ со знаком логического отрицания.
Обозначим 1= і, -;уи] , тогда І" І-іиІ Із., причем естественно потребовать 1 п 1- — jZ/ , t j., где 1 - множество индексов дескрипторов, не содержащихся в запросе С . Определение. Вектор OCC io -j -"O V" называется вектором, релевантным запросу q, , если
Легко видеть, что определения документа, релевантного запросу, и вектора, релевантного с\, , согласованы. Если вектор ОС в V релевантен запросу q, и ОС -f « d (А) , то вектор X однозначно определяет документ X: \ , релевантный запросу О .
Определение. Алгебраической поисковой функцией называется отображение tp : Q — А , которое каждому поисковому образу запроса о (2 ставит в соответствие множество 1\с =УЛ6) такое, что для каждого СІ Є Кп выполняется соотношение MtjCabfCr,), j H. Определение. Совокупность называется алгебраической моделью информационно-поисковой системы. Далее мы ограничимся рассмотрением случая,когда: 1) А - конечное множество; 2) Если Л определяющий дескриптор, то T o(A)j т.е. А - взаимнооднозначное отображение; 3) Дескриптор Л порождается элементарными d ± } .. v J 4) Множество і является полем, т.е. Р"Р При сделанных ограничениях поисковый образ архива Is (fe«U(AJ является конечным множеством в линейном пространстве "V над полем і размерности m. .
Задача информационного поиска в этих условиях сводится к следующей: По заданному поисковому образу запроса Q, найти такое подмножество К. векторов в Т — V f что где к СА - множество объектов, релевантных запросу fy, . Последнее следует из взаимнооднозначное отображения о , отображение f однозначно по построению.
Отображение у называется отображением индексации. Числа і00 ."О 0 называются весом дескриптора d в до-кументе Т = dC&iJ j Is i.fc =4-, В этой главе рассмотрим случай, когда множество Р совпадает с полем -2 , что соответствует информационным системам с тривиальными коэффициентами. Построим отображение : Пусть (Ц А ; І"С » дескриптор el ставит в соответст-виє (Х- документ "t = а (.а ) ; ii ; дескрип тор d порожден элементарными а..., Jm Поставим л в соответствие каждому документу tj вектор Х- «ttjij... ХЧт) линейного пространства V над полем -2. размерности пъ_, координаты которого равны
Алгебраическая Ж - структура
В этих условиях поиск релевантных векторов ведется следующим образом. На множестве U , как правило, последовательным просмотром ищут векторы, релевантные запросу Q ± . На множестве векторов тех зон, которые релевантны запросу Q , проводится поиск векторов, релевантных запросу Q ,
Построим алгебраическую модель рассмотренной выше структуры множества і и стратегии поиска релевантных векторов.
Пусть I - подмножество линейного пространства "V" над полем размерности m , е,,.., - канонический базис линейного пространства V" Рассмотрим разбиение множе-ства I на конечное число непересекающихся подмножеств Tl T UdLK, где Т гчТ; «0 для l j vT.
Пусть i j ... ,М- векторы подмножества 1 , где "tj j 4 \ ь j i - t разложение X: в каноническом базисе линейного пространства V над полем 2_. Каждому множеству I \, , і -1, к , поставим в соответствие характеристический вектор U подмножества I , где
Множество v \У \,] характеристических векторов назовем характеристическим множеством первого уровня. Аналогично, если задано разбиение множества V на конечное число непустых непересекающихся подмножеств, то можно построить \) - характеристическое множество второго уровня.
Определение, Совокупность jT f V ... j U j мно жеств Т , разбиения \\ Л » характеристического множест ва первого уровня VJ , характеристического множества второго уровня v и т.д., называется Ж - структурой множест ва . Элементы разбиения \ \,) , \Уі ] и т.д. называют -ся зонами соответствующих множеств.
Как отмечалось ранее, мы предполагаем,что запрос \ име ет следующий вид: дескрипторы Л Ai содержатся в \. без логического отрицания, &\ г- Ч 02 1 в Я/ с логическим отрицанием.Представим запрос Cj, в виде Э=Я\?- , где % іу-, J ) » Уі г-v О . Тогда запросу 1 соответствует пара,которую обозначим (Ка,,Ц/) » а запросу с -пара (Aq,, ) , причем поисковое уравнение Ac ty ЯВЛЯеТСЯ Объединением уравнений АеЭС = fy и Ае . Следовательно,система линейных уравнений A VOC=SJ; (5) распадается на две системы
Пусть заданы множество Т ,его конечное разбиение Т;Д и vJ \_U-LJ - характеристическое множество перво -го уровня.Имеет место теорема: ,
Теорема 2. Пусть вектор tg е- і і является решением системы Aq = fy » тогда характеристический вектор Uif О является решением системы Лс Х= 0 Доказательство. Без ограничения общности предположим, что первые « координат вектора 0 равны I, остальные равны нулю, соответственно, элементы Ац. j -з 5 4 матрицы Aq. равны I, остальные равны нулю; тогда в матрице Ал не равны нулю элементы С . ... Я . Если вектор "t является решением (5), то первые oL координат этого вектора равны I, координаты с номерами «u-lj .3 і равны нулю, координаты 4+ij ..., m могут принимать любые значения из поля - 2. » т,е разложение вектора і іо в каноническом базисе имеет вид 10 Следовательно, векторы е 3 ... е„Л содержатся в разложении характеристического вектора fU;e с ненулевыми коэффициентами, откуда А Я.
Следствие I. Пусть "U характеристическое множество L -уровня t t, IUM - разбиение U на непересекающиеся подмножества, "U - соответствующее характеристическое множество уровня 1 + L.. Если вектор т Є vi,0 является решением уравнения (б), то и характеристический вектор зоны U«Uo также является решением уравнения (6). Следствие 2. Если характеристический вектор "Н-- зоны 1 ю не является решением системы (б), то ни один вектор "и. 6 Tv,0 не является решением системы (5).
Таким образом, на основании теоремы и следствий 1,2, мы можем предположить следующую стратегию поиска векторов, релевантных запросу о , на конечном множестве Т , снабженном Ж-структурой. Среди векторов характеристического множества U высшего уровня ищем решения системы (б): если решений нет, то векторов л.1 і , релевантных сз на множестве I j нет; если решение существует, то переходим к поиску решений (б) среди векторов тех зон С "0 уровня, характеристические векторы которых являются решениями системы (б) и т.д. На последнем этапе получим зоны множества I (если они существуют) , характеристические векторы которых являются решениями системы (б). На множестве векторов,полученных зон, мы будем искать решения системы (5), т.е. векторы,релевантные запросу О,. Легко видеть, что удачно выбранная 2" -структура множества Т может сократить время поиска векторов "Н . релевантных запросу.
Метод Кодда сокращения размерности при решении поисковых уравнений (Модели поиска в библиотеке
В настоящее время широкое распространение получил реляционный подход к изучению систем баз данных, основу которого заложил Е.Кодд в работах _54\, [5j. По К.Дейту [joj, "реляционное вычисление представляет собой просто набор правил для записи выражения, определяющего некоторое новое отношение в терминах заданной совокупности отношений, другими словами, реляционное исчисление есть метод определения того отношения, которое нам желательно получить (как ответ на запрос) в терминах уже имеющихся отношений (отношений в базе данных)". Как отмечалось, реляционное исчисление есть операции над отношениями. Под отношением принято понимать таблицу однотипных данных, входящую в базу данных. Можно считать, что база данных это заданный набор различных отношений. Строки таблиц (отношений) называются кортежами, столбцы - атрибутами. Множество значений элементов данной таблицы называется доменом. Примеры отношений и определения операций реляционного исчисления можно найти, например, в [l6\.
С другой стороны, организация работы автоматизированных информационно-поисковых систем с информационной базой большой размерности и большой мощности сталкивается с трудностями хранения и обработки данных. Одним из способов преодоления этих трудностей является создание автоматизированной библиотеки проблемно-ориентированных архивов. Такие библиотеки, естественно, возникают при разработке автоматизированных систем управления производством -данные по цехам, складам и т.д., где данные характеризуют работу подразделения и поступают из своего проблемно-ориентированного ис точника. При автоматизированной обработке результатов научных экспериментов имеел? смысл создавать автоматизированные библиотеки -архив используемой литературы, архив приборов, установок с характеристиками, архив результатов экспериментов и т.д. Проблемная ориентация этих архивов может дополнительно разделяться по научным направлениям. Если поступающие в такую библиотеку запросы относятся только к одному проблемно-ориентированному архиву, то поиск в нем описывается методами, разработанными в 1-5. С другой стороны, возможны запросы, обращенные сразу к нескольким архивам, например, информация о выполнении плана предприятия в целом. Если объединить все вышесказанное, то придем к отождествлению проблемно-ориентированного архива и отношения. Таким образом для сокращения размерности решаемой задачи на каждом отдельном этапе можно воспользоваться реляционным методом Кодда.
В настоящем параграфе будет построен метод решения поискового уравнения (метод борьбы с размерностью), который сводит исходную задачу к аналогичным задачам на подпространствах заведомо меньших размерностей, чем dlmY и построены геометрические аналоги операций реляционного исчисления. Таким образом будет доказано, что реляционный метод Кодда есть один из методов решения поискового уравнения Ао ри-Ц/ на конечном множестве Т . Результаты этого параграфа можно также рассматривать как линейную алгебраическую интерпретацию реляционного подхода Кодда.
Далее; будем считать, что числовое поле Р является общим доменом для всех отношений данной базы данных. Результаты настоящего параграфа справедливы не только для случая Р- . , но и для других числовых полей. Далее везде предполагается, что в линейном пространстве V выбран базис et v Єт , а все рассматривав мне линейные пространства порождаются некоторым подмножеством данного базиса. Пусть L;, t і,к , « mL;,88 , линейное подпространство линейного пространства!/ , порожденное е ... е , векторами канонического базиса е1э...дет линейного пространства V , "VеL ... ! к ч - оператор проекции на линейное подпространство L» v $ -- Тогда поисковый образ документа t I , l-i. , порожденного документом х е I связан с поисковым образом "L I следующей формулой rKx=t , ь=1Л .
Определение. Множество ГГЇ Т- Т. , Ui,id , называется поисковым, образом проблемно-ориентируемого архива 1\ , 1-і.к.
Операцию построения множеств Ч у..;Тк можно описать следующим образом: представим множество Т в виде матрицы, столбцами которой являются векторы "tj.r..5 t Разбиение матрицы Т на зоны по строкам соответствует построению подмножеств Т . j..., Т При построении зон по строкам необходимо учитывать, что по каждому вектору і: для ь-4_,\с мы должны уметь восстановить "
Построение псевдорелевантных подмножеств
В 1,2 настоящей главы мы рассмотрели случай, когда числовое множество Р совпадало с конечным полем Ж С другой стороны, архивы естественно-научных экспериментов являются характерным примером, когда дескриптор может принимать значения в непрерывном множестве (например, температура в опыте непрерывно менялась от 20 до 500).
Таким образом, естественно рассмотреть случай, когда либо г -хк, - вещественная прямая, либо ± - отрезок на прямой ІК, . Легко видеть, что в нашем случае Т= 11г.., j - поисковый образ архива представляет собой конечное множество в линейном пространстве v над полем (К размерности vw , где vn - число элементарных дескрипторов А 3 ... А дескрипторного словаря . Как и ранее через А і обозначим отображение \ \,- 1 t -Ь-С Пусть Ті=-1 Щ область допустимых значений отображения а к,- 4- . . Мы ограничимся рассмотрением случая I - L&l, ti J Ч .
Определение, Фазовым информационным параллелепипедом называется множество 1 - \jj- ... у L w\ , где i«t область допус i/ t тимых значений отображения Л ъ-iy . Число Yn - на зывается размерностью фазового информационного параллелепипеда. Поисковый образ каждого объекта ft.;, , t-іЛ t пред ставляет собой точку в 1 .С другой стороны, произвольную тт. точку 1 _ можно рассматривать как некоторый документ, может быть формальный.
Если d і составной дескриптор, порожденный элементарными сч...,%. J;, »то легко видеть, что область допустимых значений Ґ1\, отображения \ о\, представляет собой соответствующую грань фазового информационного паралле-лепипеда 1 , причем где ±. - область допустимых значений отображения 1 — \ 1 і і/. о Пусть задан запрос V - \_С ] , С-) , j = 4.Д j / я с где O-L,. - -f = {,? } :_ і,я , Bv; - область изменения значений t- интересующая пользователя. Если jVt .= В ,. Л ГІ.= С? ,то, очевидно, запрос противоречив и векторов, релевантных запросу О в I нет, К. у = р . Если множества sil. непустые, то перейдем к рассмотрению о запроса где множества Условия на представления запроса, если использованы логические функции "и", "или", сформулированные в гл.1, I, переносятся на случай непрерывных коэффициентов без всяких изменений.
Если запрос су сформулирован с использованием логического отрицания, например, V" t l (d , М0\ »то последнее означает , что нас интересуют объекты & & К , для которых образ отображения о d- d. J\[»v , следовательно, запрос Q эквивалентен запросу 0 -=. \ (_ J« j М \ -WI} Т. Таким образом, если мы говорим "задан запрос", мы подразумева ем, что он преобразован к виду
Используя замену переменных типа У / мы можем считать, что область изменения 1 с отображения а есть отрезок Рассмотрим запрос а, вида (44). В фазовом информацион-ном параллелепипеде 1 для каждого номера ь- \ -i,3 построим цилиндр Л/ . JV .X 1 , где I- L«1J dim X/l- t W. Размерность Jim ЛІ С- определяется как размерность ли нейной оболочки множества JJi. . .С другой сто роны, dlvw J/i. совпадает с числом элементарных дескрипторов, порождакщих dv- д = 1Л . Нижним основанием цилиндра Мl. является Ml. (. , )) , верхним основанием - множество JVC. л ( L, -, -) = ; .Множество Mq= Ж: называется областью релевантности. Теорема 9, Отображение ЛІГ \\ — 1 такое, что 1 X , если ОС -1 = \ , если ОС Хг ; совпадает с поисковой функцией tfо (см. гл.1, 2) на множестве
Доказательство. Действительно, всякая точка ОС- цилинд pa -Nu. , 1 = -Л , обладает тем свойством, что ее координаты ОСL: \-0 » лежащие в грани г\ 1- изменяются в области Jvu- } -ІЛ . Пересечение цилиндров V= Ci 1-эквивалентно требованию выполнения всех ограничений запроса ldlj\ .Nij і" і Л » одновременно, откуда и из определения релевантных векторов следует утверждение теоремы.
Следствие. Если J\I о f) , то 9 о р. Пусть А! I j 1-4-- } является выпуклым множеством, тогда цилиндр Я і- совпадает с выпуклой линейной оболочкой множеств Ml. и t. . Дополнительно предположим, что множе 11 \ —.6 ства JVC« , v - 4-, являются выпуклой линейной оболочкой Л л Лг точек - вершин АІД. ... _ A vc. , Ц Тогда цилиндр J\l t -4-Л описывается следующей линейной системой уравнений и неравенств
