2. Условия поиска
 

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

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

Поиск по совпадению. Задан некоторый ключ, требуется выделить один или все элементы (записи), признаки которых совпадают с заданным ключом. Иначе говоря, необходимо найти все записи, для которых p_i = q, где р_i — ключ i-й записи, a q — значение поискового признака (заданного ключа, или ключа поиска).

Поиск по интервалу. В условии поиска задан некоторый числовой интервал а < - q ≤ b, требуется выделить одну или все записи, значения признаков которых заключены между границами интервала. Например, найти всех студентов, имеющих оценки 3, 4 и 5 по некоторому предмету: 3 ≤ q ≤5.

Поиск по близости. Найти такую запись, для которой abs(p_i -q) минимально среди всех записей, т.е. запись с ближайшим к q значением p_i. Сюда же относится поиск записи с максимальным или минимальным значением ключа.

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

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

Поиск по нескольким условиям. Используется некоторое логическое выражение над несколькими логическими значениями, например, найти всех абитуриентов, проживающих в Москве и имеющих средний балл не менее 4.3, или найти всех служащих имеющих специальность «механик» и возраст более 45 лет.

Все рассмотренные выше условия поиска, кроме условия по¬иска по близости, связаны с проверкой некоторых внутренних характеристик каждого отдельного эле-мента, т.е. выполнение или невыполнение условия поиска может быть проверено в каждом элементе в отдельности и не зависит от наличия других элемен¬тов. Выпол-нение условия поиска по близости не может быть про¬верено в отдельном элементе без учета других объектов, т.е. здесь учитываются некоторые отношения между элементами.

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

Фактографические данные об объекте (элементе множества) включают: объект (фамилия сотрудника, код изделия, название отдела и т.п.); значения признаков (свойств, характеристик) объекта (Иванов, 8к88, бухгалтерия).

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

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

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

Мы ограничиваемся рассмотрением таблиц, хранящих фактографические данные.