Корректировка данных.
Поиск.
Сжатие.
Сжатие - это процесс обработки упорядоченного по заданным ключам массива информации, с помощью которого все записи с одинаковыми ключами преобразуются в одну запись.
Пример.
Пусть имеется некоторый файл, содержащий наряды с выполненными работами. В наряде указаны номер наряда, табельный номер работника, сумма заработка по тарифу. Необходимо распечатать документ, в котором по каждому табельному указана общая сумма заработка.
Входной файл, неупорядочен по табельному номеру, структура записи:
Номер наряда | Табельный | Сумма по наряду |
Упорядоченный по табельному номеру (неуникальный ключ) файл со структурой:
Номер наряда | Табельный | Сумма по наряду |
Сжатый файл, упорядочен по табельному номеру, ключ уникальный (табельный номер), структура записи:
Табельный | Сумма итоговая по всем нарядам |
Поиск - это процедура извлечения (выделения) из некоторого множества записей такого подмножества, записи которого удовлетворяют заранее заданному условию. Условия поиска называют запросом на поиск, поисковым признаком.
Ключи поиска - это поля записи, которые используются для проверки на соответствие условиям поиска.
Виды условий поиска:
1) по совпадению (ключ = q, где q конкретное значение),
2) по интервалу (а =< ключевое поле р =< в),
3) по близости (|р-q| - минимум, где р-поле, q-значение),
4) по арифметическому условию (например, р1-р2=q и т.п.),
5) по текстовому значению,
6) по совокупности условий.
Поиск по своему содержанию близок процедуре выборки.
Поиск - одна из основных процедур обработки данных, так как удовлетворяет информационные потребности пользователя. Особое значение поиск приобретает в современных условиях при наличии средств телеобработки, телекоммуникаций.
Одним из простых, но эффективных способов поиска является метод дихотомии. Метод дихотомии - это способ поиска данных путем последовательного деления интервала записей упорядоченного массива пополам и выполнения операций сравнения.
Важным критерием в оценке процедуры поиска является время ее выполнения. Как правило, время зависит от числа сравнений по поисковым полям для получения искомой информации. Принимают во внимание как среднее число сравнений Сср, так и Сmax - максимальное число сравнений.
Приведем некоторые оценки поиска для файла из М записей.
Упорядоченность файла | Метод поиска | Число сравнений Сср среднее | Сmax максимальное |
Неупорядоченный | Поиск перебором | М | М |
Упорядоченный | Поиск перебором | (М+1)/2 | М |
Упорядоченный | Метод дихотомии | ![]() | ![]() |
Последовательность поиска в индексно - последовательном файле:
![]() |
Принцип использования рубрикаторов.
В некоторых системах и банках данных используется поиск информации по рубрикаторам. Обычно, имеется один рубрикатор старшего (или первого) уровня, несколько рубрикаторов второго уровня и т.д.
Рубрикатор Рубрикаторы Рубрикаторы
старшего уровня нижнего уровня или данные
Корректировка - это процесс обработки массива информации (файла, набора данных, базы) путем внесения в него изменений с целью обеспечения достоверности и актуальности данных. Корректировка - достаточно сложная процедура.
При корректировке выполняются следующие действия:
- поиск корректируемой записи по ключам и/или места в массиве;
- изменение полей записи;
- удаление записи;
- включение записи.
В процессе корректировки участвуют четыре информационных объекта - исходный (основной) массив, в который вносятся изменения, массив корректур (изменений), результирующий (откорректированный исходный) массив и протокол корректировки. Протокол корректировки - это документ, в котором содержится информация о результатах корректировки, обнаруженных ошибках и нестыковках, используемый для анализа и принятия решения по завершению операции корректировки.
В массиве корректур обычно различают 3 типа записей:
1-й тип - “включение”, содержит целиком новую запись, признак “включения”, например, "1";
2-й тип - “удаление”, содержит “ключ” и признак удаления, например, "2";
3-й тип - “замена”, содержит значения заменяемых полей и признак замены, например, "3".
Приведем простой пример корректировки массива информации. Пусть есть массив, состоящий из записей с двумя полями - табельным номером и фамилией, и.о. В него вносится корректура.
Корректировка последовательного файла.
Недостатки последовательного файла:
- большие затраты на корректировку, связанные с перезаписыванием основного файла (большое время обработки);
- последовательные файлы не используются в он-лайновых системах.
Основной файл и файл корректур отсортированы по ключу (см. схему).
Корректировка в индексно-последовательных и прямых файлах.
Корректировка в индексно-последовательных файлах, файлах прямого доступа, базах данных несколько сложнее.
Для осуществления вставок, включения новых записей или данных используются так называемые “области переполнения”. Области переполнения создаются как в основной области, так и в индексных областях.
При вставке данных они могут попасть в область переполнения, при этом делаются ссылки на добавленную информацию, появляются цепочки данных. При удалении данных, как правило, делаются отметки об удалении в специальном символе (логическое удаление), а физически сама информация не удаляется. При замене данных происходит перезапись физического блока на машинном носителе.
При применении методов прямого доступа, областей переполнения в ряде случаев механизм работы с памятью повторно использует освобожденную память. Для облегчения использования свободных областей они связываются в цепочки. Например, блок памяти будет содержать участки данных вперемешку со свободной памятью:
данные | свободная память | данные | своб.память | данные | . . . | данные | св.память | данные |
При этом участок свободной памяти содержит, как правило, в начале длину участка свободной памяти и ссылку (адрес) на следующий участок свободной памяти:
L длина участка | А ссылка на следующий участок | свободная память |
Участок свободной памяти |
Типичная структура индексно-последовательного файла:
![]() |
индекс основная память
В результате корректировки происходит изменение физического расположения файла, меняется соответствие между физическим расположением записей и их логической последовательностью (упорядоченностью). Кроме того, могут оказаться заполненными области переполнения файла, что делает невозможным дальнейшее добавление данных даже при наличии свободных участков в основной области файла на машинном носителе.
Для приведения физической и логической организации файла к некоторому исходному состоянию применяются специальные процедуры, которые позволяют перенести данные из области переполнения в основную и подготовить ее для дальнейшего использования, физически удалить логически удаленные записи и т.д. Такие процедуры называют реорганизацией. Для индексно-последовательных файлов реорганизацию подразделяют на процедуру разгрузки (выгрузки) и процедуру загрузки индексно-последовательного файла.
Как часто нужно проводить реорганизацию - это зависит от активности внесения информации (корректировки) и активности использования информации.
В онлайновых системах реорганизация баз данных, файлов проводится в то время, когда абоненты онлайновой системы не работают с ней. Это обычно ночное время или выходные дни. Особая проблема, очень трудная и острая, если базы данных используются круглосуточно. В этом случае необходимо найти такие средства и способы реорганизации баз данных, при которых бы процесс работы с базой данных не прерывался.
При всех видах корректировки необходимо иметь протоколы выполнения корректировки, а в режиме он-лайн сохранять сведения о корректировке в отдельном файле (базе) или включать сведения о корректировке в саму базу данных (файл).