А Мельничин, Г Цегелик - Ефективність оптимальних схем варіантів пошуку інформації у послідовних файлах баз даних - страница 1

Страницы:
1  2 

ВІСНИК ЛЬВІВ. УН-ТУ Серія прикл. матем. інформ. 2010. Вип. 16. C. 47-53

VISNYK LVIVUNIV. Ser. Appl. Math. Inform. 2010. Is. 16. P. 47-53

УДК 004.632.3

ЕФЕКТИВНІСТЬ ОПТИМАЛЬНИХ СХЕМ ВАРІАНТІВ ПОШУКУ ІНФОРМАЦІЇ У ПОСЛІДОВНИХ ФАЙЛАХ БАЗ ДАНИХ

А. Мельничин, Г. Цегелик

Львівський національний університет імені Івана Франка, вул. Університетська, 1, Львів, 79000, e-mail: kafmmsep@franko.lviv.ua

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

Найбільш поширеною організацією файлів баз даних є послідовна [1, 3]. У [2, 4-6] досліджена ефективність пошуку записів у послідовних файлах баз даних, які містяться в зовнішній пам'яті однопроцесорних ЕОМ, залежно від вибраного варіанта пошуку записів і розподілу ймовірностей звертання до записів. У цьому разі розглянуто такі варіанти пошуку: послідовне читання блоків записів в основну пам'ять і їхній послідовний перегляд; послідовний перегляд блока записів, який попередньо локалізований шляхом читання блоків записів в основну пам'ять і перегляд їхніх останніх записів; використання методу блочного пошуку в блоці записів, який попередньо локалізований шляхом читання блоків записів в основну пам' ять і перегляду їхніх останніх записів; читання та послідовний перегляд блока записів, який попередньо локалізований шляхом читання і перегляду останнього запису кожного блока. Серед законів розподілу ймовірностей звертання до записів розглянуто рівномірний і такі близькі до реальності нерівномірні розподіли: "бінарний", Зіпфа та узагальнений, частковим випадком якого є розподіл, що наближено задовольняє правило "80-20". У цій роботі для згаданих законів розподілу ймовірностей звертання до записів проведено порівняльний аналіз оптимальних схем згаданих варіантів пошуку.

2. ФОРМУЛЮВАННЯ ЗАДАЧІ

Розглянемо послідовний файл, який містить N записів. Припустимо, що файл зберігається в зовнішній пам'яті ЕОМ і всі його записи умовно розбиті на n блоків по m записів у кожному. Введемо позначення:

a = b + dm - час читання блока записів в основну пам'ять (якщо блок записів буде містити ms записів, то a = b + dms), де b, d - деякі сталі; t - час перегляду запису в основній пам'яті; pi - ймовірність звертання до і-го запису файла; E -математичне сподівання загального часу, потрібного для пошуку запису у файлі.

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

3. ПЕРШИЙ ВАРІАНТ ПОШУКУ

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

1. ВСТУП

© Мельничин А., Цегелик Г., 2010

Математичне сподівання Е загального часу, потрібного для пошуку запису у файлі, виражається формулою [2, 6]

nm

E = YY.{ai + ((І - 1) m + j) t) p(i-1)m+j .

Формули для знаходження математичного сподівання для різних законів розподілу ймовірностей звертання такі:

у випадку рівномірного розподілу ймовірностей

E = 2 ((m +1 j (b + dm ) + (N + 1)t

• для "бінарного" розподілу ймовірностей з точністю до нескінченно малої величини

E =-(b + dm)+ 2t;

2m - Г

для закону Зіпфа з достатньо високою точністю

E = — ((HN + n - lln n - C If b + — I + Nt

n

1 N

N

де C1 = 0.5ln2^ , Н», = V - частинна сума гармонічного ряду;

високою точністю

(( 1.,1-c -.(c)! \\\

E

H(c

11 N

N!l(n-аМ)\( b+Nd|+H(c-Dt

-n -

1 - c { 2 - c n[1]-c

'1

N 1

де с - будь-який параметр (0 < c < 1); H'N) = V~ - частинна сума узагальненого

гармонічного ряду; ac (n) = H[2]^ 1)--[3] n2 c - повільно зростаюча функція.

2 - c

4. ДРУГИЙ ВАРІАНТ ПОШУКУ

Пошук записів у файлі відбувається шляхом послідовного перегляду блока записів, який попередньо локалізований при послідовному читанні блоків записів в основну пам'ять і перегляду їхніх останніх записів. Якщо математичне сподівання загального часу, потрібного для пошуку запису у файлі, подати у вигляді суми математичного сподівання загального часу, потрібного для локалізації блока, і математичного сподівання загального часу, потрібного для пошуку запису в локалізованому блоці, то математичне сподівання Е загального часу, потрібного для пошуку запису у файлі, виразиться формулою [2, 6]

E = VV(ai +(i + j)t)p((-1)m+j .

Формули для знаходження математичного сподівання для різних законів розподілу ймовірностей звертання до записів такі: • для рівномірного розподілу ймовірностей

1 N

+ 1 І (b + dm +1 ) + (m + l)t

2 1^ m

• у випадку „бінарного" розподілу ймовірностей з точністю до нескінченно малої величини

E =

2 m

-(b + dm + t) + І 2

m

2m - V '   {    2m -1

для закону Зіпфа з достатньо високою точністю t;

E-­1

--+1 І+ І ln n + C1 І—t І;

n      I   {2 ) n 1

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

E ­1

((

HN> +

N

1-c f

1 - С

c -1  a c) ( n)

-n--r1-^-

21-c -c n

H

(c-1)

N2

1 - c 1 2 - c

c -1 a{c)(n)

+ —Г71 N t

1n

5. ТРЕТІЙ ВАРІАНТ ПОШУКУ

Припустимо, що файл розбитий на n блоків по ms записів у кожному і процес пошуку запису відбувається так: спочатку локалізується блок, який містить шуканий запис, шляхом послідовного читання блоків записів в основну пам'ять і перегляду їхніх останніх записів. Після цього пошук потрібного запису продовжується в локалізованому блоці за допомогою методу блочного пошуку. У цьому разі локалізований блок записів умовно розбивається на s підблоків по m записів у кожному. Якщо подати математичне сподівання загального часу, потрібного для пошуку запису у файлі, у вигляді суми математичного сподівання часу, потрібного для локалізації блока записів, математичного сподівання часу, потрібного для локалізації підблока записів, і математичного сподівання часу, потрібного для пошуку запису в локалізованому підблоці, то Е виразиться формулою [4]

ns m

E = ILILIK™ + k + j)t) P(,-1)ms+(k-1)m+j ,

i=1 k=1 j=1

де a = b + dms .

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

• у випадку рівномірного розподілу ймовірностей

E = - ((— + 11 (b + dms) + \— + s + m + 3 11 2 \\ms    J \ ms J

для „бінарного" розподілу ймовірностей з точністю до нескінченно малої величини

E

+

E--

-(b + dms) +1

• 2

+

m - 2

2ms - Г '   { 2ms -1        2m -1

для закону Зіпфа з достатньо високою точністю

E--

t;

1

HN + — - 11п— - C1 I (b + dms) +

ms   2 ms

+ I 2H— + +

2^(s + m -2)ln+(m -l)lns|| + (s + m -2)C1 t

ms 2

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

(

2H—J+ H—,-1) +

N l-c 1 - c

N l-c 1 - c n +--^-L

2 - c

b + d I +

( N - n)

c -1   (s - 1)g(c) (n)

2-c

N

a(c) (ns)

(ns)1-c

t

6. ЧЕТВЕРТИЙ ВАРІАНТ ПОШУКУ

При розгляді цього варіанта вважатимемо, що всі записи файла розбиті на n блоків по m записів у кожному і пошук запису в файлі відбувається так. Спочатку знаходимо блок, що містить шуканий запис файла, шляхом читання і перегляду останнього запису кожного блока. Після цього локалізований блок зчитується в основну пам'ять і пошук у ньому продовжується з використанням методу послідовного перегляду. Якщо подати математичне сподівання загального часу, потрібного для пошуку запису у файлі, у вигляді суми часу читання блока записів в основну пам' ять, математичного сподівання загального часу, потрібного для локалізації блока, і математичного сподівання загального часу, потрібного для пошуку запису в локалізованому блоці, то Е виразиться формулою [2, 6]

n    m n m

E = a + ЕХЛP(i-1)m+j + T.T.JtP((-1)m+j ,

i=1 j =1 i=1 j=1

де t1 - час читання і перегляду запису в основній пам'яті (t1 = b + d +1) .

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

• у випадку рівномірного розподілу ймовірностей

E = b + dm +1 |J  + 1jjt1 + (m + 1)tjj;

• для „бінарного" розподілу ймовірностей з точністю до нескінченно малої

величини

E = b + dm +—-11 + I 2 -

2m -1     ^    2m -1 • для закону Зіпфа з достатньо високою точністю

t;

E = b +-+-

n HN

N

t I;

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

E = b + dN + t1

n H

(c)

Hn + 1 - c

1 - c      a)(n)

2 - cn n[4]-c

H

(c)

Hn    + 1-c

c-1 a [5] (n

2-c

7. ПОРІВНЯЛЬНИЙ АНАЛІЗ.

У таблиці для розглянутих варіантів пошуку (з точністю до 0.01) наведені значення параметрів m і n, за яких математичне сподівання досягає мінімуму, для різних законів розподілу ймовірностей звертання до записів, b / d = 1000 , t / d = 0,1 і

N = 10[6].

 

 

 

 

 

Закон розподілу

 

 

 

n

Рівномірний

c=0.2

c=0.4

c=0.6

c=0.8

c=1

"Бінарний"

І варіант

 

31.62

33.85

37.57

44.74

61.46

108.10

105790.42

 

m

31622.75

29540.70

26617.90

22349.70

16271.99

9250.44

9.45

II варіант

n

33.16

Страницы:
1  2 


Похожие статьи

А Мельничин, Г Цегелик - Ефективність оптимальних схем варіантів пошуку інформації у послідовних файлах баз даних