Управление базами данных в системах реального времени и встроенных системах

Переведено БНТП по заказу Interface Ltd.

Часть I. Базы данных в системах реального времени и встроенных системах

I. Введение. Роль баз данных в приложениях реального времени

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

К сожалению, это общее утверждение проистекает из идеи, что понятие «база данных» является синонимом больших реляционных баз данных в рамках всего предприятия (как те, что производятся компанией Oracle) или неэффективных и медленных персональных баз данных (таких как Microsoft Access). Многие разработчики полагают, что поскольку такие базы данных не годятся для встроенных систем и систем реального времени, то им придется создавать собственные структуры управления данными с нуля.

Однако в данном случае нет необходимости заново «изобретать колесо». Существует другой тип баз данных, который радикально отличается от хорошо известных СУРБД. Эти БД является испытанным решением для хранения, извлечения и манипулирования данными во встроенных приложениях или приложениях реального времени на многих популярных операционных системах реального времени (RTOS). RDM – это именно такой процессор баз данных низкого уровня или встроенная база данных. Эта база данных встраивается в приложение на самом низком уровне и основана на хорошо себя зарекомендовавшем и высокоэффективном микроядре компании Birdstep. Данное микроядро включает в себя библиотеку функций языка C, которые встроены в приложение и работают с данными напрямую (в отличие от SQL C-API, который создает дополнительные слои между приложением и данными, хранящимися в базе данных).

II. Требования, предъявляемые к базе данных

Ниже перечислены свойства, которые важны для разработчиков приложений реального времени.

• Размер – минимальный объем использования ОЗУ и дискового пространства.
• Производительность – характеристика особенно важная для операционных систем реального времени.
• Надежность – это означает, что система должна работать без контроля со стороны человека.
• Предсказуемость – необходимость в предсказуемости таких параметров, как размер и производительность.
• Низкоуровневый контроль – способность контролировать количество операций ввода/вывода и время их совершения.

RDM превосходно подходит для RTOS-приложений, поскольку эта база данных была разработана с учетом указанных выше свойств. Кроме того, компания Birdstep более 10 лет занимается конструированием и улучшением этих свойств. Этот процессор баз данных доступен для 16- и 32-битных платформ с поддержкой множества операционных систем реального времени (UNIX и 16- и 32-битные версии Windows также доступны).

Размер

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

Обычно процессоры баз данных требуют приблизительно 400 Кб ОЗУ в зависимости от того, сколько C-функций реально используется. При использовании библиотеки классов C++ вместо C API нужно добавить еще 80 Кб. Сама база данных также может быть целиком загружена в ОЗУ.

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

Производительность

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

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

Надежность

Ядро RDM, написанное на языке C, а также его версия, основанная на библиотеке классов C++, более 10 лет пользуется успехом у разработчиков. С течением времени RDM превратился в испытанный и стабильный процессор баз данных. А то, что Birdstep предоставляет программный код RDM, обеспечивает дополнительные гарантии.

Целостность данных гарантируется за счет транзакций RDM и его механизма автоматического восстановления, который обеспечивает завершенность транзакций при нарушении электроснабжения и системных сбоях.

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

Предсказуемость

Возможно, эта характеристика даже более важна для разработчиков приложений реального времени, чем производительность сама по себе. Способность в сжатые сроки предсказывать, сколько времени займет та или иная операция над БД и сколько дискового пространства понадобится для базы данных, является насущно необходимой. Эти статистические данные должны оставаться неизменными при росте БД.

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

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

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

Низкоуровневый контроль

В случае RDM можно увеличить продуктивность за счет использования библиотеки классов C++. Но реальным преимуществом является следующее: если необходим реальный контроль того, что процессор баз данных делает на самом низком уровне, если нужно избавится от избыточности или добиться максимальной производительности, требуется использовать низкоуровневый C-API. При необходимости к использованию функций C-API можно обратиться в любое время.

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

Библиотека классов C++ предоставляет функции и операторы, позволяющие объединять два или три вызова C API в единую операцию.

RDM также обеспечивает контроль над физической структурой базы данных. Все данные хранятся «постранично». Отдельная страница состоит из нескольких записей или ключевых значений в блоке фиксированного размера. Запись и чтение данных происходит на одной странице за раз. Поскольку можно задавать размер страницы, то можно и указывать, сколько записей или ключевых значений могут быть прочитаны одновременно. За счет использования подобных параметров тонкой настройки можно улучшить производительность приложений, использующих RDM.

Все типы данных, разрешенные в языке C, могут храниться в базе данных RDM, включая структуры и массивы. Это ускоряет ввод/вывод данных за счет отказа от транзакций ненужных типов данных.

III. Архитектура баз данных: важное преимущество

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

Большинство разработчиков знакомы с реляционными моделями баз данных, используемых в системах управления реляционными базами данных (СУРБД), таких, как БД компаний Oracle, Informix, Sybase и так далее. Тем не менее, альтернативной архитектурой данных, которая может быть радикально быстрее и эффективнее, является модель сетевой базы данных, основанной на указателях.

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

Оставшаяся часть настоящей статьи посвящена описанию различий между моделями реляционных баз данных и сетевых баз данных, основанных на указателях. Кроме того, ниже предлагается эталонный тест, демонстрирующий преимущества в скорости и эффективности сетевой модели по сравнению с реляционной моделью в типичной для бизнеса ситуации. Предлагаемый тест сравнивает сетевое решение Birdstep Database Manager и реляционные модели в применении к одним и тем же задачам и демонстрирует 15-кратное превосходство сетевой модели в скорости перед реляционной версией.

IV. Определение реляционных и сетевых моделей

В реляционной модели данные хранятся в таблицах, состоящих из столбцов и строк. При возникновении необходимости в данных более чем из одной таблицы одна из операций объединения связывает эти данные, используя копию столбца от каждой таблицы. Несмотря на гибкость реляционной модели, ее производительность ограничена необходимостью создавать новые таблицы для хранения результатов реляционных операций, тогда как хранение избыточных столбцов в связанных таблицах приводит к росту размера базы данных. Кроме того, обработка операций объединения расходует ценные системные ресурсы – получение объединенных данных из двух таблиц приведет к замедлению работы приложения, а запрос на получение данных более чем из двух таблиц может полностью «подвесить» систему.

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

Проблема заключается в том, что поиск в индексном файле может потребовать две или три итерации (т.е. два или три обращения к диску) на каждую запись, к которой осуществляется доступ. Именно здесь сетевая модель и «множества» RDM могут привести к значительной экономии времени. Фактически такое множество представляет собой связанный список, представляющий тип отношений «один-ко-многим». Указатели к следующему и предыдущему членам связывают каждый элемент данного множества. «Хозяин» множества (т.е. «один» в отношении «один-ко-многим») указывает на каждый конец связанного списка. Таким образом, переход от хозяина к первому члену требует только одну операцию доступа к диску. Подобным образом осуществляется переход к следующему члену и так далее. Каждый элемент множества обладает указателем на своего хозяина, т.е. для перехода от него к хозяину также требуется только одна операция доступа к диску.

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

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

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

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

Часть II. Эталонный тест: Реляционные модели против сетевых

Задача

Многие производственные предприятия создают свои продукты из комплектующих и сборочных узлов партий/серий. Сюда относятся как шариковая ручка с полудюжиной частей, так и лайнер Боинг 747, состоящий более чем из 4 миллионов комплектующих. Чтобы сохранить конкурентоспособность, производители должны полагаться на компьютерные приложения для контроля материально-производственных запасов запчастей. Эти приложения должны поставлять занимающемуся управлением производством персоналу точную информацию о конечной стоимости продукта и данные для контроля производственных запчастей и снабжения.

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

Структура спецификаций материалов

Компонентная структура электрической газонокосилки включает в себя множество уровней, соответствующих комплектующим и сборочным узлам, с дискретными компонентами на нижних уровнях. Иногда пункт компонента (например, колеса), связанного с родительским элементом встречается несколько раз. Кроме того, один и тот же компонент (например, болт) может применяться в нескольких сборочных узлах; также могут присутствовать несколько готовых изделий (например, различные модели газонокосилки), использующих общие сборочные узлы.
Каким же образом смоделировать спецификацию материалов в структуре базы данных? Сначала рассмотрим реляционный подход. Его иллюстрирует словарь данных из Приложения А. Нужны две таблицы: одна для записи позиции, другая – для связующих записей, называемых записями спецификации. Имеется по одной записи позиции для каждой уникальной запчасти, сборочного узла и конечного продукта, а также по одной записи спецификации на каждую связь между родительским элементом и пунктом компонента. Для таблицы позиций необходим индекс соответствующего идентификатора, а для таблицы спецификации нужен индекс типа «родительский-ID/номер последовательности». Заданный идентификатор позиции позволяет найти запись позиции и все записи спецификации с указанной позицией в качестве родительской. Для каждой записи спецификации можно получить идентификатор компонента и так далее.

Диаграмма логической схемы на Рис. 1 иллюстрирует сетевой подход. Здесь записи позиции и спецификации соединены двумя множествами: спецификацией материалов (СМ) и местом назначения. На диаграмме для газонокосилки каждый прямоугольник представлял бы пример физической записи в базе данных.

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

Рис. 1: Диаграмма-схема для базы данных сетевой модели.

Допущения эталонного теста

Словари данных, представленные в Приложениях А и Б, демонстрируют сходства и различия между реляционной и сетевой структурами данных спецификации материалов. К существенным полям относятся переменные id_code, cost и quantity. Описание и данные служат для заполнения записей и придания примеру более реалистичного характера. Последовательность и поле component_count требуются только для реляционной части теста, поскольку они являются родительскими и компонентными идентификаторами в записи спецификации.

При выполнении каждая программа из эталонного теста запрашивает у пользователя количество уровней и число компонентов на каждом уровне. Записи позиции генерируются вместе со случайными 15-буквенными идентификаторами. Для сравнения затрачиваемого времени число компонентов фиксировано и равняется 4, тогда как количество уровней меняется.

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

Реляционная программная часть эталонного теста

В Приложении В приведена реляционная программная часть эталонного теста, написанная на языке C. Две основные функции – rbuild_bill() и rget_cost() – являются рекурсивными (вызывающими сами себя), чтобы облегчить многоуровневую обработку. При одиночном обращении функция rbuild_bill() создает один уровень данной спецификации (пункт компонента и записи спецификации) и вызывает сама себя для создания более низких уровней. Заметим, что каждая запись позиции содержит подсчет своих компонентов и каждая запись спецификации содержит номер последовательности.

Функция rbuild_bill() достаточно проста, тогда как rget_cost() заслуживает более пристального внимания. Последняя функция возвращает подсчитанную стоимость запчастей, расположенных в спецификации ниже обозначенного пункта. Она считывает число компонентов из записи позиции и пробегает «закрепленные» записи спецификации в поисках пунктов компонентов. Существует много поисковых ключей индекса и ключей следующих операций, но один из поисковых ключей более интересен, чем другие. Еще раз обратимся к Рис. 1. Предположим, что идет отслеживание основных компонентов газонокосилки (двигатель, ходовая часть, колеса), а в настоящее время обрабатывается ходовая часть. Затем происходит переход к обработке компонентов ходовой части. В индексе спецификации происходит «потеря места», поэтому нет возможности перейти к колесам, прежде чем ходовая часть опять не будет найдена в индексе. Необходимо повторить поиск ключа, поскольку B-древесные схемы индексирования не обладают возможностями запоминания.

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

Сетевая программная часть эталонного теста

В Приложении Г представлена программа на языке C для эталонного тестирования сетевой модели. Двумя основными (рекурсивными) функциями являются команды build_bill() и get_cost(). При одиночном обращении функция build_bill() создает один уровень данной спецификации (пункт компонента и записи спецификации) и вызывает сама себя для создания более низких уровней. Следует отметить, что запись спецификации не нуждается в идентификаторах родительских элементов и пунктов компонентов, так как она напрямую связана с записями позиции через множества, определяющие последовательность компонентов. Родительская запись позиции не нуждается в поле подсчета компонентов, поскольку эта информация также встроена и в структуру множества.

Функция get_cost() иллюстрирует способность модели сетевых баз данных «удерживать свое место» во время обработки множеств. При каждом вводе get_cost() текущая информация о хозяине и членстве множества спецификаций материалов сохраняется в стеке, чтобы быть восстановленной по завершению работы функции. Таким образом, нижние уровни спецификации материалов могут обрабатываться без приостановки обработки высших уровней.

Результаты эталонного тестирования RDM

Из эталонного теста было получено три важных множества чисел:

1. требуемое пространство на жестком диске;
2. время, необходимое для создания базы данных (время создания);
3. время, необходимое для подсчета стоимости (время выборки).

Рис. 2: Запоминающее устройство

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

Рис. 3: Время создания                                     Рис. 4: Время выборки

Так почему же программа сетевой модели настолько быстрее? Она быстрее, так как не тратит время на обработку индекса. В шестиуровневом эталонном тесте, например, для подсчета стоимости требуется около 7000 поисковых ключей и 3000 ключей следующих операций. В то же время программе сетевой модели нужен только один поисковый ключ. Соединения множеств сетевой модели обеспечивают прямые связи между пунктами и спецификациями. При тестировании сетевой модели время в расчете на запись растет вместе с размером файла, так как глубина узлов индексации увеличивается, однако график производительности сетевой модели остается плоским.

Приложение А

DDL для реляционной модели баз данных

/* RBOM.DDL RELATIONAL схема спецификации материалов для эталонного теста RDM */
/* версия номера последовательности */
/* копирайт (c) 1996, Birdstep Technology, Сиетл, штат Вашингтон */
database rbom {
data file “rbom.d01” contains ritem;
data file “rbom.d02” contains rbill;
key file “rbom.k01” contains rid_code;
key file “rbom.k02” contains rbom, rwhere_used;
record ritem {
unique key char rid_code[16];
char rdescription[58];
double rcost;
int rcomponent_count;
}
record rbill { char rparent[16];
char rcomponent[16];
int rsequence;
double rquantity;
int rlevel;
long reffectivity_in; /* данные */
long reffectivity_out; /* данные */
compound key rbom {
rparent;
rsequence;
}
compound key rwhere_used {
rcomponent;
rsequence;
}
}
}

Приложение Б

DDL для сетевой модели баз данных

/* RBOM.DDL схема спецификации материалов эталонного теста RDM */
/* копирайт (c) 1996, корпорация Birdstep , Иссака, штат Вашингтон */
database bom {
data file “bom.d01” contains item;
data file “bom.d02” contains bill;
key file “bom.k01” contains id_code;
record item {
unique key char id_code[16];
char description[58];
double cost;
}
record bill {
double quantity;
int level;
long effectivity_in;
long effectivity_out; }
set bom {
order last;
owner item; member bill; }
set where_used {
order last;
owner item;
member bill;
}
}

Приложение В

/* СПЕЦИФИКАЦИЯ МАТЕРИАЛОВ ЭТАЛОННОГО ТЕСТА RDM (РЕЛЯЦИОННАЯ ВЕРСИЯ с номерами последовательностей) */
#include <stdio.h>
#include <vista.h>
#include <string.h>
#include <ctype.h>
#include <time.h>
#include «rbom.h»
double rget_cost(char*);
void random_id(char*);
void rbuild_bill(char*);
struct rbill RBill;
struct ritem RItem;
int current_level, max_level, max_members;
double rolled_up_cost;
char response[20];
time_t start_time, end_time, elapsed_time;
main() {
int i;
printf(«\nRELATIONAL bom benchmark\n»);
RItem.rid_code[0] = ‘\0’;
RItem.rcost = 1.0L; RBill.reffectivity_in = 0L;
RBill.reffectivity_out = 0L;
RBill.rquantity = 1.0L;
current_level = 0;
printf(«\nEnter number of levels: «);
gets(response);
max_level = atoi(response);
printf(«\nEnter number of members per level: «);
gets(response);
max_members = atoi(response);
d_setpages(32,8); d_open(«rbom»,»o»);
d_initialize(); /* удаление всех файлов с данными */
printf(«building bill file\n»); time(&start_time);
strcpy(RItem.rid_code, «AAAAAAAAAAAAAAA»);
RItem.rcomponent_count = max_members;
if(d_fillnew(RITEM, &RItem) != S_OKAY) { /*прототип пункта*/ printf(«duplicate part %s\n», RItem.rid_code);
}
rbuild_bill(«AAAAAAAAAAAAAAA»);
time(&end_time);
elapsed_time = end_time — start_time;
printf(«time to build file was %ld seconds\n»,elapsed_time);
printf(«rolling up cost\n»);
time(&start_time);
rolled_up_cost = rget_cost(«AAAAAAAAAAAAAAA»);
time(&end_time);
elapsed_time = end_time — start_time;
printf(«total rolled up cost = %10.2lf\n», rolled_up_cost);
printf(«time to compute cost was %ld seconds\n»,elapsed_time);
d_close(); }
/* RGETCOST.C рекурсивная подпрограмма подсчета стоимости для низших уровней спецификации.
Данные о стоимости хранятся только на самых низких уровнях спецификации*/
double rget_cost(char* parent)
{
double total_cost;
/*для этого пункта и ниже*/ int component_count;
struct rbom Rbom, Rbom_save;
struct rbill RBill_local;
d_keyread(&Rbom_save);
/* сохранение ключа высшего уровня*/
d_keyfind(RID_CODE, parent);
/* поиск родителя */ d_recread(&RItem);
/* считывание родителя для получения количества компонентов */
component_count = RItem.rcomponent_count;
if(component_count == 0) { /* для этого родителя нет компонентов */
return RItem.rcost; /* возвращает стоимость данного низкоуровневого пункта */ }
/* имеется по крайней мене один компонент, т.е. идет спуск на один уровень */ strcpy(Rbom.rparent, parent);
Rbom.rsequence = 0;
d_keyfind(RBOM, &Rbom);
/* поиск первой записи спецификации */ total_cost = 0.0L;
for( ; ; ) {
d_recread(&RBill_local);
/* считывание записи спецификации для получения идентификатора компонента */ total_cost += rget_cost(RBill_local.rcomponent) *
RBill_local.rquantity; /* рекурсивный вызов */
if(—component_count == 0) break;
d_keynext(RBOM); /* поиск следующей записи спецификации */
}
d_keyfind(RBOM, &Rbom_save); /* репозиция в индексе */
return total_cost; /* для всего ниже данного пункта */
}
/* RBLDBILL.C рекурсивная подпрограмма для создания одного уровня спецификации путем добавления компонентов к родительским ссылкам глобальных переменных ‘current_level’ и ‘max_level’ */
void rbuild_bill(char* parent)
{
int i;
char id_code[16];
current_level++;
for(i=0; i<max_members; i++) {
random_id(RItem.rid_code);
if(current_level < max_level) { /* подсчет множества компонентов в ITEM */
RItem.rcomponent_count = max_members;
}
else {
RItem.rcomponent_count = 0;
}
if(d_fillnew(RITEM, &RItem) != S_OKAY) { /* запись нового компонента в ITEM */
printf(«duplicate part %s\n», RItem.rid_code);
}
strcpy(RBill.rparent, parent);
strcpy(RBill.rcomponent, RItem.rid_code);
RBill.rsequence = i;
RBill.rlevel = current_level;
d_fillnew(RBILL, &RBill); /* создает новую запись BILL */
if(current_level < max_level) { /* если нижний конец еще не достигнут */
strcpy(id_code, RItem.rid_code);
rbuild_bill(id_code); /* рекурсивный вызов для создания следующего уровня */
}
}
current_level—;
return;
}
void random_id(char* string)
/* генерирует 15-буквенный идентификатор */
{
int i, j;
for(i=0; i<15; i++) {
do {
j = toupper(rand() & 127);
} while (j < ‘A’ || j > ‘Z’);
string[i] = j;
}
string[i] = ‘\0’;
}

Приложение Г

/* СПЕЦИФИКАЦИЯ МАТЕРИАЛОВ ЭТАЛОННОГО ТЕСТА RDM (версия сетевой модели) */
#include <stdio.h>
#include <vista.h>
#include <string.h>
#include <ctype.h>
#include <time.h>
#include «bom.h»
double get_cost();
void random_id(char*);
void build_bill();
int current_level, max_level, max_members;
double rolled_up_cost;
char response[20];
time_t start_time, end_time, elapsed_time;
struct bill Bill; /* глобальная запись Bill */
struct item Item; /* глобальная запись ITEM */
main() {
int i;
Item.id_code[0] = ‘\0’;
Item.cost = 1.0L;
Bill.effectivity_in = 0L;
Bill.effectivity_out = 0L;
Bill.quantity = 1.0L;
current_level = 0;
printf(«\nEnter number of levels: «);
gets(response);
max_level = atoi(response);
printf(«\nEnter number of members per level: «); gets(response);
max_members = atoi(response);
d_setpages(32,8);
d_open(«bom»,»o»);
d_initialize(); /
* erase all old data */
printf(«building bill file\n»);
time(&start_time);
strcpy(Item.id_code, «AAAAAAAAAAAAAAA»);
if(d_fillnew(ITEM, &Item) != S_OKAY) { /* прототип пункта */
printf(«duplicate part %s\n», Item.id_code);
}
d_setor(BOM); /* инициализация с первоначальной прогонкой csoget */
build_bill(); /* рекурсивный вызов для создания многоуровневой спецификации */
time(&end_time);
elapsed_time = end_time — start_time;
printf(«time to build file was %ld seconds\n»,elapsed_time);
printf(«rolling up cost\n»);
time(&start_time);
d_keyfind(ID_CODE, «AAAAAAAAAAAAAAA»); /* поиск прототипа */
rolled_up_cost = get_cost(); /* рекурсивный вызов для подсчета стоимости */
time(&end_time);
elapsed_time = end_time — start_time;
printf(«total rolled up cost = %10.2lf\n», rolled_up_cost);
printf(«time to compute cost was %ld seconds\n»,elapsed_time);
d_close(); /* закрытие базы данных */
}
/* GETCOST.C рекурсивная подпрограмма для подсчета стоимости, начиная с низших уровней спецификации в предположении, что оцениваемым пунктом является текущая запись. Данные о стоимости находятся только на низших уровнях спецификации */
double get_cost()
{
DB_ADDR bom_owner;
double total_cost; /* для этого пункта и ниже */
long member_count;
struct bill Bill_local;
d_csoget(BOM, &bom_owner); /* сохранение старого хозяина BOM */
d_setor(BOM); /* задать текущего хозяина BOM из текущей записи */
d_members(BOM, &member_count); /* число связанных компонентов */
if(member_count == 0) { /* нижний конец достигнут */
d_recread(&Item); /* считывание текущего ITEM для получения стоимости */
d_csoset(BOM, &bom_owner); /* восстановление старого хозяина BOM */
return Item.cost; /* просто считывание записи ITEM */
}
/* имеется по крайней мере один член, т.е. идет спуск на один уровень */
total_cost = 0.0L;
while(member_count—) { /* циклическое прохождение всех компонентов */
d_findnm(BOM);
d_recread(&Bill_local); /* считывание записи спецификации для получения количества */
d_findco(WHERE_USED); /* запись компонента ITEM теперь является текущей */
total_cost += get_cost() * Bill_local.quantity; /* рекурсивный вызов */
}
d_csoset(BOM, &bom_owner); /* восстановление старого хозяина BOM */
return total_cost;
}
/* BLDBILL.C рекурсивная подпрограмма для создания одного уровня спецификации путем добавления компонентов к родителю в предположении, что родителем является текущая запись ссылок глобальных переменных ‘current_level’ и ‘max_level’ */
void build_bill()
{
DB_ADDR bom_owner;
int i;
current_level++;
d_csoget(BOM, &bom_owner); /* сохранение старого хозяина BOM */
d_setor(BOM); /* задать текущего хозяина BOM из текущей записи */
for(i=0; i<max_members; i++) {
random_id(Item.id_code);
if(d_fillnew(ITEM, &Item) != S_OKAY) { /* новая запись компонента в ITEM */
printf(«duplicate part %s\n», Item.id_code); }
d_setor(WHERE_USED);
Bill.level = current_level;
d_fillnew(BILL, &Bill); /* создает новую запись BILL */
d_connect(BOM); /* подключение к ее родительскому ITEM */
d_connect(WHERE_USED); /* подключение компонента ITEM к BILL rec */
if(current_level < max_level) { /* если нижний конец еще не достигнут */
d_setro(WHERE_USED); /* задать денежное обращение для нижнего уровня */
build_bill(); /* рекурсивный вызов для создания следующего уровня*/
}
}
current_level—;
d_csoset(BOM, &bom_owner); /* восстановление старого хозяина BOM */
return;
}
void random_id(char* string) /* генерирует 15-буквенный идентификатор */
{
int i, j;
for(i=0; i<15; i++) {
do {
j = toupper(rand() & 127);
} while (j < ‘A’ || j > ‘Z’);
string[i] = j;
}
string[i] = ‘\0’; }