Корректировка данных.

Поиск.

Сжатие.

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

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

Пример.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

ключ	ссылка

ключ	ссылка

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

При корректировке выполняются следующие действия:

- поиск корректируемой записи по ключам и/или места в массиве;

- изменение полей записи;

- удаление записи;

- включение записи.

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

В массиве корректур обычно различают 3 типа записей:

1-й тип - “включение”, содержит целиком новую запись, признак “включения”, например, "1";

2-й тип - “удаление”, содержит “ключ” и признак удаления, например, "2";

3-й тип - “замена”, содержит значения заменяемых полей и признак замены, например, "3".

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

Корректировка последовательного файла.

Недостатки последовательного файла:

- большие затраты на корректировку, связанные с перезаписыванием основного файла (большое время обработки);

- последовательные файлы не используются в он-лайновых системах.

Основной файл и файл корректур отсортированы по ключу (см. схему).

Корректировка в индексно-последовательных и прямых файлах.

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

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

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

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

При этом участок свободной памяти содержит, как правило, в начале длину участка свободной памяти и ссылку (адрес) на следующий участок свободной памяти:

Типичная структура индексно-последовательного файла:

индекс основная память

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

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

Как часто нужно проводить реорганизацию - это зависит от активности внесения информации (корректировки) и активности использования информации.

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

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