Оценка эффективности схем баз данных

верность ответов на вопросы серии (in) в среднем получается более высокой, чем для серии (out).

Можно считать, что din = 0,9; dout = 0,6. Тогда если значения коэффициента необходимости некоторого показателя по сериям (in) и (out) равны соответственно kNij^(in) = 0,8 и kNij^(out) =1, то наиболее достоверное значение

kNijk(i)dl 0.8*0.9+1.0*0.6

knijk =------------=--------------------= 0,88,

d1 0.9+0.6

где 1 принимает значения из множества {in, out}.

Определенная подобным образом величина коэффициента необходимости "уточняется" при помощи введенного выше коэффициента динамичности.

С этой целью kdijk предварительно нормализуют:

kdijk = kdijk, если kdijk < 1, и kdijk = Vkj если kj > 1.

Нормализации при помощи выражения (3) подвергаются лишь kdijk для динамических (но не статических) показателей. Затем, в зависимости от степени близости kdijk к 1, определяют поправочный коэффициент к величине kNijk.

В итоге информационная оболочка для некоторого подразделения представляется в виде информационного конуса с определением множеств показателей {а^(т)} и {ajj(out)}.

При этом каждому показателю из указанных множеств ставится в соответствие коэффициент необходимости kNijk. Можно ввести нижнюю границу kNijk (например, 0,5), при превышении которой показатель обязательно включается в Mnin или Ип,^.

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

ЛИТЕРАТУРА

1. Рубан В.Я., Дрогаль Т.Г. Интеграция АСУ на основе баз данных. Киев: Техника, 1988. 191 с.

2. Захаревич В.Г., Астанин А.Г. Проектирование интеллектуального интерфейса "Человек — машина". Ростов-на-Дону: Изв. СКНЦ ВШ, 1990

3. Методика описания состава и характеристик функциональной схемы ИВС на основании характеристик комплекса задач и структуры предприятия. Руководящий технический материал. М: Энергомашиностроение, 1982.

4. Борисов А.И., Крумберг О.А., Федоров И.П. Принятие решений на основе нечетких моделей. Примеры использования. Рига: Зинатне, 1990. 184 с.

УДК 681.3.016.001.63

С.В. Духин

ОЦЕНКА ЭФФЕКТИВНОСТИ СХЕМ БАЗ ДАННЫХ

Оценка эффективности схем баз данных - достаточно сложная и трудноформализуемая задача. Определить, что логическая схема ^1 “является лучшей, чем” схема ^2, может только достаточно опытный разра-

ботчик информационных систем, досконально знающий технологию использования данных этой системы, пользователей информации, перечень запросов, частоту запросов, свойства системы управления базой данных и так далее. Другой разработчик, даже имея в распоряжении ту же информацию, найдет, что схема ¥1 “не является лучшей, чем” схема ¥2, поскольку его понятия о степени важности того или иного критерия эффективности отличны от понятия первого разработчика. Любой пользователь, использующий данные информационной среды, не может быть уверен, что работает с оптимальной схемой, и обоснованно ожидает окончания обработки своих запросов.

Рассмотрим критерии эффективности, предлагаемые исследователями моделей данных для оценки эффективности логических схем.

Согласно [1], с точки зрения пользователя модель данных (а следовательно, и схема как элемент модели) должна удовлетворять следующим требованиям:

- простоты: модель данных должна иметь небольшое число типов структур с непосредственными правилами построения и минимумом атрибутов, которые должен знать пользователь;

- наглядности: модель данных должна быть визуально представимой;

- легкости информационного моделирования: модель данных должна позволять непосредственное моделирование систем реального мира;

- разбиваемости: необходимо, чтобы модель данных предоставляла возможность использования модели данных с сорезидентными моделями;

- независимости: модель данных не должна содержать деталей, связанных с конкретной реализацией.

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

Другая крайняя позиция приведена в [2], где авторы, полагая, что для описания структуры базы данных используется одна из графовых моделей данных, сложность модели данных определяют как тройку чисел:

- логарифм по основанию 2 от произведения числа вершин (выражающих записи) на число дуг (выражающих типы наборов, по определению сетевых структур баз данных РГБД КОДАСИЛ);

- сумма логарифмов по основанию 2 числа дуг, направленных в каждую вершину, т. е. необходимо для каждой вершины подсчитать число дуг, направленных в нее, определить логарифм и просуммировать по всем вершинам;

- среднее число типов полей на один тип записи, т. е. количества типов полей вершин складываются и делятся на количество типов записей.

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

В [3] приводится более комплексный набор критериев эффективности, условно разделенных на две группы: количественные и качественные критерии. К количественным критериям относят оценки, представ-

ляемые в единицах времени и стоимости и являющиеся объективными (т. е. такими, которые можно измерить):

- время отклика на запрос;

- стоимость обновления;

- стоимость памяти;

- время, затраченное на создание;

- стоимость реорганизации.

К качественным критериям относят критерии, выражаемые понятиями “лучше, чем” и “хуже, чем” и являющиеся субъективными оценками:

- гибкость;

- адаптивность;

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

- совместимость с другими системами;

- возможность конвертирования для использования в другой вычислительной среде;

- возможность восстановления/рестарта;

- возможность членения или расширения структуры.

В [4] автор предлагает следующее неформальное определение оценки эффективности модели данных и схемы базы данных. Оценка модели данных определяется ее полезностью с точки зрения формирования взглядов на организацию и использование данных. Полезность модели зависит от степени ее адекватности моделируемой предметной области. При конструировании информационного обеспечения системы обработки данных можно выделить различные уровни моделирования данных, например, соответствующие инфологической и даталогической области исследований. Соответственно определяется и назначение схем, специфицируемых моделями данных. Схема может использоваться исключительно для проектирования и выступать в качестве средства точного выражения его пониманию, т. е. использоваться для инфологической области моделирования. Такая схема называется описанием предметной области. Если схема служит целям автоматизированной обработки, она непосредственно связана с системой управления базами данных (СУБД) и называется описанием схемы базы данных.

Различные модели данных могут использоваться при исследованиях и разработках в области инфологии и даталогии, однако не существует модели (так же, как и языка программирования), которая была бы признана наилучшей при использовании для этих целей, так как в первом случае (в области инфологии) представление информации должно быть ориентировано на человека, а во втором случае (в области датало-гии) - на компьютерную обработку. Наиболее удобен вариант, когда проектировщик располагает различными моделями данных инфологической и даталогической областей, причем выбор пары моделей должен быть произведен таким образом, чтобы инфологическая модель обладала свойством отображаться в даталогическую модель. Если при выборе датало-гической модели мы ограничены в выборе предлагаемыми коммерческими СУБД, поддерживающими ту или иную модель данных, то в отношении инфологической модели проектировщик достаточно свободен в выборе.

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

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

При выборе структуры базы данных выделяются 3 аспекта:

1) представления: некоторые ограничения и конструкции можно рассматривать как естественное отображение свойств объектов реального мира;

2) неизбыточность данных, связей и ограничений;

3) разделение: информационные модели различных объектов должны быть разделены и не пересекаться.

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

Главным недостатком всех рассмотренных критериев эффективности схем баз данных является использование в них понятий самой схемы и игнорирование вопроса о том, зачем эта схема нужна. Между тем одна из основных задач схемы - обеспечение эффективной обработки запросов пользователей. Запрос является гораздо более трудно формализуемым понятием, чем сама схема. Традиционно считается, что запрос может быть выражен конструкциями (или просто понятиями) языка манипулирования данными (ЯМД), а схема - конструкциями языка описания данных (ЯОД). ЯОД и ЯМД являются двумя составляющими реализации модели данных и, как правило, не имеют общих конструкций. Поэтому, как следствие, запрос не может быть представлен в терминах схемы и использоваться при формировании критериев эффективности схемы.

В [2] предлагается рассмотрение любой информационной структуры

— .-V -0^21 -.->«82 -о Бп -г-т

в виде реляционной системы х=<Х, К1 , К2 , ..., Кп >, где X — множе-

ство объектов, - Б1-арный предикат, определенный на множестве X и задающий свойство или взаимосвязь объектов. Модель данных может

быть определена как набор типов отношений {К1Б1, И282, ..., Ип8п} с множеством ограничений на взаимосвязь этих типов. Под типом отношения

понимается множество отношений {И1Я}, удовлетворяющих указанным ограничениям. Ограничения есть формулы языка исчисления предикатов. Используя такой математический аппарат, авторы [2] оценивают эффективность использования модели данных для представления логической схемы и доказывают возможность представления любой логической схемы в виде реляционной системы X. Но очевидно, что приведенное определение реляционной системы очень похоже на определение гиперграфа [5] И=(Л,0,Р), где А - множество вершин (или атрибутов) Л={Л1, А2, ..., Ап}, совпадает с X; 0 — множество ребер (или отношений), 0={И1, И2, ..., Ит}, Р — предикат, определяющий принадлежность конкретной вершины Л1 конкретному ребру И]' (принадлежность атрибута Х1 конкретному отношению К'8'). Такое упрощенное представление реляцион-

ной схемы корректно в том случае, если мы не собираемся рассматривать с помощью него вопросы, касающиеся нормализации. Кроме того, представление схемы реляционной базы данных дает возможности так же просто построить расширение схемы (или экстенсионал), включающее вершины, соответствующие значению атрибутов. Однако для рассмотрения оценки эффективности схемы удобно воспользоваться именно таким представлением. Воспользовавшись определением запроса, данным в [6], представим запрос на поиск информации также в виде обобщенного гиперграфа Z=SuC, представляющего объединение двух гиперграфов: S=(AS,0S,PS) - гиперграфа логической схемы результата запроса и

C=(AC,0C,PC) - гиперграфа логической схемы условия запроса.

S S S

Множество AS={Al , A2 , ..., An } представляет собой множество

S

атрибутов логической схемы результата запроса, а множество AS={Al , SS

A2 , ..., An } — множество атрибутов логической схемы условия запроса, ASuA и AcuA.

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

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

ЛИТЕРАТУРА

1. McGee V.C. One user criteria for data model evaluation. ACM Transactions on Database Systems, 1976, vol. 1, № 4, p. 370—387.

2. Логическое управление информационными процессами / Горбатов В.А., Павлов П.Г., Четвериков В.Н. Под ред. В.А. Горбатова. М.: Энергоатомиздат, 1984.

3. Тиори Т., Фрай Дж. Проектирование структур баз данных: в 2-х кн. / Пер. с англ. М.: Мир, 1985.

4. Цикритзис Д., Лоховски Ф. Модели данных / Пер. с англ. М.: Финансы и статистика, 1985.

5. Мелихов А.Н., Берштейн Л.С. Гиперграфы в автоматизации проектирования дискретных устройств. Росстов-на-Дону. Изд-во РГУ, 1981.

6. Мицук Н.В. Алгебраическая модель структур данных и теория информационного поиска. // Методы автоматизации проектирования, программирования и моделирования. Таганрог.: ТРТИ, 1981. Вып. 1. С. 18—27.