Слияние (объединение).

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

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

Как правило, слияние (объединение) происходит по совпадению ключевых полей. Для удобства выполнения слияния массивы предварительно сортируют по ключевым полям.

Графическое изображение слияния: Файл 1 Файл 2   Исходные файлы   Протокол “Нестыковки” слияния Файл 3, результирующий

Пример.

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

1)

2)

Нужно получить файл с фамилией, табельным номером и суммой.

3)

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

Сжатие.

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

Графическое изображение процедуры сжатия:     Исходный файл (отсортирован по ключу)     Файл после сжатия Документ

Пример.

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

Входной файл, неупорядочен по табельному номеру, структура записи:

Сортируем этот файл по полю «табельный номер». Получим упорядоченный по табельному номеру (неуникальный ключ) файл со структурой:

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

Поиск.

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

Ключи поиска - это поля записи, которые используются для проверки на соответствие условиям поиска.

Виды условий поиска:

1) по совпадению (ключ = q, где q конкретное значение),

2) по интервалу (а =< ключевое поле р =< в),

3) по близости (|р-q| - минимум, где р-поле, q-значение),

4) по арифметическому условию (например, р1-р2=q и т.п.),

5) по текстовому значению,

6) по совокупности условий.

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

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

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

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

Приведем некоторые оценки поиска для файла из М записей.

Упорядоченность файла	Метод поиска	Число сравнений Сср среднее	Сmax максимальное
Неупорядоченный	Поиск перебором	М	М
Упорядоченный	Поиск перебором	(М+1)/2	М
Упорядоченный	Метод дихотомии

Последовательность поиска в индексно - последовательном файле:

Принцип использования рубрикаторов.

В некоторых системах и банках данных используется поиск информации по рубрикаторам. Обычно, имеется один рубрикатор старшего (или первого) уровня, несколько рубрикаторов второго уровня и т.д.

Рубрикатор Рубрикаторы Рубрикаторы

старшего уровня нижнего уровня или данные

ключ	ссылка

ключ	ссылка