СУБД LeoBase: поиск и проекция

(Продолжение. Начало в №7-9, 11, 12, 13, 14, 15, 16, 17)

Тема сегодняшнего разговора -операции выборки и воплощение их в прикладных проектах. Краткий обзор операций выборки уже давался в статье, где на примере ИПС "ЮрИнформ" мы рассказывали об их конкретном применении. Сегодня рассмотрим эти функции более детально, сравнив их со стандартными средствами поиска реляционных СУБД.

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

Основным элементом запроса на поиск является терм - минимальная единица поискового выражения, состоящая из аргументов, знаков отношения, ключевого поля и необязательного пути, по которому нужно пройти от активной БД, чтобы попасть в базу, где находится ключевое поле. Термы бывают двух видов:

1) терм отношения, в котором присутствует один аргумент и знак отношения (один из <, >, =, <=, >=);

 

2) терм диапазона - терм, имеющий два аргумента, задающих границы диапазона.

Аргумент строкового типа в терме может содержать шаблон (например, "АВ"* говорит, что условию должны удовлетворять все строки, начинающиеся с "АВ"). К любому виду терма может быть применена операция отрицания, изменяющая его значение на противоположное. Строка поиска в LeoBase представляет собой логическую комбинацию термов, которые могут быть объединены булевыми операциями с разными уровнями вложенности скобок.

В LeoBase имеется возможность проведения поиска по вычислимым полям, (например, если в строке поиска возникает необходимость использовать отношения ключей между собой). Допустим, в БД "Студенты" имеется два ключевых поля "Количество экзаменов" и "Общая сумма баллов" и необходимо найти студентов, средняя успеваемость которых в период сессии ("Общая сумма баллов/Количество экзаменов") превысила 4,5 балла. Задачу эту можно решать тремя способами:

1) простым перебором всей базы и определением необходимого множества записей;

2) вводом в структуру дополнительного ключевого поля, куда при добавлении записи вводится коэффициент "общая сумма баллов/количество экзаменов";

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

Самым оптимальным вариантом, разумеется, является третий, который поддерживается LeoBase в полном объеме.

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

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

· БД"Студенты" содержит фамилии студентов, указание на кафедру, где учится каждый студент, а также его место жительства;

· БД"Преподаватели" - фамилии преподавателей и указание на кафедру, где работает;

· БД"Кафедры" - список всех кафедр института;

· БД"Курсовые проекты" - информацию о названии проекта, оценке за его выполнение, а также в виде ссылок информацию о студенте и преподавателе, участвующем в этом проекте;

· S1-S4 - имена реляционных ссылок.

Простейший поиск в LeoBase осуществляется по ключевому полю одной БД. Скажем, зная, что база данных "Курсовые проекты" содержит поле "Отметка", то получить список проектов, выполненных на "отлично", при условии, что эта БД активна, не представляет никакого труда. Достаточно лишь, при активной БД "Курсовые проекты", задать условие поиска, при котором ключевое поле ("оценка") равно "5". Простой поиск по индексу в этой БД (проходящий в LeoBase без перебора) даст необходимый результат. Перед ключевым полем в запросе может стоять модификатор not, что позволяет найти все записи, не соответствующие указанному в запросе содержимому ключевого поля.

Более сложным видом поиска является тот, в котором используются поля из разных таблиц. Тот же запрос, выполненный при активной БД "Студенты", даст нам список студентов - отличников. (Из этого примера видно, что поиск всегда идет в терминах активной БД, которая остается активной и по его завершении). В данном случае между этими двумя БД существует единственный путь (реляционная ссылка S1), указывать который при запросе явно, разумеется, нет смысла. В рассмотренном примере при выполнении поиска уже используется операция проекции, хоть и без явного задания ее в запросе.

В случае, когда необходимо, например, получить список факультетов, к которым относятся кафедры, основанные в 1995 году, прямое указание на проведение проекции в запросе будет оптимальным решением. И здесь проекция выигрывает по сравнению с обычными методами поиска. В обычной реляционной СУБД этот процесс происходит примерно так: задавая в качестве объекта поиска ID (индекс) требуемой записи из другой таблицы, СУБД осуществляет поиск, последовательно перебирая записи в ней. И хотя для ускорения этого перебора в различных системах реализованы специальные алгоритмы, все же сам принцип не позволяет достигнуть качественного скачка в скорости. При использовании же проекции, благодаря примененному при реализации ее механизма ноу-хау, позволяющему обойтись без перебора, выборка происходит очень быстро.

Итак, для получения желаемого списка, необходимо, сначала проведя простой поиск, выделить искомые кафедры, а затем провести проекцию множества выделенных записей на БД "Факультеты". Как и в случае с заданием запроса на поиск, путь, по которому проходит проекция, следует задавать, только если этот путь неоднозначен.

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

Допустим, выделена одна запись - "Михайлов". После проведения проекции на БД "Кафедры", выделенной окажется запись "РЭ". После проведения проекции обратно на БД "Студенты", выделенными окажутся уже три записи: "Михайлов", "Иванов" и "Кузин". Эту особенность, при желании, можно использовать при реализации какой-либо поисковой функции.

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

Покажем пример сложного запроса. Пусть необходимо получить список курсовых проектов, в подготовке которых участвовали одновременно студенты и преподаватели кафедры ЭВМ. Осуществляется этот запрос одной строкой:

("\S1;S2\Кафедра=ЭВМ") AND ("\S2;S4\Кафедра=ЭВМ").

При его осуществлении СУБД проведет следующие операции:

1) выполнение запроса к БД "Кафедры" через БД "Студенты" (проекция из "Кафедры" на "Студенты");

2) выполнение запроса к БД "Кафедры" через БД "Преподаватели" (проекция из "Кафедры" на "Преподаватели");

3) проведение логической операции AND над результатами шагов 1 и 2.

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

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

БД «Студенты» БД «Курсовой проект» БД «Кафедра»
Фамилия Город Отметка  
Михайлов Минск 4 РЭ
Иванов Слуцк 5 РЭ
Митин Минск 5 ЭВМ
Мошкин Минск 3 ЭВМ
Кузин Жлобин 3 РЭ

Имея в виду, что активна БД "Кафедры", формируется следующий запрос:

((\S3;\ Студенты.Город=Минск) AND (\S3;S1\ Курсовой проект=5)).

Верно построенный, на первый взгляд, запрос, тем не менее, не даст правильного ответа. Хотя обе его половины в принципе верны, запрос, построенный таким образом, не отражает существа проблемы. Покажем действия СУБД по его выполнению (через тире указан результат операции):

1. Выполнение запроса "На каких кафедрах учатся минчане?" - РЭ, ЭВМ.

2. Выполнение запроса "На каких есть отличники?" - РЭ, ЭВМ.

3. Операция логического пересечения (AND) - РЭ, ЭВМ.

Ответ неверен. Ведь как видно из таблицы, единственная кафедра, удовлетворяющая обоим условиям - кафедра ЭВМ.

К счастью, задача легко разрешима: для этого при построении запроса необходимо лишь придерживаться определенных правил. Одно из них - в подобных случаях результаты поиска по различным БД, содержащим ключи, следует свести в базу-"перекресток" (базу, где пересекаются пути из этих БД), а затем провести проекцию на БД, в которой получается итоговый результат. Вот как правильно строится запрос в нашем случае:

((Студенты.Город=Минск) AND (\S1;\Курсовой проект=5)).

По его результатам проводим проекцию на БД "Кафедры" и получаем правильный ответ. Действия СУБД при этом:

1. Выделение всех минчан - Михайлов, Митин, Мошкин.

2. Выделение всех отличников - Иванов, Митин.

3. Операция пересечения (AND) - Митин.

4. Узнаем кафедру - ЭВМ.

Язык выполнения запросов - LeoBase Query Language, разрабатываемый в настоящее время, позволит непосредственно в строке поиска указывать, какая база является активной для какой части запроса, на какую базу делать проекцию и когда проводить операции объединения, пересечения и т.д. С помощью этого языка сложные запросы можно будет реализовывать значительно быстрее.

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

(Продолжение следует)

Владимир КОТЛЯРОВ,
"СофтИнформ", тел. 213-28-13,
e-mail:
ui@activ.minsk.by

Версия для печатиВерсия для печати

Номер: 

18 за 1997 год

Рубрика: 

Базы данных
Заметили ошибку? Выделите ее мышкой и нажмите Ctrl+Enter!