Головна   Додати в закладки Розробка та аналіз оптимальних моделей багаторівневих індексно-послідовних | Реферат


Безкоштовні Реферати, курсові, дипломи - referatbank.com.ua Безкоштовні Реферати, курсові, дипломи - referatbank.com.ua | Реферат банк.
 Пошук: 

 

 




Розробка та аналіз оптимальних моделей багаторівневих індексно-послідовних - Реферат


Категорія: Реферати
Розділ: Комп`ютерні науки
Розмір файла: 40 Kb
Кількість завантажень:
1
Кількість переглядів:
583
Описання роботи: Реферат на тему Розробка та аналіз оптимальних моделей багаторівневих індексно-послідовних
Дивитись
Завантажити


Міністерство освіти і науки України

Львівський національний університет ім. І. Франка

Факультет прикладної математики та інформатики

Кафедра теорії оптимальних процесів

Дипломна робота

Розробка та аналіз оптимальних моделей багаторівневих індексно-послідовних файлів

Виконав:

студент групи ПМа-53м

Прізвище Ім’я

Науковий керівник:

доц. Прізвище І.П.

Робота заслухана на засіданні

кафедри теорії оптимальних процесів

і рекомендовано до захисту.

Протокол № від 2010р.

Завідувач кафедри проф. Бартіш М. Я.

Львів 2010

Зміст

Вступ. 3

Розділ I. Основні поняття та особливості поставленої задачі 3

1.1. Постановка задачі 3

1.2. Теоретична частина. 3

1.3. Типові розподіли ймовірностей звертання до записів файлів бази даних. 3

Розділ II. Оптимальні моделі багаторівневих індексно-послідовних файлів. 3

2.1. Оптимальні моделі дворівневих індексно-послідовних файлів. 3

2.2. Оптимальні моделі багаторівневих індексно-послідовних файлів. 3

Розділ III. Практична частина. 3

3.1. Розігрування випадкових величин. 3

3.2. Порівняльний аналіз. 3

Висновок. 3

Список використаної літератури. 3

Вступ

Для збереження записів у базах даних широко застосовують індексні файли, зокрема найчастіше їх підвид – індексно-послідовні файли. Ідея такого збереження наступна. Нехай фізичні записи файлу даних зберігаються в логічній послідовності, скажімо впорядковано за зростанням основного ключа. Тоді для локалізації запису не варто здійснювати пошук у всьому файлі, можна якимось іншим способом знайти дрібнішу область, що містить шуканий запис і пошук вести лише в цій області. Зазвичай для визначення такої невеликої області (блоку записів) складають спеціальну таблицю, котру називають індексом. Індекс складається з послідовності записів, кожен з яких містить найбільше значення ключа в межах блоку записів і вказівник на цей блок.

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

На малюнку зображено індексно-послідовний файл з одним рівнем індексної частини.

Рис. 1 - Загальна структура однорівневого індексно-послідовного файлу

Де – елементи індексу, – елементи файлу даних, – вказівники на початок індексної частини та частини з даними, – часи переходу між елементами індексу та записами в базі даних, – час переходу від елементів індексу до блоку, на котрий вони вказують.

Якщо для адресації файлу використовується індекс (в більшості випадків він чи його частина може знаходитися в основній пам’яті), то попередній пошук в індексі, а не файлі, суттєво економить час, що необхідний для локалізації запису файлу.

При роботі з великим файлами індекс часто виявляється надто великим для пошуку. В такому разі елементи індексу теж групують в блоки, котрі теж можна індексувати. Великі файли містять два і більше рівнів індексу.

На малюнку зображено індексно-послідовний файл з двома рівнями індексу. Взагалі кажучи їх може бути більше.

Рис. 2 - Загальна структура дворівневого індексно-послідовного файлу

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

Розділ I. Основні поняття та особливості поставленої задачі

1.1. Постановка задачі

В реальних задачах ми нечасто маємо справу з надходженням вимог рівномірно. Частіше має місце надходження вимог за певними законами розподілу ймовірностей.

Поставимо задачу дослідити середній час пошуку інформації для кожного з варіантів розподілу ймовірностей. Дослідити оптимальні розбиття інформації на блоки за цих умов. За критерій оптимальності візьмемо величину середнього часу пошуку (математичне сподівання), а точніше поставимо собі задачу мінімізувати його.

Розглядається побудова та аналіз оптимальних стратегій різних варіантів пошуку інформації в послідовних файлах, що містяться в зовнішній пам"яті ЕОМ, для різних законів розподілу ймовірностей звертання до записів.

Серед законів розподілу ймовірностей звертання до записів розглядаються:

· рівномірний, розподіл

· «бінарний» розподіл,

· закон Зіпфа

· узагальнений розподіл (частковим випадком якого є правило "80-20").

1.2. Теоретична частина

В цьому розділі ми розглянемо необхідні нам для практичної роботи теоретичні матеріали. Поставимо задачу дослідити середній час пошуку інформації для кожного з варіантів розподілу ймовірностей. Дослідити оптимальні розбиття інформації на блоки за цих умов. За критерій оптимальності візьмемо величину середнього часу пошуку (математичне сподівання), а точніше поставимо собі задачу мінімізувати його.

Для мінімізації математичного сподівання розробимо теоретичний механізм диференціювання з застосуванням ЕОМ, механізм отримання випадкової змінної з довільного закону розподілу (т.з. операція «розігрування змінної»).

Виведемо потрібні формули для оптимальних параметрів розбиття файлу та індексу на блоки, для більших розмірностей виведемо системи рівнянь для отримання цих параметрів. Самі системи розв’язано не буде, так як це є окремою задачею, взагалі кажучи складною, особливо у випадку нелінійних рівнянь.

Серед законів розподілу ймовірностей звертання до записів розглядаються:

· рівномірний, розподіл

· «бінарний» розподіл,

· закон Зіпфа

· узагальнений розподіл (частковим випадком якого є правило "80-20").

1.3. Типові розподіли ймовірностей звертання до записів файлів бази даних

Розглянемо детальніше кожен з законів розподілу, наведемо основну інформацію про їх властивості та функції розподілу, котрі будуть нам потрібні для обрахунку ймовірностей.

1. Рівномірний розподіл

Характеризується однаковою імовірністю отримання будь якого елементу з відрізку. Імовірність залежить лише від довжини самого відрізку. На зображенні бачимо функцію розподілу ймовірності для рівномірного розподілу.

Функція розподілу

Рис. 3 Функція розподілу ймовірності для рівномірного розподілу

2. Бінарний розподіл

Бінарний закон демонструє нам степеневе спадання імовірності:

Інтегруючи цю функцію можемо отримати і відповідну функцію розподілу.

3. Закон Зіпфа

Емпірична закономірність розподілу частоти слів мови: якщо всі слова мови (або просто досить довгого тексту) посортувати за порядком спаданням частоти їх використання, то частота n-го слова в такому списку приблизно пропорційна його порядковому номеру n (так званому рангом цього слова). Наприклад друге за використовуванням слово зустрічається приблизно у два рази рідше, ніж перше, третє - у три рази рідше, ніж перше, і т. д.

Імовірність .

Тут є параметром, залежно від його значення ми отримаємо різні закони розподілу.

Функція розподілу:

Зазначимо, що рівномірний розподіл (при ) і закон «80-20» (при ) є частинними випадками розподілу Зіпфа. На малюнку бачимо функцію розподілу ймовірності для розподілу Зіпфа при різних параметрах s рівномірного розподілу.

Рис. 4 Функція розподілу для закону Зіпфа

Розділ II. Оптимальні моделі багаторівневих індексно-послідовних файлів

1.

2.

2.1. Оптимальні моделі дворівневих індексно-послідовних файлів

Розглянемо дворівневий індексно-послідовний файл. Нехай кількість записів файлу, кількість елементів індексу ого рівня, час доступу до індексу ого рівня, час доступу до блоку записів файлу, - час, що потрібен для перегляду одного запису файлу. Зазначимо, що це значення може бути різним залежно від того в якій пам’яті здійснюється перегляд записів. Позначимо через відповідно розміри індексу другого рівня, блоку елементів індексу першого рівня і блоку записів файлу. Припустимо, що , для порівняльного аналізу це нічого не змінить, а розрахунки спростяться суттєво.

Будемо вважати, що увесь індекс і файл знаходяться у зовнішній пам’яті і порядок пошуку запису в файлі наступний: спочатку в основну пам’ять зчитується індекс першого другого рівня і в ньому шукається елемент-вказівник на блок елементів індексу першого рівня, в якому міститься значення ключа шуканого запису. Далі в основну пам’ять зчитується знайдений блок елементів індексу першого рівня і в ньому шукається елемент, що містить вказівник на блок записів, в якому міститься шуканий запис. Нарешті, в знайденому блоці методом послідовного перегляду знаходиться шукана інформація. При цьому елементи блоку зчитуються в основну пам’ять або ж пошук здійснюється без попереднього зчитування.

Розглянемо спосіб пошуку, коли до першого та другого рівнів індексу застосовується метод послідовного перегляду і потрібний блок записів файлу зчитується в основну пам’ять. Тоді загальний середній час пошуку при рівномірному розподілі імовірності звертання виразиться формулою:

Для мінімізації цього виразу ми візьмемо частинні похідні по параметрах , прирівняємо їх до нуля, розв’яжемо отриману систему рівнянь і отримаємо:

Якщо ж в індексі першого та другого рівнів використовується метод послідовного перегляду, але потрібний блок не зчитується в основну пам’ять, тоді загальний середній час пошуку при рівномірному розподілі імовірності звертання шукається як:

У випадку нерівномірного розподілу ймовірностей звертань ми розглянемо узагальнений закон Зіпфа . Тоді при використовуванні в індексі методу послідовного перегляду математичне сподівання загального часу, потрібного на пошук запису в файлі визначимо за формулою

Розіб’ємо цей вираз на кілька сум і мінімізуємо кожну з них:

Враховуючи, що , отримаємо

, де

Диференціюючи відповідну суму цих виразів по і ми отримаємо систему рівнянь для їх знаходження:

Отож ми розглянули оптимальні моделі дворівневих індексно-послідовних файлів і вивели параметри, при яких час пошуку відповідного запису сягатиме мінімуму. Як бачимо, формули не завжди є легкими для обрахунків, для складніших законів розподілу ймовірностей доступу доводиться навіть розв’язувати підзадачу вирішення системи рівнянь, в загальному випадку нелінійної.

2.2. Оптимальні моделі багаторівневих індексно-послідовних файлів

Розглянутий спосіб визначення загального середнього часу пошуку запису в дворівневому індексному-послідовному файлі можна перенести на довільні - рівневі файли з однаковим розміром блоків на кожному рівні.

Нехай - час перегдяу елементів індексу на -ому рівні; – час перегляду запису файлу; – число елементів індексу на -ому рівні; - час переходу від -ого рівня індексу до -ого; - час доступу до блоку записів файлу з першого рівня індексу; - час доступу до -ого рівня індексу;

Оскільки розмір блоків на кожному рівні -рівневого індексно-послідовного файлу є однаковим, то на -ому рівні індекс містить блоки розміром , де . Сам файл розбитий на блоки записів, по записів в кожному, де .

Розглянемо ситуацію з рівномірним розподілом імовірності звертань до записів. Нехай весь індекс і файл знаходяться у зовнішній пам’яті. Подамо величини у вигляді

де деякі сталі величини, що залежать від типу зовнішньої пам’яті, на котрій зберігається -ий рівень індексу, і довжини елементів індексу; - сталі, що залежать від типу зовнішньої пам’яті, в котрій зберігається файл і довжини записів файлу.

Розглянемо кілька моделей оптимальної організації - рівневих індексно-послідовних файлів залежно від використаного методу пошуку елементу в індексі і організації процесу пошуку запису в блоці.

Якщо в індексі та файлі застосовується метод послідовного перегляду і потрібний блок зчитується в основну пам’ять, то загальний середній час пошуку запису в файлі

Прирівнючи частинні похідні до нуля, отримаємо відповідну систему рівнянь, з якої знайдемо вираз для :

Якщо час доступу до блоків індексу і блоку записів вважати постійним, то вираз для середнього часу пошуку спроститься

і, відповідно, параметри за яких вона сягає мінімуму теж:

Якщо в індексі і файлі використовується метод послідовного перегляду, але потрібний блок не зчитується в основну пам’ять, то

і відповідно параметри точки мінімуму:

Розглянемо тепер узагальнений випадок розподілу ймовірностей. Позначимо ймовірність звертання до -ого запису файлу. В індексі і файлі для спрощення застосуємо метод послідовного перегляду. Вважатимемо, що час доступу до блоків індексу і блоків запису файлу рівне нулю. На порівняльний аналіз таке спрощення не матиме жодного впливу. Тоді математичне сподівання загального часу пошуку запису в файлі:

Знайдемо значення для конкретних розподілів ймовірностей звертання і визначимо значення параметрів при яких математичне сподівання сягає мінімуму. Для цього подамо у вигляді

Нехай імовірності звертання до записів задовольняють «бінарному» розподілу, тобто

для де

.

Провівши необхідні спрощення матимемо

Узявши частинні похідні і прирівнявши їх до нуля отримаємо цікавий результат: при частинні похідні від функції математичного сподівання завжди додатні. Тому при розглянутих значеннях функція математичного сподівання сягає мінімуму в точці . Звідси слідує, що оптимальний розмір блоків на кожному рівні крім останнього рівний 2.

Якщо імовірності розподіляються за котримсь з варіантів узагальненого розподілу Зіпфа, то

Позначимо

тоді для

таким чином загальне математичне сподівання

Тут нам потрібно розглянути два випадки – (закон Зіпфа) і (закон 80-20).

Нехай , тоді для визначення параметрів ми матимемо наступну систему:

Нехай , тоді для визначення параметрів ми матимемо наступну систему:

Отож ми розглянули оптимальні моделі багаторівневих індексно-послідовних файлів і вивели параметри, при яких час пошуку відповідного запису сягатиме мінімуму. Як бачимо, формули не завжди є легкими для обрахунків, для складніших законів розподілу ймовірностей доступу доводиться навіть розв’язувати підзадачу вирішення системи рівнянь, можливо високої розмірності, в загальному випадку нелінійної.

Розділ III. Практична частина

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

З функціональної точки зору на вхід програми буде надходити кількість записів у файлі і закон розподілу ймовірностей запитів (один з розглянутих чотирьох). На виході ми отримаємо набір даних про кількість рівнів у файлі і відповідне цій кількості рівнів розбиття файлу даних на блоки. Присутній також порівняльний графік середнього часу пошуку залежно від кількості рівнів у файлі і відповідної кількості рівнів кількості блоків основного файлу.

Зауважимо, що в програмі ми розглянемо лише дво- і три рівневі файли, так як для більшої кількості рівнів задача розв’язування системи рівнянь є складною і потребує окремого вивчення.

1.

2.

3.

3.1. Розігрування випадкових величин

Бачимо, що в кожній формулі математичного сподівання присутні ймовірності звертання до кожного конкретного елемента даних. У нас є закони розподілу випадкових величин, ми можемо згенерувати потрібні нам імовірності за допомогою підзадачі розігрування випадкових величин.

Нехай безперервна випадкова величина задана своїм законом розподілу:

, де - щільність розподілу ймовірностей, а - функція розподілу ймовірностей. В прикладній статистиці доведено, що випадкова величина

розподілена рівномірно на інтервалі (0,1).

Звідси випливає, що шукане значення y може бути визначене з рівняння:

що еквівалентно рівнянню:

де y - значення випадкової величини . Рішення рівняння можна записати в загальному вигляді через зворотну функцію :

Основний недолік методу полягає в тому, що інтеграл не завжди є таким, що береться, а рівняння не завжди вирішується аналітичними методами. В наших дослідженнях ми скористаємось методом Гауса третього прядку для апроксимації інтегралу.

Ми згенеруємо послідовність випадкових чисел, отриманих методом зчитування з комп’ютерних датчиків. Така послідовність згідно технічної документації є нормально розподіленою. Нашим завданням буде “розіграти” цю послідовність, тобто отримати з неї послідовності, розподілені за потрібними нам законами. Цього ми досягнемо знайшовши верхню межу інтегралу , де змінна з нормально розподіленої послідовності випадкових чисел. Підінтегральну функцію ми апроксимуємо квадратурною формулою Гауса. Отримана послідовність буде розподіленою за потрібним нам законом, якщо функція буде функцією густини відповідного закону розподілу. Вхідну послідовність ми згенеруємо вище згаданим алгоритмом.

Наведемо тут найважливіші технічні моменти програми.

1. Розігрування послідовності нормально розподілених випадкових чисел

ArrayList play(ArrayList randoms)

{

ArrayList res = new ArrayList(randoms.Count);

for (int i = 0; i < randoms.Count; i++)

{

res.Add(this.gauss((double)randoms[i]));

}

return res;

}

2. Підпрограма знаходження верхньої межі підінтегральної функції методом Гауса третього порядку

double gauss(double square)

{

double step = 0.001;

double a = 0;

double tmp_square = 0;

do

{

tmp_square += (step / 2) * (this.density (((a + a + step) / 2) - (step / (2 * Math.Sqrt(3)))) + this.density(((a + a + step) / 2) + (step / (2 * Math.Sqrt(3)))));

a += step;

}

while (Math.Abs(square - tmp_square) > 0.01);

return a;

}

Тут this.density() підпрограма для обчислення значення густини розподілу випадкової величини.

3. Клас-підпрограма для комп’ютерного диференціювання. Можлива конфігурація точності.

// class for numerical differentiation

// http://en.wikipedia.org/wiki/Numerical_differentiation

public class Derivativer

{

double PREC = 0.00001; // precision

Function f; // target function

// calculation of derivative from function f in point x

// partial and high orders are available

public double calc(Vector x, params int[] way)

{

Vector x1 = Vector.Copy(x);

int pos = way[way.Length - 1];

x1[pos] -= this.PREC;

int[] way1 = new int[way.Length - 1];

for (int i = 0; i < way1.Length; i++) way1[i] = way[i];

if (way1.Length != 0)

{

return (this.calc(x, way1) - this.calc(x1, way1)) / this.PREC;

}

else

{

return (this.f(x) - this.f(x1)) / this.PREC;

}

}

// constructor

public Derivativer(Function f) {

this.f = f;

}

}

4. Підпрограма мінімізації багатовимірної нелінійної функції методом Ньютона із змінною довжиною кроку.

// found extremum of function with Newton method

// http://en.wikipedia.org/wiki/Newton%27s_method_in_optimization

public class Extremum_Searcher

{

Function func; // target function

Vector result; // result

Array process; // whole iterative process will be here (history)

int funcDim; // dimension of researched function

double iterStep = 1; // step in Newton formula

public bool recalcIterStep = false; // should we recalculate iterative step?

public int frequencyCount = 1; // after each value we shoud recalc Hesse matrix

public double precision = 0.000000001;

// get all history of founding extremum process

public Array getHistory() {

return this.process;

}

// check whether founded extremum is maximum

public bool isMaximum() {

Hessian hes = new Hessian(this.func);

Gradient gr = new Gradient(this.func);

return (gr.calc(this.result).norma() < this.precision && hes.calc(this.result).isNegative());

}

// check whether founded extremum is minimum

public bool isMinumum() {

Hessian hes = new Hessian(this.func);

Gradient gr = new Gradient(this.func);

return (gr.calc(this.result).norma() < this.precision && hes.calc(this.result).isPositive());

}

// run calculation process

public Vector run(Vector point)

{

Hessian hes = new Hessian(this.func);

Gradient gr = new Gradient(this.func);

Vector x = Vector.Copy(point);

int p = 0;

Vector oldx = new Vector();

do

{

oldx = Vector.Copy(x);

if (0 == p++ % this.frequencyCount) // recalc hessian

{

hes = hes.calc(x).invert();

}

if (this.recalcIterStep) // recalc iterative step

{

this.iterStep = this._recalcIterStep(x);

}

if (gr.calc(x).norma() < this.precision) { // exit to avoid precision errors

break;

}

x = x - this.iterStep * (hes * gr.calc(x));

this.process.push(x); // add to history

Console.WriteLine("{0:0.0000000}, {1:0.0000000} => {2:0.0000000}", x[0], x[1], this.func(x));

}

while ((oldx - x).norma() > this.precision);

return this.result = x;

}

// recalculate iterative step

double _recalcIterStep(Vector x) {

Hessian hes = new Hessian(this.func);

Hessian hesReverse = hes.calc(x).invert();

Gradient gr = new Gradient(this.func);

Gradient grRes = gr.calc(x);

Vector h = -1 * (hesReverse * grRes);

double iterStep = this.iterStep;

if (this.func(x + iterStep * h) > this.func(x))

{

do

{

iterStep *= 0.5;

}

while (this.func(x + iterStep * h) > this.func(x));

}

else {

iterStep = 1;

}

return iterStep;

}

// constructor

public Extremum_Searcher(Function func, int dimension)

{

this.func = func;

this.funcDim = dimension;

this.process = new Array(0);

}

}

3.2. Порівняльний аналіз

В цілому між дворівневими та багаторівневими індексно-послідовними файлами в плані оптимальності моделей побудови простежуються спільні риси. Зокрема підхід до обрахунку оптимальних параметрів є одним і тим же. Формули для обрахунку параметрів за різних законів розподілу імовірності мають схожий вигляд. Водночас при збільшенні кількості рівнів файлу спостерігається підвищення складності розрахунків. Зокрема збільшується розмірність систем для обрахунку параметрів. Це породжує необхідність розв’язування підзадачі, котра в загальному випадку не є простою. Це в свою чергу змушує замінювати оригінальні рівняння певними апроксимаціями, що зменшує кінцеву точність. Таким чином результати отримують не точний, а асимптотичний характер.

Таким чином крім теоретичного аспекту (обрахунок оптимальних параметрів математичних шляхом) слід взяти до уваги ще й практичний аспект, тобто результати, що базуються на практичному досвіді провідних компаній-розробників баз даних. Зокрема згідно порад компанії Borland (розробник баз даних Interbase) оптимальною кількістю рівнів індексу для великих файлів є 3-4. На офіційному форумі компанії у темі, де обговорювалось питання оптимальної кількості рівнів індексу для таблиці з великою кількістю даних була дана офіційна відповідь від компанії: «Оптимальною кількістю рівнів індексу для великих файлів є 3-4якщо у вас виникла потреба у більшій кількості рівнів, Вам слід переглянути структуру вашої таблиці або й цілої бази даних». Причини такого рішення висвітлено не було, але швидше за все причина полягає у складності розв’язування систем рівнянь великої розмірності.

Наведемо знімки з екрану, що дають приблизні уявлення про стиль і результати роботи програми. Знімки демонструють порівняльний аналіз для файлу одного порядку рівневості при різних законах розподілу ймовірностей звертань.

Рис. 4 – Порівняльний аналіз для однорівневого файлу при різних варіантах розподілу ймовірностей

Рис. 5 – Порівняльний аналіз для дворівневого файлу при різних варіантах розподілу ймовірностей

Можна спостерігати зменшення приблизно вдвічі середнього часу пошуку інформації, насправді це зменшення носить швидше логарифмічний характер і пов’язане, очевидно, з збільшенням кількості рівнів.

Рис. 6 - Порівняльний аналіз для багаторівневого (к-сть рівнів рівна 3) файлу при різних варіантах розподілу ймовірностей

Наведемо також графік, що демонструє зменшення часу пошуку для однорівневого індексно-послідовного файлу.

Рис. 7 – Порівняльний аналіз часу пошуку в однорівневому індексно-послідовному файлі при різних законах розподілу ймовірності доступу

Як бачимо програма допомагає обрахувати оптимальні параметри файлу та його індексу враховуючи закони розподілу ймовірностей звертань та кількість даних в файлі. Крім того демонструє різницю результатів графічно, що дає змогу візуально порівняти результати.

Програма демонструє часовий порівняльний аналіз залежно від різної кількості рівнів індексу файлу, що дозволить вибрати як вдале розбиття на блоки основного файлу, так і кількість рівнів його індексу.

Видно, що збільшення кількості рівнів сприяло зменшенню загального часу пошукую Водночас згідно досліджень провідних компаній-виробників програмного забезпечення баз даних така явна часова оптимізація різко спадає вже після 4-ого рівня. Крім того між теоретичними обрахунками і реальними результатами з’являються значні відхилення, пов’язані очевидно з застосованими апроксимаціями.

Висновок

У роботі розглянуто механізм пошуку даних в базах даних і запропоновано шляхи їх оптимального розташування в зовнішній пам’яті з метою отримання найменшого часу пошуку.

Розглянуто оптимальність побудови індексного файлу в умовах нерівномірного розподілу ймовірностей доступу до даних, розглянуто такі близькі до реалій закони нерівномірного розподілу як «бінарний», закон Зіпфа і розподіл, що наближено задовольняє закон «80-20».

Знайдено формули для явного знаходження оптимальних параметрів залежно від розподілу ймовірностей. У складніших випадках наведено лише системи рівнянь для знаходження цих параметрів, так як розв’язок таких систем є окремою задачею, взагалі кажучи складною у випадку великих розмірностей і нелінійних рівнянь.

Як розвиток теми, пропонується дослідити ефективність досліджених механізмів пошуку оптимальних параметрів для індексу, побудованого на основі B-дерев так кластеризованих двійкових дерев.

У практичній частині запропоновано невелику програмку, що допомагає обрахувати оптимальні параметри файлу та його індексу враховуючи закони розподілу ймовірностей звертань та кількість даних в файлі. Програма демонструє часовий порівняльний аналіз залежно від різної кількості рівнів індексу файлу, що дозволить вибрати як вдале розбиття на блоки основного файлу, так і кількість рівнів його індексу.

Список використаної літератури

1. Цегелик Г.Г. Некоторые оптимальные модели многоуровневых индексно-последовательных файлов // Модели и системы обработки информации, -1989. -Вып. 8, -С. 94-98.

2. Цегелик Г.Г. Определение параметров оптимальной организации многоуровневых индексно-последовательных файлов // Кибернетика, -1988. -№2, -С. 74-78.

3. Цегелик, Г. Г. Организация и поиск информации в базах данных // Львів, Вища школа, Видавництво при ЛНУ ім.І.Франка, 1987. - 176 c.

4. Кнут Д. Искусство програмирования для ЭВМ. Т.3. Сортировка и поиск.-М.: Мир, 1978.-844с.

5. Цегелик Г.Г. Организация и поиск информации в базах данных.-Львов: Вища шк.,1987.-176с.

6. Цегелик Г.Г. Оптимальна організація індексно-послідовних файлів при нерівномірному розподілі ймовірностей пошуку записів //Доп. АН УРСР. Сер.А, №3, 1987, с.70-73.

7. Цегелик Г.Г. Об оптимальной по времени поиска организации одноуровневого индекса //Исследование операций и АСУ. К.,1987, вып. 29, с.96-101.




 
 

Записник:
Вибранних робіт  

На данній час, в нашій базі:
Реферати: 5481
Розділи по алфавіту:
АБВГДЕЖЗ
ИЙКЛМНОП
РСТУФХЦЧ
ШЩЪЫЬЭЮЯ

 

Ключеві слова: Розробка та аналіз оптимальних моделей багаторівневих індексно-послідовних | Реферат

РефератБанк © 2017 - Банк рефератів, дипломні, курсові роботи - безкоштовно.