Лекция 5. Поиск информации . . Лекция 5. Поиск информации

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

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

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

Языки запросов

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

Предписания формулируются в терминах реальных структур данных, хранящихся в базе данных (например, SQL) Предписания формулируются в терминах абстрактных структур и схем данных (например, LDAP) Предписания формулируются в терминах абстрактных поисковых образов (например, RPN для Z39.50)

Язык запросов SQL (Structured Query Language)

Язык SQL для создания, модификации и управления данными в произвольных реляционных СУБД.

История языка как стандарта ANSI начинается в 1986 году (ANSI SQL-86). Последний вариант - SQL:2008 (ISO/IEC 9075-*:2008).

Несмотря на обилие команд, предусмотренных в SQL для поиска информации используется фактичеки только одна - команда SELECT. Упрощенный вид этой команды таков:

SELECT {список извлекаемых элементов}

НЕ нашли? Не то? Что вы ищете?

FROM {список источников}

WHERE {условия отбора данных}

ORDER BY {список условий сортировки извлекаемых данных}

GROUP BY {список условий для группировки извлекаемых данных}

OFFSET {смещение начала выдачи}

LIMIT (FETCH) {количество извлекаемых записей}

К поиску информации относятся только условия отбора данных, указанные в области WHERE. Условие отбора в SQL есть любое логическое выражение, операндами которого могут быть значения полей и допустимые функции от них.

Отметим, что условия отбора данных в SQL формулируются в терминах имен полей реальных таблиц, т. е. для создания запроса на поиск информации требуется знать структуру базы данных и ее таблиц. Пример:

SELECT * FROM publication WHERE pub_title like 'Система%'

Здесь подразумевается, что таблица "publication" имеет поле "pub_title" строкового типа.

Поиск в LDAP

В LDAP для поиска информации в распределенном каталоге используется своя система запросов.

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

Структура поискового запроса (поискового фильтра в терминологии LDAP) определена в терминах ASN.1

Filter ::= CHOICE {

and [0] SET OF Filter,

or [1] SET OF Filter,

not [2] Filter,

equalityMatch [3] AttributeValueAssertion,

substrings [4] SubstringFilter,

greaterOrEqual [5] AttributeValueAssertion,

lessOrEqual [6] AttributeValueAssertion,

present [7] AttributeDescription,

approxMatch [8] AttributeValueAssertion,

extensibleMatch [9] MatchingRuleAssertion

}

SubstringFilter ::= SEQUENCE {

type AttributeDescription,

SEQUENCE OF CHOICE {

initial [0] LDAPString,

any [1] LDAPString,

final [2] LDAPString

}

AttributeValueAssertion ::= SEQUENCE {

attributeDesc AttributeDescription,

attributeValue AttributeValue

}

MatchingRuleAssertion ::= SEQUENCE {

matchingRule [1] MatchingRuleID OPTIONAL,

type [2] AttributeDescription OPTIONAL,

matchValue [3] AssertionValue,

dnAttributes [4] BOOLEAN DEFAULT FALSE

}

AttributeDescription ::= LDAPString

AttributeValue ::= OCTET STRING

MatchingRuleID ::= LDAPString

AssertionValue ::= OCTET STRING

LDAPString ::= OCTET STRING

Именно такая структура, естественно, BER-кодированная, передается клиентом серверу LDAP для исполнения. Для удобства стандартом предусмотрено текстовое представление структуры фильтра.

filter = "(" filtercomp ")"

filtercomp = and / or / not / item

and = "&" filterlist

or = "|" filterlist

not = "!" filter

filterlist = 1*filter

item = simple / present / substring / extensible

simple = attr filtertype value

filtertype = equal / approx / greater / less

equal = "="

approx = "~="

greater = ">="

less = "<="

extensible = attr [":dn"] [":" matchingrule] ":=" value

/ [":dn"] ":" matchingrule ":=" value

present = attr "=*"

substring = attr "=" [initial] any [final]

initial = value

any = "*" *(value "*")

final = value

attr = AttributeDescription

matchingrule = MatchingRuleId

value = AttributeValue

Примеры поисковых фильтров:

(cn=Babs Jensen) (!(cn=Tim Howes)) (&(objectClass=Person)(|(sn=Jensen)(cn=Babs J*))) (o=univ*of*mich*)

Для поискового запроса необходимо указать не только фильтр, но и точку поиска (DN) в каталоге LDAP и область поиска (scope: sub, base, one).

Пример запроса для консольного клиента LDAP:

ldapsearch - h elib. sbras. ru - p 1389 - s sub - b dc=ru - x "cn=Федотов*" cn

Таким образом, для формирования поискового запроса в LDAP совсем не обязательно знать структуру каталога, достаточно знать базовый DN (корень) для поиска.

RPN - поисковые запросы Z39.50

В Z39.50 поисковые запросы можно формулировать не к реальной базе данных, а к абстрактной. Эта абстрактная база данных не имеет никакой структуры и характеризуется только поисковыми атрибутами. Поэтому и принято ее называть «Набор атрибутов» (attributeSet).

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

Наборы поисковых атрибутов составляют класс объектов Z39.50 {Z39.50 3}, подлежащих стандартизации. В классе {Z39.50 3} в настоящий момент стандартизованы следующие наборы атрибутов:

OID	Набор	Комментарий
{1.2.840.10003.3.1}	bib-1	Библиографическая информация
{1.2.840.10003.3.2}	exp-1	Explain
{1.2.840.10003.3.3}	ext-1	Расширенный сервис
{1.2.840.10003.3.4}	ccl-1	Type-2 (ISO 8777) и Type-100 (Z39.58) запросы
{1.2.840.10003.3.5}	gils	Для поиска GILS
{1.2.840.10003.3.6}	stas	Научно-техническая информация
{1.2.840.10003.3.7}	collections-1	Навигация по электронным коллекциям
{1.2.840.10003.3.8}	cimi-1	Информация по музейным коллекциям
{1.2.840.10003.3.9}	geo-1	Пространственные метаданные
{1.2.840.10003.3.10}	ZBIG	Биологическая информация
{1.2.840.10003.3.11}	util	Утилиты
{1.2.840.10003.3.12}	xd-1	Междоменный набор
{1.2.840.10003.3.13}	Zthes	Навигация по тезаурусам

Поисковые атрибуты

Набор bib-1 включает в себя шесть типов атрибутов с номерами 1-6. При построении запроса в комбинации с поисковым термом указание поисковых атрибутов определяет критерии отбора информации. В каждой группе конкретные атрибуты определяются числовым значением. Поэтому для указания поискового атрибута необходимо задание двух чисел: тип + значение. Здесь следует заметить, что, строго говоря, для однозначного задания атрибута необходимо указание еще и набора атрибутов, т. е. тройки OID + тип + значение. Как будет видно ниже, именно эта информация присутствует в запросе при ссылке на атрибут. Однако в этой секции OID будет опускаться, т. к. везде речь будет идти о bib-1.

Атрибуты 1: Use

Атрибуты этого типа указывают, с какой смысловой информацией связывается поисковый терм. В наборе атрибутов bib-1 определено 99 значений. Среди значений Use есть значения, соответствующие полям автор, заглавие, ключевые слова, год издания и т. д.:

4	Title	Название
21	Subject	Ключевое слово
31	Date-publication	Дата публикации
1003	Author	Автор

Среди атрибутов Use есть такие, которые связываются одновременно с несколькими полями:

1000	Author-name-and-title	Автор и название
1035	Anywhere	Все

Последнее значение связывается со всеми поисковыми полями.

Полный список атрибутов USE приведен в описании Z39.50 и дополнительных документах (http://www. loc. gov/z3950/agency/defns/oids. html).

Атрибуты 2: Relation

Атрибуты Relation указывают, как поисковый терм соотносится с выбираемыми данными из полей, определенных атрибутом Use, например

1	Less than	Меньше чем
3	Equal	Равно
6	Not equal	Не равно

Атрибуты 3: Position

Атрибуты Position указывают, в каком месте поля, определенного атрибутом Use, должен находится поисковый терм, например

1	First in field	Первый в поле
3	Any position in field	Любая позиция в поле

Полный список атрибутов Position приведен в описании Z39.50 и дополнительных документах (http://www. loc. gov/z3950/agency/defns/oids. html).

Атрибуты 4: Structure

Атрибуты Structure указывают, какую структуру имеет поисковый терм, например

1	Phrase	Набор слов, разделенных пробелом
2	Word	Слово
4	Year	Год как четыре цифры

Полный список атрибутов Structure приведен в описании Z39.50 и дополнительных документах (http://www. loc. gov/z3950/agency/defns/oids. html).

Атрибуты 5: Truncation

Атрибуты Truncation указывают, что представляет из себя поисковый терм, например

1	Right truncation	Усечение справа
100	Do not truncate	Не усекать
102	RegExpr-1	Регулярное выражение

Полный список атрибутов Truncation приведен в описании Z39.50 и дополнительных документах (http://www. loc. gov/z3950/agency/defns/oids. html).

Атрибуты 6: Completeness

Атрибуты Completeness указывают, что является обязательной областью совпадения при поиске, например

2	Complete subfield	Полное подполе
3	Complete field	Полное поле

Полный список атрибутов Completeness приведен в описании Z39.50 и дополнительных документах (http://www. loc. gov/z3950/agency/defns/oids. html).

Таким образом, для поиска записей, в которых встречается автор Иванов или Иванова, необходимо задать:

bib-1 1=1003 2=3 3=3 4=2 5=1 6=2 “Иванов”

Типы запросов в Z39.50

В Z39.50 предусмотрено несколько видов запросов:

-- Query Definitions

BEGIN

EXPORTS Query;

Query ::= CHOICE{

type-0 [0] ANY, -- Любой

type-1 [1] IMPLICIT RPNQuery, -- RPN

type-2 [2] OCTET STRING, -- CCL ISO 8777

type-100 [100] OCTET STRING, -- CCL Z39.58

type-101 [101] IMPLICIT RPNQuery, -- RPN

type-102 [102] OCTET STRING,

type-104 [104] IMPLICIT EXTERNAL} -- SQL

END

При этом запрос type-0 представляет собой любой запрос в синтаксисе СУБД, с которой связан сервер. Target должен передать запросы этого типа к database provider без изменения.

Запросы type-2 и type-100 представляют собой запросы в синтаксисе CCL. Они редко используются в Z39.50 и здесь обсуждаться не будут.

Интерес представляют запросы type-104 – SQL. Это новый тип запросов, который входит в стандарт Z39.50 c февраля 2000 года. Сегодня практически нет серверов, которые поддерживали бы запросы SQL в Z39.50. Тем не менее следует привести его определение:

--SQL Query Definition

SQLQuery ::= SEQUENCE {

abstractDatabaseFlag [0] BOOLEAN OPTIONAL,

queryExpression [1] IMPLICIT InternationalString }

-- as defined in the SQL Standard [ISO/IEC9075]

-- with/without Z39.50 schema abstraction extension as

-- specified by the flag

-- end SQL Query Definition

Как видно, SQL-запрос – простая текстовая строка. Однако строиться он может двумя способами: обычным (abstractDatabaseFlag = FALSE) и через абстрактную схему данных (abstractDatabaseFlag = TRUE).

Прямой вариант запроса (abstractDatabaseFlag = FALSE) - обычный запрос SQL в терминах реальных названий таблиц и полей, например

select title from collection where title like '%система%';

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

select title from Q1 where title like '%система%';

будет выполнен только на множестве Q1.

Абстрактный вариант запроса (abstractDatabaseFlag = TRUE) отличается от прямого тем, что в нем указываются не реальные названия таблиц и полей, а идентификаторы элементов абстрактной структуры записи. Например, при отображении таблиц предыдущего примера на схему GILS предыдущий запрос можно представить в виде

select [(2,1)] from [1.2.840.10003.13.2, 1.2.840.10003.3.5]
where [4] like '%система%';

где указаны OID схемы GILS [1.2.840.10003.13.2], OID набора поисковых атрибутов GILS [1.2.840.10003.3.5]}, выбираемый элемент title [(2,1)] и поисковый атрибут USE title [4]. В абстрактном запросе можно ссылаться на именнованные наборы элементов (ниже F - full), например

select *.F from [1.2.840.10003.13.2, 1.2.840.10003.3.5]

where [4] like '%stamp%';

и использовать именованные результирующие наборы.

Таким образом, абстрактный вариант запроса совмещает синтаксис SQL с абстрактным представлением данных Z39.50.

Если вернуться к типам запросов в Z39.50, то наибольший интерес представляют запросы type-1 и type-101 – запросы RPN (RPN – Reverse Polish Notation – обратная польская нотация). Для версии 3 протокола Z39.50 оба типа ничем не отличаются. Запросы type-1 (RPN) являются обязательными для всех серверов Z39.50. Поддержка других типов запросов сервером Z39.50 является факультативной.

Построение запросов RPN

Запрос RPN можно представить в виде дерева, в узлах которого находятся связывающие операторы (AND, OR, AND-NOT). Листьями этого дерева являются блоки «атрибуты+терм» (APT). На рисунке схематично изображен запрос RPN.

Дополнительно к сказанному на рисунке указан набор атрибутов, который используется по умолчанию.

В Z39.50 запрос RPN не является строкой символов, а является структурой, которую можно изобразить в виде строки, но только для наглядности.

В терминах ASN.1 запросы RPN

-- Definitions for RPN query

RPNQuery ::= SEQUENCE{

attributeSet AttributeSetId,

rpn RPNStructure}

RPNStructure ::= CHOICE{

op [0] Operand,

rpnRpnOp [1] IMPLICIT SEQUENCE{

rpn1 RPNStructure,

rpn2 RPNStructure,

op Operator }}

Operand ::= CHOICE{

attrTerm AttributesPlusTerm,

resultSet ResultSetId,

-- If version 2 is in force:

-- - If query type is 1, one of the above two must be chosen;

-- - resultAttr (below) may be used only if query type is 101.

resultAttr ResultSetPlusAttributes}

AttributesPlusTerm ::= [102] IMPLICIT SEQUENCE{

attributes AttributeList,

term Term}

ResultSetPlusAttributes ::= [214] IMPLICIT SEQUENCE{

resultSet ResultSetId,

attributes AttributeList}

AttributeList ::= [44] IMPLICIT SEQUENCE OF AttributeElement

Term ::= CHOICE{

general [45] IMPLICIT OCTET STRING,

-- values below may be used only if version 3 is in force

numeric [215] IMPLICIT INTEGER,

characterString [216] IMPLICIT InternationalString,

oid [217] IMPLICIT OBJECT IDENTIFIER,

dateTime [218] IMPLICIT GeneralizedTime,

external [219] IMPLICIT EXTERNAL,

integerAndUnit [220] IMPLICIT IntUnit,

null [221] IMPLICIT NULL}

Operator ::= [46] CHOICE{

and [0] IMPLICIT NULL,

or [1] IMPLICIT NULL,

and-not [2] IMPLICIT NULL,

-- If version 2 is in force:

-- - For query type 1, one of the above three

-- must be chosen;

-- - prox (below) may be used only if query type

-- is 101.

prox [3] IMPLICIT ProximityOperator}

AttributeElement ::= SEQUENCE{

attributeSet [1] IMPLICIT AttributeSetId OPTIONAL,

-- Must be omitted if version 2 is in force.

-- If included, overrides value of attributeSet

-- in RPNQuery above, but only for this attribute.

attributeType [120] IMPLICIT INTEGER,

attributeValue CHOICE{

numeric [121] IMPLICIT INTEGER,

-- If version 2 is in force,

-- Must select 'numeric' for attributeValue.

complex [224] IMPLICIT SEQUENCE{

list [1] IMPLICIT SEQUENCE OF StringOrNumeric,

semanticAction [2] IMPLICIT SEQUENCE OF INTEGER OPTIONAL}}}

ProximityOperator ::= SEQUENCE{

exclusion [1] IMPLICIT BOOLEAN OPTIONAL,

distance [2] IMPLICIT INTEGER,

ordered [3] IMPLICIT BOOLEAN,

relationType [4] IMPLICIT INTEGER{

lessThan (1),

lessThanOrEqual (2),

equal (3),

greaterThanOrEqual (4),

greaterThan (5),

notEqual (6)},

proximityUnitCode [5] CHOICE{

known [1] IMPLICIT KnownProximityUnit,

private [2] IMPLICIT INTEGER}}

KnownProximityUnit ::= INTEGER{

character (1),

word (2),

sentence (3),

paragraph (4),

section (5),

chapter (6),

document (7),

element (8),

subelement (9),

elementType (10),

byte (11) -- Version 3 only

}

-- End definitions for RPN Query.

Запросы PQF

Как уже отмечалось, запросы RPN представляются структурами ASN.1, однако для их задания в консольном клиенте и использования в SRW/SRU удобно их текстовое представление. Одним из вариантов текстового представления запросов RPN является представление PQF. В этом представлении строка запроса определяется как

simple ::= result-set | term.
result-set ::= '@set' string.
term ::= string.

proximity ::= exclusion distance ordered relation which-code unit-code.

exclusion ::= '1' | '0' | 'void'.

distance ::= integer.

ordered ::= '1' | '0'.

relation ::= integer.
which-code ::= 'known' | 'private' | integer.

unit-code ::= integer.

В качестве примера можно привести запрос RPN представлении PQF. Пусть требуется найти все записи, в которых автор начинается с «Ивано»:

@attrset bib-1 @attr 1=1003 @attr 2=3 @attr 3=3 @attr 5=1 {Ивано}

или

@attr bib-1 1=1003 @attr 2=3 @attr 3=3 @attr 5=1 {Ивано}

где по Bib-1 @attr 1=1003 - соответсвует author, @attr 2=3 – равно, @attr 3=3 – любая позиция в поле, @attr 5=1 – усечение справа, Ивано – поисковый термин.

Что является результатом поиска

В результате выполнения поиска в базах данных origin может получить от target следующую информацию в APDU searchResponse:

Сообщение об ошибке Количество найденных записей Сами найденные записи

Первый вариант ответа связан с какой-либо ошибкой, которая диагностируется, например, по bib-1. Например, можно получить сообщение

Access to specified database denied (Доступ к указанной базе запрещен).

Второй и третий варианты соответствуют успешному проведению поиска. Какой из них будет получен origin, зависит от параметров, которые передаются target вместе с поисковым запросом в APDU searchRequest.

Для этого вводятся понятия малый набор, средний набор и большой набор. Здесь под набором понимается пронумерованная сквозным образом совокупность найденных записей. Все записи из малого набора возвращаются всегда в APDU searchResponse, все записи из большого набора не возвращаются никогда, а из среднего набора возвращаются некоторые записи. Далее задаются параметры:

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

Нетрудно догадаться, что, меняя эти три параметра, можно добиться возвращения любого количества записей, в том числе и ни одной.

Коль скоро записи, найденные при поиске, могут быть возвращены origin сразу, необходимо указать в APDU searchRequest параметры, связанные с представлением этих записей. Эти параметры указываются в полях: smallSetElementSetNames, mediumSetElementSetNames, preferredRecordSyntax, но их смысл станет ясным после прочтения следующего раздела.

Наконец, следует отметить, что все найденные при поиске записи target должен сохранить в сессионном блоке для последующего использования. Если target допускает опцию NamedResultSet, этой сохраненной совокупности может быть присвоено имя, если - нет, совокупность сохраняется неименованной и переписывается при последующем поиске. Имя сохраняемой совокупности записей, или результирующего набора, передается в APDU searchRequest в поле resultSetName. Если результирующий набор с указанным именем уже существует, то, если поле replaceIndicator содержит TRUE, он переписывается, или, если поле replaceIndicator содержит FALSE, возвращается ошибка с номером 21 по bib-1 (см. документацию).

Именованные результирующие наборы, которые сохраняются на target, можно использовать в последующих RPN-запросах, где они выступают такими же операндами, как блоки APT (см. предыдущую секцию).

APDU searchRequest и searchResponse

Таким образом, для выполнения поиска origin посылает target APDU searchRequest и получает в ответ APDU searchResponse. Ниже приведены ASN.1 определения этих APDU с учетом определений, сделанных выше (Query, OtherInformation), и с учетом определений, которые будут сделаны в следующих разделах (Records, ElementSetNames, PresentStatus).

BEGIN

EXPORTS SearchRequest, SearchResponse;

IMPORTS Query, OtherInformation, Records, ElementSetNames,

PresentStatus, InternationalString;

SearchRequest ::= SEQUENCE{

referenceId ReferenceId OPTIONAL,

smallSetUpperBound [13] IMPLICIT INTEGER,

largeSetLowerBound [14] IMPLICIT INTEGER,

mediumSetPresentNumber [15] IMPLICIT INTEGER,

replaceIndicator [16] IMPLICIT BOOLEAN,

resultSetName [17] IMPLICIT InternationalString,

databaseNames [18] IMPLICIT SEQUENCE OF DatabaseName,

smallSetElementSetNames [100] ElementSetNames OPTIONAL,

mediumSetElementSetNames [101] ElementSetNames OPTIONAL,

preferredRecordSyntax [104] IMPLICIT OBJECT IDENTIFIER OPTIONAL,

query [21] Query,

-- Following two parameters may be used only if version 3 is in force.

additionalSearchInfo [203] IMPLICIT OtherInformation OPTIONAL,

otherInfo OtherInformation OPTIONAL}

ReferenceId ::= [2] IMPLICIT OCTET STRING

DatabaseName ::= [105] IMPLICIT InternationalString

SearchResponse ::= SEQUENCE{

referenceId ReferenceId OPTIONAL,

resultCount [23] IMPLICIT INTEGER,

numberOfRecordsReturned [24] IMPLICIT INTEGER,

nextResultSetPosition [25] IMPLICIT INTEGER,

searchStatus [22] IMPLICIT BOOLEAN,

resultSetStatus [26] IMPLICIT INTEGER{

subset (1),

interim (2),

none (3)} OPTIONAL,

presentStatus PresentStatus OPTIONAL,

records Records OPTIONAL,