Projection of the memory size necessary for implementation of supertype-subtype relations.pdf 1. Способы представления категорированных отношенийВ базах данных (БД) информационных систем значительная часть данных свя-зана отношениями категоризации.Наиболее развиты способы реализации категорированных отношений в СУБДOracle. Варианты СУБД Oracle охватывают практически все возможные вариантыдругих СУБД, поэтому они приняты за основу при разработке аналитического ме-тода оценки объемов памяти, необходимых для реализации категорированных от-ношений в реляционных БД. В многотомном описании методологии проектиро-вания Oracle [1, с. 71−76.] приведены только словесные описания вариантов реа-лизации с кратким перечнем достоинств и недостатков каждого.На рис. 1 показана модель отношения категоризации по нотации Баркера («су-пертип» - «тип»).Сущности категории «Общая сущность «супертип» тип»Атрибуты общей сущности Атрибуты сущностей категорийC# C1o C2B# B1o B2А# A1o A2Рис. 1. Базовая ER-диаграммаКатегорированные данные могут быть представлены (рис. 2):- в одной таблице (вариант а);- в нескольких (по количеству категорий) таблицах (вариант б);- в нескольких (по количеству категорий + одна) таблицах (варианты в, г).A(#)#*A1*A_TYPEoA2oB1oB2oC1oC2вариант аB(#)#*A1*B1oA2oB2…С(#)#*A1*С1oС2oА2вариант бА(#)#*A1oA2B(#)#*A1*B1oA2oB2 …C(#)#*A1*C1oC2oA2вариант в…B(#)#*B1oB2вариант гА(#)#*A1oA2o B_B1o C_C1C(#)#*C1oC2Рис. 2. Варианты реализации категорированных отношений2. Аналитический метод оценки различий в требуемых ресурсах памятиБД вариантов представления категорированных отношенийВведем обозначения: N − число записей в БД; Nmax − максимально возможноечисло записей в БД; Kу.и − размер уникального идентификатора; Aо.а − размер об-щих атрибутов; Kк − число категорий; Ai − размер частных атрибутов (для катего-рии i); Ni − число записей категории i; Nimax − максимально возможное число запи-сей категории i; Kу.иi − размер уникального идентификатора для категории i.Должны выполняться следующие неравенства:Kу.и >= log2 Nmax ; Kу.иi >= log2 Nimax , (1)однако на практике для уникальных идентификаторов записей используют деся-тичные числа, поэтому имеемKу.и >= lg Nmax ; Kу.иi >= lg Nimax . (2)Кроме того,1kkiiN N=ƒ =. (3)Пределы суммирования во всех формулах данной статьи одинаковы, поэтомуниже они не указываются (вместо1kki= ƒ используется ƒ).В некоторых упрощениях (при несущественном влиянии на результат) прини-мается также, что Kу.иi = Kу.и.Объем памяти по варианту а − Оа (без учета несущественного по объему атри-бута TYPE):Оа = N(Kу.и + Aо.а + ƒ Ai). (4)Объем по варианту б − (Об):Об = ƒ Ni(Kу.и + Aо.а + Ai). (5)Объем по варианту в − (Ов):Ов = N(Kу.и + Aо.а)+ ƒ Ni(Kу.и + Aо.а + Ai). (6)Объем по варианту г − (Ог):Ог = N(Kу.и + Aо.а + ƒ Kу.иi)+ ƒ Ni(Kу.иi + Ai). (7)Для анализа эффективности различных вариантов представления категориро-ванных отношений в реляционных БД представляют интерес:- относительные оценки: (Оа - Об)/ Оа; (Оа - Ов)/ Оа ; (Оа - Ог)/ Оа;- абсолютные оценки: Оа; Оа - Об; Оа - Ов; Оа - Ог.С учетом формул (1) - (7):(Оа - Об)/Оа={N(Kу.и+Aо.а+ ƒAi) - ƒNi(Kу.и+Aо.а+Ai)}/N(Kу.и+Aо.а+ ƒAi); (8)(Оа - Ов)/Оа={N(Kу.и+Aо.а+ ƒ Ai) - [N(Kу.и +Aо.а)+ ƒ Ni(Kу.и + Aо.а+ Ai)]}//N(Kу.и + Aо.а+ ƒ Ai); (9)(Оа - Ог)/Оа={N(Kу.и+Aо.а+ ƒ Ai) - [N(Kу.и + Aо.а+ ƒ Kу.иi) + ƒ Ni(Kу.и + Ai)]}//N(Kу.и + Aо.а + ƒ Ai). (10)После преобразований, с учетом формул (2), (3) и некоторых приближений:(Оа - Об)/Оа=Aо.а[ƒAi/Aо.а - ƒ (Ni/N)(Ai/Aо.а)]/[Aо.а(1+ ƒAi/Aо.а)+lgNmax]; (11)Оа - Об=NAо.а[ƒAi/Aо.а - ƒ(Ni/N)(Ai/Aо.а)]; (12)Оа - Ов)/Оа = {Aо.а[ƒAi/Aо.а - 1 - ƒ(Ni/N)(Ai/Aо.а)] - lgNmax}//[Aо.а(1+ ƒAi/Aо.а)+lgNmax]; (13)Оа - Ов = N{Aо.а[ƒAi/Aо.а - 1 - ƒ(Ni/N)(Ai/Aо.а)] - lgNmax}; (14)(Оа -Ог)/Оа = {Aо.а[ƒAi/Aо.а-ƒ(Ni/ N)(Ai/Aо.а)]-ƒ lgNimax - lg Nmax }//[Aо.а(1+ƒ Ai/Aо.а) + lgNmax]; (15)(Оа - Ог) = N{Aо.а[ƒ Ai/Aо.а - ƒ (Ni/ N)(Ai/Aо.а)] - ƒ lg Nimax - lg Nmax}; (16)Оа = N[ Aо.а(1 + ƒ Ai/Aо.а) + lg Nmax]; (17)Об = N[Aо.а{1 + ƒ (Ni/ N)(Ai/Aо.а)} + lg Nmax]; (18)Ов = N[Aо.а {2 + ƒ (Ni/ N)(Ai/Aо.а)} + 2lg Nmax ]; (19)Ог = N[Aо.а {1 + ƒ (Ni/ N)(Ai/Aо.а)}+ ƒ lg Nimax + 2lgNmax ]. (20)Выражения (11) - (16) могут быть использованы для проведения исследованийи анализа эффективности различных вариантов представления категорированныхотношений в реляционных БД [2, с. 86−87].3. Модель базы категорированных данныхСледует обратить внимание на набор компонентов выражений (11) - (20):{N; Nmax; Nimax; Aо.а; ƒ Ai/Aо.а; ƒ (Ni/ N)(Ai/Aо.а) }.Эти компоненты достаточно адекватно представляют реальную БД и особен-ности структуры данных.Введем обозначения: ai = Ai/Aо.а; ni = Ni/N и преобразуем формулы (11) - ( 20):(Оа - Об)/ Оа = Aо.а(ƒai - ƒni ai)/[ Aо.а(1 + ƒai ) + lg Nmax]; (21)Оа - Об = NAо.а(ƒai - ƒ ni ai); (22)(Оа - Ов)/Оа=[Aо.а(ƒ ai - 1 - ƒ ni ai) - lg Nmax ]/[Aо.а(1+ ƒ ai)+lg Nmax]; (23)Оа - Ов = N[Aо.а (ƒai - 1 - ƒ ni ai) - lg Nmax]; (24)(Оа - Ог)/Оа=[Aо.а(ƒ ai - ƒ niai) - ƒ lgNimax - lgNmax]/[Aо.а(1+ ƒ ai+lgNmax)]; (25)(Оа - Ог)=N[Aо.а(ƒai - ƒni ai) - ƒlg Nimax - lg Nmax]; (26)Оа= N[Aо.а(1 + ƒ ai) + lg Nmax]; (27)Об = N[Aо.а(1 + ƒ ni ai) + lg Nmax]; (28)Ов = N[Aо.а (2 + ƒ ni ai) + 2lg Nmax ]; (29)Ог = N[Aо.а (1 + ƒ ni ai )+ ƒ lg Nimax + 2lg Nmax]. (30)Формулы (21) − (30) положены в основу аналитического метода оценки тре-буемых объемов памяти по вариантам представления категорированных отноше-ний.Целесообразно использовать набор { N; Nmax; |Nimax|; Aо.а; |ai |; |ni| } как модельбазы категорированных данных для исследований зависимостей объемов памяти,необходимых для реализации категорированных отношений.Замечание. Если ƒai имеет простой «физический» смысл (эта сумма показыва-ет соотношение между суммарными размерами общих и частных атрибутов), то скомпонентом ƒniai несколько сложнее. Диапазон значений ƒniai: − 0 < ƒ niai < ƒai .Если значения ƒniai в левой части диапазона (от 0,5 ƒai к 0), то в БД незначительнадоля записей, относящихся к категориям, имеющим существенные размеры част-ных атрибутов, и, наоборот, существенна доля записей, относящихся к категори-ям, имеющим незначительные размеры частных атрибутов. Если значения ƒ ni ai вправой части диапазона (от 0,5 ƒai к ƒai), то в БД значительна доля записей, отно-сящихся к категориям, имеющим существенные размеры частных атрибутов, и,наоборот, несущественна доля записей, относящихся к категориям, имеющим не-значительные размеры частных атрибутов.4. Зависимости затрат памяти от параметров моделибазы категорированных данныхНекоторые зависимости затрат памяти, полученные по выражениям (21)-(30),приведены на диаграммах (рис. 3, 4).(О - О а i)/Оа, %2 4 6 880706050403020100Зависимость затрат памяти от структуры категорированных записей ( )( = 500 000; = 10; lg = 6; = 512 симв.)a nN a N Ai iƒ i max o.aƒƒa n i i(Оа - Об)/Оа(Оа - Ов)/Оа(Оа - Ог)/ОаРис. 3. Уменьшение (экономия) ресурсов памяти при переходе от вариантапредставления категорированных данных а к вариантам б, в, г в зависимостиот структуры категорированных данных (ƒaini) в БД0,5 1 5 106040200-20-40-60Зависимость затрат памяти от соотношения общих и частных атрибутов ( )(ƒniai = 0,5ƒai; = 500 000; lg Nmax = 6; Ao.a = 512 симв.)ƒaiNƒai(Оа - Оi)/Оа, %(Оа - Об)/Оа(Оа - Ов)/Оа(Оа - Ог)/ОаРис. 4. Уменьшение (экономия) ресурсов памяти при переходеПолученные с помощью аналитических выражений данные показывают по-тенциальные возможности минимизации затрат ресурсов памяти с помощью вы-бора вариантов представления категорированных данных. В предельных случаяхресурсы памяти, необходимые для реализации категорированных данных, могутбыть сокращены на 60 − 70 %.5. Имитационная программа для уточнения аналитических выраженийметода оценки требуемых ресурсов памятиВ аналитических выражениях метода оценки объемов памяти (разделы 2, 3)единицей измерения объема памяти является символ данных, заносимых в базуданных − Sд. Такой выбор удобен для определения параметров модели категори-рованных данных по анализу информационных моделей. В то же время при оцен-ке затрат ресурсов памяти общепринятыми являются единицы измерения: бит,кбит, Мбит и Гбит.Помимо этого, в ЭВМ и в СУБД используются методы сжатия данных. Призаписи таких типов данных, как числовые, несмотря на то, что отдельным атрибу-там (в СУБД) резервируется определенные максимально возможные значения,нулевые значения слева от значащих символов числа не записываются и не со-храняются в памяти ЭВМ. Как правило, не заносятся (и не требуют ресурсов па-мяти) пустые значения атрибутов.Современные СУБД обладают развитыми средствами повышения производи-тельности баз данных. Ряд методов повышения производительности достигают засчет избыточного хранения данных (напрр, методы индексации записей в таб-лицах БД).Для практического применения аналитических выражений (21) - (30) необхо-димо определить коэффициент перевода единиц измерения, учета сжатия и избы-точности данных − kес размерностью бит/символ данных. При этом оценки (в еди-ницах измерения − бит) необходимых затрат ресурсов памяти для реализации раз-личных вариантов представления категорированных отношений:Оабит = kеса Оа; Оббит = kесб Об; Овбит = kесв Ов; Огбит = kесг Ог.Для перевода единиц измерения необходимо учитывать особенности кодиро-вания символов данных - Sд. Каждый символ данных представляется обычно де-сятичным или шестнадцатеричным кодом, содержащим несколько символов(символов кода − Sк). Наиболее употребительным является стандарт ASCII(American Standard Code for Information Interchange, стандарт ANSI − американ-ского национального института стандартов). Часто используемая для передачиданных американская версия семибитовой кодировки символов кода (Sк) утвер-ждена ISO. Восьмой бит символа кода ASCII обычно яется битом контролячетности (паритета). Таким образом, одним из компонентов kес является коэффи-циент (nSк) двоичного представления символа кода Sк. Для ASCII nSк = 8(бит/символ); nSк = 1 (байт/символ); nSк = 1/1024 (кбайт/символ) и т.д.На ПК используется так называемый расширенный код ASCII, в котором пер-вые 128 комбинаций совпадают со стандартным, а остальные используются дляпредставления национальных алфавитов, псевдографики и специальных знаков.Кодировка символов данных отличается количеством знаков кода (NSк). Напри-мер, цифры и большая часть латинских символов кодируются двумя десятичнымизнаками (NSк = 2), а символы кириллицы - тремя (NSк = 3). Необходимый дляпредставления данных объем памяти зависит от набора символов, необходимогодля определенного типа данных, заносимых в базу данных. В первом приближе-нии может быть принято, что набор символов данных носит случайный характер,и этот набор может быть представлен математическим ожиданием значения числасимволов кода − NSк . По стандарту ASCII для большинства наборов символовзначение NSк будет находиться в диапазоне от 2 до 3.Таким же образом может быть признана случайной величина коэффициентаучета сжатия (kсж) данных при записи в ЭВМ (при записи данных сжатие прово-дится только по отдельным атрибутам, и степень сжатия различна). Фактор сжа-тия данных должен приводить к уменьшению kес. При сжатии данных, например в1,5 - 2 раза, общая оценка kес должна находиться в диапазоне от 1 до 2 (при изме-рении в единицах байт/символ).Избыточность данных, прежде всего при использовании индексирования запи-сей, также может быть учтена коэффициентом (kи.д). При индексировании записейСУБД может создавать дополнительные колонки, с помощью которых упорядо-чиваются записи. В связи с этим введение kи.д адекватно отражает изменения втребуемых ресурсах памяти.С учетом представления коэффициента сжатия средним значением общий видkес:kес = kсж kи.д nSк NSк.Значения nSк и kи.д могут быть определены при достаточно тщательном анализеконкретных вариантов реализаций фрагментов БД с категорированными данны-ми. Аналитически определить kсж и NSк гораздо сложнее. Предлагается использо-вать для оценки kес имитационную программу без детального анализа составляю-щих kес. Программа представляет собой тестовую базу данных со структурой, со-ответствующей исследуемой структуре категорованных данных (соотношениеобщих и частных атрибутов, в соответствии с моделью категорированных данных,раздел 3) и вариантам представления категорированных отношений.Шаги процедуры определения значения kес:- внесение набора числа тестовых записей (ряд значений N) и фиксация затрат (в би-тах) ресурсов памяти − Оаимит (N); Обимит (N); Овимит (N); Огимит(N);- расчет затрат ресурсов по выражениям (27) - (30) в символах (Sд) для каждо-го значения из ряда N − Оа(N); Об(N); Ов(N); Ог(N);- расчет kес для каждого Ni:kеса(N) = Оаимит (N)/ Оа(N); kесб(N) = Обимит (N) / Об(N);kесв(N) = Овимит 0Up(N) / Ов(N); kесг(N) = Огимит (N) / Ог(N);- определение среднего значения kеса; kесб; kесв; kесг;- построение зависимостей Оабит Оббит Овбит Огбит.Использование оценки на основе среднего значения (kес), получаемого по дан-ным имитационной программы, позволяет получить аналитические выражения,отличающиеся от данных имитационной программы на 3 - 5 %, что вполне до-пустимо для использования их для оценок затрат ресурсов при проектированииреальных базах данных.Величина kес(N) при различных значениях N и вариантах структуры категори-рованных данных находилась в пределах от 0,8 до 3,2 (оценка диапазона при ана-лизе факторов, влияющих на kес(N), − от 1 до 2). Расширение диапазона влевоможно объяснить тем, что при малом числе записей более существенно влияетфактор сжатия данных при записи в БД (например, для значений уникальных ат-рибутов достаточно одного-двух символов вместо lg Nmax). Расширение диапазонавправо до значения kес(N) = 3,2 также объяснимо. Часть тестовых данных исполь-зовалась на текстовых фрагментах, содержащих только символы кириллицы, ко-торые представляются тремя символами кода по ASCII. Кроме того, дополни-тельные затраты ресурсов памяти связаны с индексацией первичных ключей.ЗаключениеОценить различия в объеме памяти БД вариантов представления категориро-ванных отношений возможно аналитическими расчетами. Аналитические выра-жения определяют зависимости требуемых объемов памяти от параметров струк-туры категорированных данных для наиболее распространенных на практике ва-риантов представления категорированных отношений.В аналитической модели должны быть учтены особенности структуры катего-рированных данных. Модель особенностей категорированных данных использу-ется в аналитических выражениях метода оценки различий в объеме памяти БДвариантов представления категорированных отношений. Представление модельюреальных баз категорированных данных распространяет конкретные аналитиче-ские выражения метода на группу баз категорированных данных и сокращает за-траты на моделирование.Уточнить аналитические выражения метода оценки требуемых ресурсов памя-ти можно с помощью имитационной программы. Программа обеспечивает про-верку достоверности аналитических выражений метода. Данные, получаемыеимитационной программой, используются для определения коэффициента учетасжатия данных в СУБД, особенностей кодирования символов и дополнительныхзатрат ресурсов памяти при использовании в СУБД, например избыточных мето-дов повышения производительности.

Скачать электронную версию публикации