Выборка информации.
Выборка информации - это процесс обработки массива информации (файла, набора данных), с помощью которого создается новый массив информации по заданным критериям отбора данных и со структурой данных, являющейся подмножеством данных исходного массива.
Пример.
Пусть есть список студентов некоторого факультета. Запись имеет вид:
Фамилия, и.о. |
Группа |
Пол |
Дата рождения |
Служба в ВС |
Задача: Выбрать всех призывников и сформировать файл.
Определим условие выборки:
(пол=“М”).”И”.((16=<(Текущая дата - Дата рождения).”И”.(Текущая дата - Дата рождения)<28) *
.“И”.”НЕ”(Служба в ВС))
Структура записи результирующего файла:
Фамилия, и.о. |
Группа |
Дата рождения |
Графическое изображение
выборки:
Исходный файл
Файл выборки
Документ
Число выбранных записей может быть от 0 до n, где - n число записей в исходном массиве.
Критерии отбора - это логические условия, которым должны удовлетворять заданные поля исходного массива. Элементами логических условий являются поля, отношения между ними и заданными значениями полей, логические связки - и, или, нет.
Слияние (объединение).
Слияние - процесс обработки двух или более массивов информации, в результате которого получается массив, представляющий собой подмножество данных исходных массивов, записи в котором сформированы по заданным критериям объединения данных.
При слиянии массивов информации часть данных может не найти заданного соответствия и не попадает в результирующий массив. Такие данные называются нестыковкой.
Как правило, слияние (объединение) происходит по совпадению ключевых полей. Для удобства выполнения слияния массивы предварительно сортируют по ключевым полям.
Графическое изображение слияния:
Файл 1 Файл 2
Исходные
файлы
Протокол
“Нестыковки”
слияния Файл
3,
результирующий
Пример.
Пусть есть два файла, отсортированных по ключу, со структурами записей:
1)
Табельный номер |
Фамилия, и.о. |
2)
Табельный номер |
Сумма |
Нужно получить файл с фамилией, табельным номером и суммой.
3)
Фамилия, и.о. |
Табельный номер |
Сумма |
В результате выполнения процедуры слияния двух файлов получим результирующий файл.
Сжатие.
Сжатие - это процесс обработки упорядоченного по заданным ключам массива информации, с помощью которого все записи с одинаковыми ключами преобразуются в одну запись.
Графическое изображение процедуры
сжатия:
Исходный файл
(отсортирован по ключу)
Файл после сжатия
Документ
Пример.
Пусть имеется некоторый файл, содержащий наряды с выполненными работами. В наряде указаны номер наряда, табельный номер работника, сумма заработка по тарифу. Необходимо распечатать документ, в котором по каждому табельному указана общая сумма заработка.
Входной файл, неупорядочен по табельному номеру, структура записи:
Номер наряда |
Табельный |
Сумма по наряду |
Упорядоченный по табельному номеру (неуникальный ключ) файл со структурой:
Номер наряда |
Табельный |
Сумма по наряду |
Сжатый файл, упорядочен по табельному номеру, ключ уникальный (табельный номер), структура записи:
Табельный |
Сумма итоговая по всем нарядам |
Поиск.
Поиск - это процедура извлечения (выделения) из некоторого множества записей такого подмножества, записи которого удовлетворяют заранее заданному условию. Условия поиска называют запросом на поиск, поисковым признаком.
Ключи поиска - это поля записи, которые используются для проверки на соответствие условиям поиска.
Виды условий поиска:
1) по совпадению (ключ = q, где q конкретное значение),
2) по интервалу (а =< ключевое поле р =< в),
3) по близости (|р-q| - минимум, где р-поле, q-значение),
4) по арифметическому условию (например, р1-р2=q и т.п.),
5) по текстовому значению,
6) по совокупности условий.
Поиск по своему содержанию близок процедуре выборки.
Поиск - одна из основных процедур обработки данных, так как удовлетворяет информационные потребности пользователя. Особое значение поиск приобретает в современных условиях при наличии средств телеобработки, телекоммуникаций.
Одним из простых, но эффективных способов поиска является метод дихотомии. Метод дихотомии - это способ поиска данных путем последовательного деления интервала записей упорядоченного массива пополам и выполнения операций сравнения.
Важным критерием в оценке процедуры поиска является время ее выполнения. Как правило, время зависит от числа сравнений по поисковым полям для получения искомой информации. Принимают во внимание как среднее число сравнений Сср, так и Сmax - максимальное число сравнений.
Приведем некоторые оценки поиска для файла из М записей.
Упорядоченность файла |
Метод поиска |
Число сравнений Сср среднее |
Сmax максимальное |
Неупорядоченный |
Поиск перебором |
М |
М |
Упорядоченный |
Поиск перебором |
(М+1)/2 |
М |
Упорядоченный |
Метод дихотомии |
|
|
Последовательность поиска в индексно - последовательном файле:
Главный
индекс
Текущий индекс
Файл данных
Принцип использования рубрикаторов.
В некоторых системах и банках данных используется поиск информации по рубрикаторам. Обычно, имеется один рубрикатор старшего (или первого) уровня, несколько рубрикаторов второго уровня и т.д.
Рубрикатор Рубрикаторы Рубрикаторы
ключевые слова
ссылки на рубрикатор
нижнего уровня
ключ
ссылка
Данные или
рубрикатор следующего
уровня
ключ
ссылка
Данные
Данные