Содержание к диссертации
Введение
1. АСУП. Учетная подсистема 19
1.1. Назначение и структура 19
1.2. Первичная информация и требования к ее подготовке 23
1.3. Система исходной информации 28
1.4. Формирование записей 33
1.4.1. Лесопильное производство 33
1.4.2. Фанерное производство 39
1.4.3. Производство древесных плит 41
1.4.4. Мебельное производство 43
1.4.5. Вспомогательные подразделения 45
1.5. Выводы 46
2. Структуры данных в файлах с различной организацией 50
2.1. Организация файлов 50
2.1.1. Неупорядоченные последовательные файлы 50
2.1.2. Упорядоченные последовательные файлы 51
2.1.3. Хешированные файлы 55
2.2. Методы доступа 61
2.2.1. Связанные списки 61
2.2.2. Индексирование 63
2.2.2.1. Индексно-последовательные файлы 65
2.2.2.2. Многоуровневые индексы 68
2.2.2.3. Вторичные индексы 69
2.2.3. В+-деревья 72
2.3. Выводы 76
3. Усовершенствованный метод комбинированных индексов 78
3.1. Описание 78
3.2. Примеры поиска записей 84
3.2.1. Поиск записей в отношении R, где поле а принимает значение Al, поле - значение , поле с - значение с2 84
3.2.2. Поиск записей в отношении R, где поле с принимает значение с2 .86
3.3. Характеристики усовершенствованного метода 90
3.4. Выводы 91
4. Практическая реализация усовершенствованного метода комбинированных индексов 93
4.1. Описание разработанного ПО 93
4.2. Алгоритм построения индекса 96
4.3. Алгоритм выборки записей с использованием стандартного метода индексирования 99
4.4. Алгоритм подсчета количества записей с использованием стандартного метода индексирования 101
4.5. Алгоритм выборки записей с использованием усовершенствованного метода комбинированных индексов 102
4.6. Алгоритм подсчета количества записей с использованием усовершенствованного метода комбинированных индексов 104
4.7. Анализ эффективности применения усовершенствованного метода комбинированных индексов 106
4.7.1. Эксперимент 1 106
4.7.2. Эксперимент 2 113
4.8. Выводы 121
Заключение 127
Библиографический список использованной литературы. 131
- Первичная информация и требования к ее подготовке
- Упорядоченные последовательные файлы
- Поиск записей в отношении R, где поле с принимает значение с2
- Алгоритм выборки записей с использованием усовершенствованного метода комбинированных индексов
Введение к работе
Актуальность исследования. В последнее десятилетие XX века и в настоящее время Россия и ее хозяйственно-политическая система переживает сложный и болезненный процесс трансформации всех основных составляющих сфер жизнедеятельности страны в направлении создания общецивилизованных форм национальной экономики и политико-институциональных основ общества. Переход страны к рыночной постиндустриальной экономике предполагает расширение и повышение эффективности производства. Одной из важнейших составляющих в решении этой задачи является внедрение и использование достижений современных информационных технологий в автоматизации управления производством и его технологическими процессами.
Основу любой автоматизированной системы управления производством (АСУП) составляют ее информационные модели и средства их обработки, представленные в совокупности баз данных (БД).
Истоки технологий баз данных относятся к началу 60-х гг., когда уже был накоплен некоторый опыт решения задач обработки экономической информации средствами технологий файловых систем и языка COBOL. Это были технологии, основанные на использовании магнитных лент с их последовательным доступом. Появление таких устройств памяти прямого доступа, как магнитные диски вычислительных систем IBM/360 или ICL-1900, открыло принципиально новые возможности и стимулировало поиски новых эффективных методов организации хранения во внешней памяти интегрированных совокупностей сложноструктурированных данных большого объема. Необходимость в них была продиктована потребностями многих разнообразных приложений.
Актуальность и новизна проблем, связанных с этой сферой, привлекла к ним внимание широкого круга ученых (Э. Кодд, К. Дейт, Ч. Бахман, М. Стоун-брекер и др.) и специалистов в американских компаниях, занятых производством вычислительной техники и программного обеспечения, а также в крупных индустриальных компаниях, испытывающих наиболее острые потребности в
5 новом инструментарии и ранее других осознавших его эффективность. Заметим, что в рассматриваемый период еще не существовало специализированной индустрии коммерческого программного обеспечения, и производители вычислительной техники самостоятельно выпускали все необходимое системное программное обеспечение, а также многие прикладные программы для поставляемых ими аппаратных платформ. Весь комплекс созданного программного обеспечения поставлялся вместе с оборудованием вычислительной машины как единый продукт. Основная же доля прикладного программного обеспечения создавалась его будущими пользователями - крупными индустриальными компаниями, научными центрами, университетами.
В результате активной деятельности ряда крупных компаний США, большинство из которых выполняло военные заказы, стали появляться первые приложения, использующие принципы баз данных. В июне 1963 г. в городе Санта-Моника (США) компанией System Development Corporation (SDC) был организован, первый симпозиум, посвященный проблематике баз данных [1]. На симпозиуме обсуждался ряд докладов по использованию баз данных в военных приложениях, были представлены программные системы, которые можно квалифицировать как прообраз СУБД.
В начале 60-х гг. были созданы первые системы управления базами данных. Среди них СУБД общего назначения IDS (Integrated Data Storage, 1963 г.), разработанная в компании General Electric под руководством Чарльза Бахмана. Эта система интересна не только тем, что она была одной из первых коммерческих СУБД. Реализованные в ней принципы организации базы данных и манипулирования данными стали впоследствии основой сетевой модели данных CODASYL [2].
В период 60-х гг. начинают также формироваться основы методологии построения систем баз данных, которая вскоре стала играть основополагающую роль в разработке АСУП и АСУТП как в нашей стране, так и за рубежом. Одним из ключевых элементов этой методологии является концепция модели дан-
ных. Термин "модель данных" вошел в лексикон специалистов в области баз данных несколько позднее - в 70-е гг., после публикации фундаментальной работы Эдгара Кодда о реляционной модели данных [3]. Именно во второй половине 60-х гг. стали конструироваться первые модели данных, которые были реализованы в целом ряде коммерческих СУБД. Наиболее значимыми разработками в этом направлении стали сетевая модель данных CODASYL и иерархическая модель данных компании IBM. В нашей стране вопросами АСУП и моделей данных занимались такие ученые как А.И. Берг, Н.П. Федоренко, В.М. Глушков, Ю.И. Черняк, В.М. Жеребин, М.Ш. Цаленко, В.Г. Хорошевский, Е.Л. Ющенко, Л.А. Калиниченко, В.М. Савинков, С.С. Свириденко и др.
Наряду с разработками средств для "логического" моделирования данных в конце 60-х гг. стали исследоваться методы организации среды хранения базы данных. В подходе CODASYL с самого начала предусматривалось использовать для управления представлением базы данных в среде хранения специальный язык Data Storage Definition Language (DSDL). Работа над этим языком оказалась довольно продолжительной. Его спецификация была опубликована в 1978 г [4].
В конце 60-х гг. начала формироваться и индустрия программного обеспечения систем баз данных. В это время были созданы широко известные коммерческие СУБД общего назначения, которые вот уже более трех десятилетий не сходят со сцены и содержат в своих недрах львиную долю накопленных и используемых в настоящее время "базоданновых" ресурсов. В этот период компания IBM разработала свою знаменитую систему IMS (1969 г.), основанную на иерархической модели данных. В процессе ее создания разрабатывались эффективные методы хранения и доступа для иерархических баз данных [5]. В отличие от большинства других СУБД, где механизмы среды хранения разрабатывались над средствами файловой системы используемой аппаратно-программной платформы, IBM для достижения высокой эффективности доступа ввела специальные методы доступа в саму файловую систему.
СУБД IDMS (Integrated Data Management System), созданная компанией BF Gudrich Chemical Company (1971 г.) была основана на модели данных СО-DASYL [5].
Период 70-х гг. чрезвычайно богат новыми идеями и подходами в области управления данными, фундаментальными исследованиями, затрагивающими фактически все важнейшие аспекты организации и функционирования систем баз данных, исследовательскими прототипами и коммерческими программными продуктами. В отличие от интуитивно формировавшихся базовых принципов технологий баз данных раннего периода, в 70-е гг. происходило интенсивное развитие функциональности СУБД на основе серьезных теоретических исследований, создания прототипов, проведения экспериментов и анализа их результатов. При этом проблематика теоретических исследований была настолько широкой, что можно смело утверждать, что в 70-е гг. были сформированы теоретические основы современных технологий баз данных и образовалась новая самостоятельная научная ветвь информатики - наука о базах данных. Наибольший вклад в становление и формирование этой науки внесли (Э. Кодд, К. Дейт, Ч. Бахман, М. Стоунбрекер, М. Сенко, М. Злуф, Д. Чемберлин, Д. Цикритзис, Э. Сибли, Ч. Мидоу, Н.П. Федоренко, В.М. Глушков, Е.Л. Ющенко, Л.А. Калини-ченко и др.).
В 70-е гг. было выпущено довольно большое число коммерческих СУБД, основанных на различных моделях данных, и многие из них имели значительное число установок. Так, был создан ряд СУБД для иерархических систем, наиболее распространенными из которых были System 2000 (MRI Systems Corp.), а также несколько новых версий флагманского продукта того времени компании IBM - системы IMS, среди которых IMS/VS. Появился также ряд новых СУБД типа CODASYL - DMS-1100 (UNIVAC), IDS/II (Honeywell), DBMS-10/20 (Digital), новая версия системы IDMS (Cullman) [6]. В этот период были выпущены также известные системы - ADABAS (Software AG), использующая
8 технику инвертированных списков, и TOTAL (Cincom), основанная на модели связанных файлов и обычно относимая к категории сетевых систем [7].
В 70-е гг. довольно многое было сделано в разработке и исследовании различных подходов к моделированию данных. В связи с этим нужно, прежде всего, отметить инициированный циклом работ Э. Кодда ряд публикаций по математической теории реляционных баз данных [8 - 10]. К числу их главных итогов можно отнести: создание теории зависимостей и базирующейся на ней теории нормализации отношений, которая стала основой проектирования реляционных баз данных; разработку алгоритмов редукции выражений реляционного исчисления в реляционную алгебру; первые шаги в исследовании неопределенных значений и проблемы неполноты информации; ряд результатов, связанных с понятием универсального отношения.
Методов доступа, доставшихся формирующимся технологиям баз данных в наследство от техники файловых систем, оказалось явно недостаточно для эффективного управления данными в среде хранения баз данных. Поэтому в рассматриваемый период уделялось много внимания развитию новых методов доступа [9, 11 - 15]. В ряде СУБД стали использовать страничную организацию пространства памяти с индексами страниц, обеспечивающими косвенную адресацию хранимых записей, благодаря чему достигалась подвижность записей на странице. В базах данных нашли также применение методы хеширования, идеи которых были опубликованы еще в начале 60-х гг. В конце 70-х гг. были предложены их разновидности (линейное, динамическое хеширование и т.д.), позволяющие преодолеть существенные ограничения традиционных методов. Интенсивно развивалась техника первичного и вторичного индексирования, было предложено множество подходов к построению механизмов индексирования и поддержке индексов. Методы доступа и процедуры разделения данных и связей в настоящее время представляют большой интерес в качестве объекта исследования. Этот интерес обусловлен как важностью проблемы повышения эффек-
9 тивности обработки данных, так и недостаточной изученности полного множества подобных методов.
В рамках подхода CODASYL уже изначально была выдвинута концепция управления организацией хранимых данных с использованием языка DSDL. Аналогичную задачу пыталась решить группа М. Сенко [16] в ее проекте DIAM, где также были разработаны некоторая модель хранения данных и основанные на ней языковые средства описания хранимых данных.
Важным событием рассматриваемого периода стала публикация работы Р. Байера и Э. МакКрейта об индексах со структурой В-дерева и связанных с ними алгоритмах [17]. Техника В-деревьев и различные ее модификации нашли широкое применение в разработках СУБД. Проблема организации хранения данных, обеспечивающая повышение эффективности обработки в конкретных приложениях АСУП и АСУТП, представляет в настоящее время большой интерес в качестве объекта исследования, что обусловлено, с одной стороны, важностью проблемы повышения эффективности информационных систем предприятий, с другой стороны, недостаточной изученностью вопроса.
Разработки первых реляционных СУБД в начале 70-х гг. породили проблему оптимизации реляционных запросов. Были предложены некоторые подходы к решению этой многоаспектной проблемы, предусматривающие оптимизацию реляционных выражений, выражений условий в запросах, составление оптимальных планов обработки запросов с учетом состояния базы данных и т.д. [11, 18, 19]. Оптимизаторы запросов стали необходимым функциональным компонентом коммерческих серверов баз данных. Эта проблематика далека от своего окончательного решения и представляет интерес для исследований в настоящее время.
Благодаря успешному созданию исследовательских прототипов и первых коммерческих СУБД конца 70-х гг. реляционная теория стала активно применяться на практике. В течение 80-х гг. быстро увеличивалось число коммерческих реализаций реляционных СУБД для различных программно-аппаратных
10 платформ [20]. В 1981 г. поставку своей первой коммерческой реляционной СУБД SQL/DS начала компания IBM. Спустя два года компания выпустила новую систему DB2, положившую начало линии SQL-серверов баз данных, поставляемой IBM до настоящего времени. Был создан ряд новых коммерческих версий системы Ingres, в том числе поддерживающих язык SQL. Было выпущено несколько новых версий Oracle, появилась реляционная СУБД Rdb компании Digital для платформы VAX/MVS. К концу рассматриваемого десятилетия реляционные системы были созданы практически для всех серийно выпускаемых аппаратных платформ и поддерживаемых на них операционных систем, в частности и для персональных компьютеров.
К началу 90-х гг. реляционные СУБД стали составлять доминирующую долю установок СУБД практически на всех распространенных аппаратно-программных платформах [21, 22]. Реляционные СУБД стали использоваться для создания приложений разного масштаба - от офисных до крупных корпоративных - в самых различных областях применения. Большинство из этих систем поддерживало язык SQL. Однако следует отметить, что универсальность языка запросов, обладая понятными преимуществами, не позволяет варьировать производительностью в обработке данных за счет выбора наиболее подходящих структур хранения данных в зависимости от их свойств, либо в текущий момент времени, либо в конкретном приложении АСУП или АСУТП.
В 80-е годы начали разрабатывать географические информационные системы и пространственно-временные базы данных. Для их реализации потребовались новые эффективные методы хранения и доступа для данных такой природы. В связи с этим был предложен ряд подходов к технике индексирования, специально предназначенных для точечных и протяженных в пространстве индексируемых объектов, а также данных, ассоциированных с отметками времени.
Были, в частности, предложены получившие широкое распространение структуры R-деревьев [23] для хранимых представлений прямоугольников и
несколько их расширенных или оптимизированных разновидностей, например Я+-деревья [24] и R*-деревья [25], методы доступа для многомерных точек -квадратичные деревья [26] и K-D-B-деревья [27] и т.д. Для индексирования пространственных фигур была предложена структура клеточных файлов [28].
Многочисленные исследования были посвящены оценкам производительности предложенных методов доступа [29, 30]. Развитие методов эффективной организации хранения пространственно-временных данных является актуальной проблемой в настоящее время и представляет большой интерес для исследований.
Одним из наиболее значимых достижений 90-х гг. в области информационных технологий стало создание открытой глобальной гипермедийной информационной системы, использующей коммуникационную среду Интернет. Эта система получила название World Wide Web (всемирная паутина) [31, 32].
Масштабы WWW и в настоящее время растут беспрецедентными темпами в нескольких измерениях - по числу пользователей, по объему поддерживаемых информационных ресурсов, по количеству разновидностей оказываемых услуг. Актуальной проблемой является эффективная организация хранения и доступа к ресурсам баз данных, доступных в Интернете.
В недалеком будущем, несомненно, можно ожидать появления качественно новых возможностей информационных систем, обеспечиваемых за счет интеграции технологий и информационных ресурсов Web и баз данных на новом уровне [33-34].
Однако, не все аспекты данной проблемы в настоящее время достаточно изучены, что вызывает необходимость их дальнейшей углубленной проработки и исследований. Все это и послужило основанием выборы темы исследования.
Данная диссертационная работа посвящена дальнейшему развитию и конкретизации возможных подходов для организации хранения и поиска информации в базах данных АСУП деревообрабатывающей промышленности.
Цель работы. Цель диссертационной работы заключается в создании моделей, методов и программного обеспечения, обеспечивающих повышение эффективности коммуникаций в БД АСУП деревообрабатывающей промышленности.
Задачи исследования. Для достижения поставленной цели были решены следующие задачи:
Анализ структуры и количества записей производственного учета и разработка обобщенной модели данных АСУП деревообрабатывающей промышленности.
Сравнительный анализ существующих методов организации и доступа к данным, разработка критериев и практических рекомендаций по их выбору в АСУП деревообрабатывающей промышленности.
Исследование возможностей и путей повышения эффективности доступа к данным за счет сжатия данных и их специальной логической организации, основанной на методе комбинированных индексов.
Разработка методов и алгоритмов организации хранения и поиска информации в БД АСУП деревообрабатывающей промышленности с использованием усовершенствованного метода комбинированных индексов и оценка его эффективности.
Разработка программного обеспечения, реализующего усовершенствованный метод комбинированных индексов.
Сравнительный анализ усовершенствованного и стандартного методов комбинированных индексов применительно к БД с различными характеристиками.
Разработка системы зависимостей основных показателей эффективности применения стандартного и усовершенствованного методов комбинированных индексов от различных характеристик информационной модели БД АСУП деревообрабатывающей промышленности.
Объект исследования. Объектом исследования являются информационные процессы управления в рамках АСУП деревообрабатывающей промышленности предприятий г. Екатеринбурга и Уральского федерального округа.
Предмет исследования. Предметом исследования являются методы эффективного доступа к данным БД АСУП деревообрабатывающей промышленности.
Методы исследования. В процессе подготовки отдельных глав диссертационного исследования в зависимости от поставленных целей и решаемых задач использовались положения теории множеств, математической логики, теоретических основ информатики и теории баз данных, а также системный подход и методы статистического анализа.
Достоверность и обоснованность результатов исследования подтверждается научной обоснованностью исходных теоретических положений; целостностью рассмотрения предмета исследования; внутренней непротиворечивостью логики исследования; повторяемостью устойчивых результатов экспериментов; адекватностью применяемых методов целям и задачам исследования; длительным характером экспериментальной работы; личным опытом работы диссертанта.
Теоретические основы исследования. Базой для теоретических положений, практических рекомендаций и расчетов послужили труды по теории информационных систем, автоматизированных систем управления следующих ученых: Глушкова В.М., Берга А.И., Федоренко Н.П., Ющенко Е.Л., Калини-ченко Л.А. и др., теории баз данных, АСУП и АСУТП, в том числе проблематике организации эффективных коммуникаций в информационных системах, а также публикации отечественных и зарубежных авторов по исследуемой теме, а именно: Кодца Э., Мартина Дж., Дейта К., Люма В., Бахмана Ч., Стоунбрекера М., Сенко М. и др. Были также использованы законодательные акты, инструктивно-методические документы, нормативные документы рассматриваемой отрасли промышленности.
14 Основные положения, выносимые на защиту.
Модель данных АСУП деревообрабатывающей промышленности.
Усовершенствованный метод комбинированных индексов.
Методика логического проектирования баз данных АСУП на основе предложенного метода.
Программная реализация усовершенствованного метода комбинированных индексов.
Система зависимостей основных показателей эффективности применения стандартного и усовершенствованного методов комбинированных индексов от характеристик информационной модели БД АСУП деревообрабатывающей промышленности.
Научная новизна. В результате проведенного исследования были получены следующие новые элементы научного знания:
Разработана модель данных, учитывающая специфические особенности функционирования АСУП деревообрабатывающей промышленности.
Предложены метод и алгоритмы доступа к данным БД АСУП деревообрабатывающей промышленности, который позволяет значительно повысить эффективность коммуникаций в БД, а также уменьшить размер файлов БД на вторичном носителе информации.
Разработана система зависимостей основных показателей эффективности применения стандартного и усовершенствованного методов комбинированных индексов от различных характеристик информационной модели БД АСУП деревообрабатывающей промышленности, позволяющая оценить эффективность применения этих методов на этапе логического проектирования БД.
Теоретическая ценность. Разработанный усовершенствованный метод комбинированных индексов является модификацией стандартного метода индексирования, разработанной специально для использования с определенной информационной моделью БД. Он позволяет значительно повысить эффектив-
15 ность коммуникаций в БД АСУП, соответствующих рассматриваемой информационной модели, и является вкладом в теорию автоматизированных систем управления и теорию баз данных.
Практическая ценность. Анализ результатов испытаний разработанного метода показал высокую эффективность его применения для широкого спектра информационных моделей баз данных, например, БД переписи населения, БД комплектующих радиоэлектронной продукции. Сжатое представление данных и связей, используемое в усовершенствованном методе доступа к данным, позволяет существенно повысить скорость обработки транзакций при обработке запросов, а также уменьшить размер файлов БД, имеющих сходные характеристики с БД АСУП деревообрабатывающей промышленности.
Также практической ценностью является то, что разработано программное обеспечение (ПО) в среде разработки Delphi с использованием СУБД Paradox и InterBase, реализующее усовершенствованный метод комбинированных индексов, позволяющее оценить эффективность его применения к БД с заданными характеристиками.
Реализация работы. Основные результаты, изложенные в диссертационной работе, использованы в НИР, проводимой в рамках грантов:
"Исследование моделей и создание комплексов информационных технологий для оценки положения слабоструктурированных объектов в многомерном пространстве". № госрегистрации 01.9.80006371.
"Обеспечение семантической целостности данных в системах обработки информации о сложных слабоформализованных объектах". № госрегистрации 01.20.0005726.
"Создание компьютерной справочно-аналитической информационной системы многофакторной оценки деятельности вузов". № госрегистрации 01.2.00108541.
"Исследование особенностей гуманитаризации образования в высшей технической школе и создание комплекса научно- и учебно-методического
обеспечения блока дисциплин ГСЭ ГОС ВПО". № госрегистрации 01.200.214168.
Результаты работы внедрены:
в АСУП ОАО "Лобва" (Свердловская обл., п. Лобва);
в АСУП ОАО "Ляля-лес" (Свердловская обл., г. Новая Ляля);
в АСУ ЗАО "Свердлеспром" (г. Екатеринбург);
в АСУП ФГУП "Химический завод "Планта" (Свердловская обл., г. Нижний Тагил);
в информационную систему сопровождения конструкторско-технологической документации ОАО "Уральское производственное предприятие "Вектор" (г. Екатеринбург);
в АСУ РИЦ "Исеть" (г. Екатеринбург).
Апробация работы. Основные результаты работы докладывались:
на международной научно-технической конференции "Математические методы в экономике" (г. Пенза, 2002);
на IV Всероссийской научной Интернет-конференции "Компьютерные тех-
нологии и моделирование в естественных науках и гуманитарной сфере" (2002);
на X международной научно-технической конференции "Математические методы и информационные технологии в экономике, социологии и образовании" (Пенза, 2002);
на Всероссийской научно-методической конференции "Телематика'2002" (г. Санкт-Петербург, 2002);
на XVIII Всероссийской научной конференции молодых ученых и студентов "Реформы в России и проблемы управления" (г. Москва, 2003);
на международной научно-технической конференции "Социально-экономические и экологические проблемы лесного комплекса" (г. Екатеринбург, 2001, 2003).
Публикации. Основные результаты диссертации опубликованы в 11 печатных работах автора, а также отражены в зарегистрированном отчете о НИР.
Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения и библиографии из 170 наименований. Работа содержит 144 страницы текста, 23 рисунка, 21 таблицу, 14 страниц библиографии.
Во введении отражены актуальность темы, цели и задачи диссертации, новизна и практическая ценность полученных результатов, структура диссертации и положения, выносимые на защиту.
В первой главе был выполнен анализ структуры и количества записей производственного учета различных деревообрабатывающих производств. В результате были определены свойства информационной модели данных БД АСУП деревообрабатывающей промышленности и построен пример таблицы БД, реализующий свойства информационной модели АСУП деревообрабатывающей промышленности.
Во второй главе был проведен сравнительный анализ существующих методов организации и доступа к данным. Были даны практические рекомендации по выбору оптимальной структуры хранения для БД АСУП деревообрабатывающей промышленности. Также во второй главе были исследованы возможности и пути повышения эффективности доступа к данным.
В третьей главе предлагается метод и алгоритмы организации хранения и поиска информации в базе данных АСУП деревообрабатывающей промышленности, являющиеся усовершенствованным методом комбинированных индексов.
В четвертой главе рассматриваются вопросы программной реализации усовершенствованного метода комбинированных индексов. Рассмотрены функциональные возможности разработанного ПО, возможные режимы функционирования, структура данных в создаваемых программой отчетах. Выявлены зависимости основных показателей эффективности применения стандартного и усовершенствованного методов индексирования от характеристик БД. С
18 использованием разработанного программного обеспечения произведены эксперименты, моделирующие эксплуатацию БД АСУП деревообрабатывающей промышленности, на основании примеров записей, рассмотренных в главе 1.
В заключении подводятся итоги работы, формулируются выводы, вытекающие из результатов исследования.
Первичная информация и требования к ее подготовке
Экономическая информация - основа процессов хозяйственного управления. Поскольку учет есть функция управленческой деятельности, он информативен по своей природе. Информационный характер учета определяется и технологическими особенностями первичной регистрации, сбора, накопления, переработки и выдачи учетных данных. Свойственная учету информационная взаимосвязь с другими управленческими функциями позволяет строить учет 24 ную подсистему на базе единого комплекса информационного обеспечения АСУП.
Информационный процесс, составляющий основное по трудоемкости содержание учета, подлежит изучению, прежде всего как объект автоматизации, осуществляемой с помощью современной техники управления.
Автоматизация технологического процесса переработки исходных сведений в результатные требует глубокого обоснования информативной нагрузки первичных документов и учетных регистров с точки зрения обеспечения необходимого уровня полноты данных, поэтому в автоматизированном учете особенное значение имеет проблема определения состава информации и ее параметров по каждой учетной задаче.
Далее определим основные составляющие элементы ИО АСУП таких производств деревообрабатывающей промышленности как, например, лесопильное, фанерное, мебельное производства. Теория АСУП деревообрабатывающей промышленности представлена в [82-84].
Массивами переменных данных будем называть информационные совокупности, представленные одной или несколькими разновидностями первичных документов или промежуточными группировками.
К массивам условно-постоянного информационного фонда будем относить разнообразные справочники: классификаторы-ценники на материалы, запасные части, малоценные и быстроизнашивающиеся предметы, готовые изделия; кодификаторы работ и расценок, норм материальных и трудовых затрат; шифраторы инвентарного состава основных фондов, личного состава работников предприятия, поставщиков и покупателей, дебиторов и кредиторов; номенклатуры статей расходов и доходов, оплат и вычетов и т.п. В качестве признаков связи между переменной и условно-постоянной информацией в конкретных учетных задачах могут выступать, например, номенклатурный номер материала, шифр работы (производственной операции, комплекса операций), шифр затрат (калькулируемого объекта и калькуляцион 25 ной статьи), шифр изделий (позиции прейскуранта, артикула), номер лицевого счета. В виде постоянных величин (констант) используются числа, являющиеся, например, коэффициентами перевода возможных единиц измерения количества того или иного материала в главную учетную единицу или выражающие такие постоянные категории, как календарное время определенного месяца, т.е. неизменные числовые характеристики отдельных объектов. В иерархии информационных единиц основополагающая роль принадлежит структурным единицам низшего ранга - учетным реквизитам, отображающим классификационные (группировочные), количественные и справочные характеристики хозяйственных операций. Классификационные реквизиты, входящие в вычислительные схемы и сохраняющие постоянные значения для данной частной задачи (расчета), будем называть параметрами учетной информации. К ним относятся, например, обозначения склада, номенклатурного номера материала, объекта получателя и позиции затрат в учетных сообщениях (записях) об операциях отпуска предмета труда в производство. Количественные реквизиты, отражающие операцию по натуре и стоимости, будем называть основаниями. Справочные реквизиты, индивидуализирующие запись, будем называть признаками. В качестве признаков чаще всего фигурируют дата операции и номер документа. По классификационным и справочным реквизитам записи чаще всего осуществляется большая часть запросов к БД АСУП. Элементарным информационным образованием БД АСУП является стандартная бухгалтерская запись (СБЗ), комплекс реквизитов которой отражает минимально необходимый набор учетных сведений о хозяйственных операциях [82]. Всякий учетный реквизит СБЗ может быть выражен целыми числами. Числовые параметры и признаки служат для поиска, выборки, систематизации и других логических действий над записями. Числовые основания, дающие количественное выражение объекта записи, используются для арифметической обработки данных. СБЗ реализуется в виде строки, образованной числами, выражающими технологическую характеристику записи, дату и номер первичного документа или отчетный период, шифры основных синтетического и аналитических счетов, шифры корреспондирующих синтетического и аналитических счетов, натуральное и стоимостное основания. В случае необходимости в запись можно вводить также дополнительные характеристики.
Упорядоченные последовательные файлы
Если записи упорядочены по полям а, Ь, с, то в тех случаях, когда запрос содержит условие поиска с использованием значений полей а, Ь, с, при обработке запросов можно будет применять бинарный поиск. В качестве примера возьмем SQL-запрос, приведенный ниже.
Для простоты предположим, что в каждой странице вторичного носителя информации находится по одной записи. Тогда упорядоченный файл будет выглядеть так, как показано на рис. 2.1. При этом процедура бинарного поиска будет включать следующие этапы. 1. Извлечение средней записи для оставшейся на данный момент части файла. Проверка равенства значений полей извлеченной записи и критериев поиска. В случае равенства извлечение записей прекращается, поскольку требуемая запись найдена. 2. Если значение ключевого поля в извлеченной записи больше, чем искомое значение, то это значит, что искомая запись (если она существует) находится в одной из предыдущих страниц файла. Дальше приведенная выше процедура поиска повторяется для первой половины обрабатываемой части файла. Если значение ключевого поля в записи меньше, чем искомое значение, то искомое значение находится на последующих страницах файла. Дальше указанная выше процедура поиска повторяется для второй половины обрабатываемой части файла. Таким образом, при каждой попытке извлечения записи область поиска сокращается на половину. В среднем, при использовании метода бинарного поиска требуется выполнить приблизительно log2p операций доступа к файлу с р записями. В рассматриваемом случае (рис 2.1) средней записью файла является запись со значениями а2, Ы, с2. Эта запись не является искомой и значения ключевого поля записи больше требуемого значения, потому вся вторая половина файла исключается из области поиска. Теперь следует извлечь среднюю страницу из оставшейся части файла. На этот раз значения ключевого поля (al, Ь2, сі) меньше искомого значения, что позволяет нам исключить из текущей области поиска ее первую половину. После извлечения средней записи из оставшейся на данный момент части файла определяем, что она содержит искомые значения. В общем случае бинарный поиск эффективнее линейного, однако, этот метод чаще применяется для поиска данных в первичной, а не во вторичной памяти. Операции вставки и удаления записей в упорядоченном файле усложняются необходимостью поддерживать установленный порядок записей. Для вставки новой записи нужно найти ее месторасположение в заданном упорядочении, а потом найти пространство для вставки. Если на нужной странице достаточно места для размещения новой записи, то тогда потребуется переупорядочить лишь только эту страницу, после чего записать ее на диск. Если же свободного места недостаточно, то в таком случае потребуется переместить одну или несколько записей в следующую страницу. Аналогично, в следующей странице также может не оказаться достаточно свободного места, и из нее также потребуется переместить некоторые записи в следующую страницу и т.д. Таким образом, вставка записи в начало большого файла может оказаться очень длительной процедурой. Для решения этой проблемы часто используется временный неотсортированный файл, который называется файлом переполнения или файлом транзакции. При этом все операции вставки выполняются в файле переполнения, содержимое которого периодически сливается с основным отсортированным файлом. Таким образом, операции вставки выполняются более эффективно, но при этом некоторое отрицательное влияние оказывается на выполнение операций извлечения данных. После осуществления бинарного поиска в отсортированном файле придется выполнить линейный поиск в файле переполнения. При удалении записи потребуется реорганизовать файлы так, чтобы удалить пустующие места. Последовательный файл является наиболее удобной структурой для хранения данных в следующих случаях: 1. Данные загружаются в таблицу крупными блоками. Например, при заполнении вновь созданной таблицы, в нее одновременно может загружаться большое количество данных. Если последовательная организация была выбрана для вновь созданной таблицы как исходный тип файловой организации, то реструктуризация файла таблицы после загрузки основного объема данных может оказать заметное влияние на эффективность ее использования. 2. Весь файл таблицы занимает несколько страниц. В этом случае время поиска любой записи будет невелико, даже при последовательном просмотре всех строк таблицы. 3. При каждом обращении к таблице выборке подлежат все ее записи (в любом порядке). 4. Таблица имеет дополнительные структуры поиска - например, индекс по ключу. В этом случае использование файлов последовательной организации позволяет достичь экономии дискового пространства. Файлы последовательной организации неэффективны в случаях, когда файл таблицы имеет большой объем и доступ необходим только к некоторым записям таблицы. При использовании упорядоченной последовательной организации файла БД АСУП деревообрабатывающей промышленности в рамках СУБД, поддерживающей бинарный поиск, среднее время запроса сократилось на 65%. Размер файла БД при упорядоченной последовательной организации не изменился.
Поиск записей в отношении R, где поле с принимает значение с2
Вопросы программирования баз данных и различных методов доступа к данным рассмотрены в [124-165].
Практическая реализация усовершенствованного метода комбинированных индексов была произведена в среде разработки Borland Delphi 7.0 с использованием СУБД Borland Paradox 10 и Borland InterBase 7.0.
Интерфейс разработанного ПО изображен на рис. 4.1. Разработанное ПО позволяет проводить эксперименты по реализации усовершенствованного метода комбинированных индексов для БД с заданными характеристиками. Исходными данными для проведения экспериментов являются: - количество значений для каждого из полей индексирования; - количество записей в таблице данных. ПО позволяет получить данные для дальнейшего сравнения эффективности применения усовершенствованного метода комбинированных индексов по сравнению со стандартным методом. ПО может функционировать в "ручном" и "автоматическом" режимах. В "ручном" режиме программа функционирует в соответствии с управляющим воздействием пользователя на кнопки запуска различных процедур программы (например, процедуры заполнения и упорядочивания таблицы данных, заполнения таблицы индекса). В "автоматическом" режиме программа функционирует по заданному сценарию. Сценарий представляется в виде массива данных, где каждая строка массива представляет собой достаточный для проведения эксперимента набор характеристик информационной модели БД. позволяет осуществлять четыре вида запросов по значениям полей индексирования: - запрос на выборку записей с использованием стандартного комбинированного индекса; - запрос на выборку записей с использованием усовершенствованного комбинированного индекса; - запрос на подсчет количества записей с использованием стандартного комбинированного индекса; - запрос на подсчет количества записей с использованием усовершенствованного комбинированного индекса. В "ручном" режиме пользователь может производить запросы в любом порядке и произвольно изменять критерии запросов. В "автоматическом" режиме все виды запросов осуществляются последовательно заданное количество раз (в рассматриваемых экспериментах - 5000) с автоматическим изменением критериев. В "автоматическом" режиме для каждой строки массива сценария программой создается отчет специальной формы, пригодной для дальнейшей обработки данных средствами табличного процессора Microsoft Excel. В отчете фиксируются следующие показатели: - количество записей в таблице данных; - количество возможных комбинаций значений индексируемых полей; - время создания индекса по усовершенствованному методу; - размер таблицы данных; - размер файлов стандартного индекса; - размер файлов индекса, построенного по усовершенствованному методу комбинированных индексов. - время запроса на выборку записей с использованием стандартного комбинированного индекса; - время запроса на выборку записей с использованием усовершенствованного комбинированного индекса; - время запроса на подсчет количества записей с использованием стандартного комбинированного индекса; - время запроса на подсчет количества записей с использованием усовершенствованного комбинированного индекса. Дальнейшая обработка данных средствами табличного процессора MS Excel позволяет получить следующие показатели эффективности применения усовершенствованного метода комбинированных индексов: - изменение размера файлов комбинированного индекса; - изменение размера файлов БД в целом; - изменение времени запроса на выборку записей; - изменение времени запроса на подсчет количества записей. Вышеперечисленные показатели позволяют оценить целесообразность применения усовершенствованного метода комбинированных индексов для БД с заданными характеристиками. Для каждой из возможных комбинаций значений полей а, Ь, с, d осуществляется поиск записей в таблице данных (R). Если запись с искомой комбинацией существует, то в таблицу индекса добавляется запись, содержащая в поле IVal закодированное значение найденной комбинации, в поле n_f наименьшее значений поля N_pp из значений найденных записей.
Алгоритм выборки записей с использованием усовершенствованного метода комбинированных индексов
Основным результатом диссертационной работы является разработка усовершенствованного метода комбинированных индексов. Результаты диссертационной работы сводятся к следующему: 1. На основе анализа структуры записей производственного учета различных видов производств деревообрабатывающей промышленности разработана обобщенная модель данных АСУП деревообрабатывающей промышленности. Эта модель и построенный на ее основе пример отношения БД позволили выработать рекомендации по использованию различных методов повышения эффективности коммуникаций в БД АСУП деревообрабатывающей промышленности в целом. 2. Проведен сравнительный анализ существующих методов организации и доступа к данным, рассмотрены их преимущества и недостатки применительно к модели данных АСУП деревообрабатывающей промышленности. Наиболее эффективным методом организации доступа к данным БД АСУП деревообрабатывающей промышленности из реализованных в настоящее время в СУБД является метод индексирования, а точнее, метод плотных вторичных комбинированных индексов. 3. Исследованы возможности повышения эффективности доступа к данным за счет сжатия данных и их специальной логической организации, основанной на методе комбинированных индексов. 4. Разработаны методы и алгоритмы организации хранения и поиска информации в БД АСУП деревообрабатывающей промышленности, являющиеся усовершенствованным методом комбинированных индексов. 5. Разработано программное обеспечение в среде Borland Delphi с использованием СУБД InterBase и Paradox, реализующее усовершенствованный метод комбинированных индексов. Разработанное ПО позволяет получить данные для проведения сравнительного анализа усовершенствованного и стандартного методов комбинированных индексов применительно к БД с различными характеристиками. 6. Анализ данных проведенных экспериментов показал следующие преимущества и недостатки усовершенствованного метода комбинированных индексов по сравнению со стандартным методом: - время создания индекса по усовершенствованному методу довольно велико. Это можно объяснить тем, что процедура создания индекса по усовершенствованному методу реализована в виде программной надстройки над СУБД, в то время как стандартная процедура индексирования реализована на уровне ядра СУБД. В случае реализации усовершенствованного метода на этапе заполнения БД на уровне ядра СУБД можно ожидать снижения времени создания индекса в 20-30 раз; - размер файлов индекса, построенного по усовершенствованному методу комбинированных индексов, увеличивается с ростом количества записей таблицы данных в 2,8 раза медленнее, чем размер файлов стандартного индекса, что говорит о более сжатом представлении связей между полями и указателей в усовершенствованном комбинированном индексе; - в среднем размер файлов индекса, построенного по усовершенствованному методу, на 51,4% меньше, чем при использовании стандартного метода, а размер БД в целом - меньше на 30,2%; - время запросов на выборку записей с использованием усовершенствованного индекса с ростом количества записей таблицы данных увеличивается в 24 раза медленнее, чем при использовании стандартного индекса, поэтому процент снижения времени запросов на выборку записей с использованием усовершенствованного метода комбинированных индексов увеличивается с ростом количества записей в таблице данных; - время запросов на подсчет количества записей с использованием усовершенствованного индекса с ростом количества записей таблицы данных увеличивается в 95 раз медленнее, чем при использовании стандартного индекса; - в среднем время запросов на выборку записей при использовании усовершенствованного метода комбинированных индексов меньше на 34,5%, а время запросов на подсчет количества записей - меньше на 97,7%, чем соответствующее время при использовании стандартного индекса. 7. Разработанная система зависимостей основных показателей эффективности применения стандартного и усовершенствованного методов комбинированных индексов позволяет оценить эффективность применения того или другого метода при различных значениях характеристик информационной модели БД на этапе логического проектирования БД АСУП деревообрабатывающей промышленности. 8. Разработанное программное обеспечение позволяет смоделировать БД с необходимыми характеристиками и получить фактические показатели времени запроса и размера файлов с использованием стандартного и усовершенствованного методов комбинированных индексов до начала фактической эксплуатации БД АСУП деревообрабатывающей промышленности. 9. С использованием разработанного ПО произведены эксперименты, моделирующие эксплуатацию БД АСУП различных видов производств деревообрабатывающей промышленности. По всем примерам БД, кроме БД фанерного производства по фиксированию остатков технологической щепы в бункерах, наблюдается улучшение показателей размера файлов БД и времени запросов. Следовательно, для всех этих видов производств рекомендуется к использованию усовершенствованный метод комбинированных индексов.
В ходе диссертационной работы разработаны модели, методы и программное обеспечение, позволяющее значительно повысить эффективности коммуникаций в БД АСУП деревообрабатывающей промышленности, т.е. цель диссертационной работы достигнута.
Научные исследования, выполненные в диссертационной работе, используются не только на предприятиях деревообрабатывающей промышленности, а также в проектных реализациях автоматизированных систем управления ряда предприятий различных отраслей промышленности г. Екатеринбурга и Свердловской области.
