Бази даних повнота і надійність
Бази даних: повнота і надійність
# 9; Типовою впорядкованої інформаційної структурою є база даних. Такі бази з різних тем створювалися ще в докомпьютерную еру, але саме комп'ютеризація дозволила зробити якісний стрибок в цьому напрямку: крім власне бази (тобто сховища) даних, почали інтенсивно розвиватися системи навігації, тобто пошуку потрібних відомостей в неосяжному масиві бази. Все це в поєднанні з підвищеною потребою в таких інформаційно-пошукових системах привело до появи на ринку безлічі альтернативних пропозицій баз даних по будь-який більш-менш цікавою тематикою (цікавою для покупця, звичайно).
# 9; Зіткнувшись з необхідністю мати під рукою базу даних по якій-небудь темі, покупець часто виявляється здивований тим, яку (або які) бази йому краще придбати, ніж та чи інша база відрізняється від інших в кращу або гіршу сторону. При цьому ключовими порівнюваними параметрами баз даних можна вважати наступні: повнота бази (тобто наявність усіх відомостей по темі), якість навігаційного супроводження (тобто легкість і точність знаходження потрібної інформації в базі) і оперативність оновлення (тобто темп поповнення бази свіжими даними). І якщо два останніх параметра будь-який користувач може самостійно оцінити за паспортними даними та по демонстраційній версії бази, то про повноту судити значно важче (добре, якщо покупець знає десяток-другий об'єктів або документів, які зобов'язані бути присутніми в основі цієї тематики, і може переконатися в тому , скільки з них є в наявності в цій конкретній базі), найчастіше єдиним джерелом інформації про повноту є чесне слово розробника бази. Однак існують об'єктивні методи оцінки повноти баз даних, і справжня робота присвячена одному з таких методів.
1. Розрахунок для двох баз даних
# 9; Вихідні постулати розрахунку такі.
# 9; 2. Кожен документ має набір ідентифікаторів, однозначно його визначають (наприклад, дата створення документа, творець документа, вихідний номер, джерело інформації про документ, і т.п.), тобто в будь-який БД наявність даного документа можна встановити за комплексом його ідентифікаторів (в окремому випадку - по якомусь одному ідентифікатору, якщо цей ідентифікатор - унікальний).
# 9; 3. Будь-який документ має одні й ті ж ідентифікатори в різних БД.
# 9; 4. Кожна БД комплектується документами самостійно, незалежно від інших БД, тобто жодна БД не є постачальником первинної інформації для іншої БД.
# 9; В рамках цих положень можна далі міркувати так.
# 9; Нехай об'єктивно існує N документів по даній темі. Конкуруючі розробники БД розшукують ці документи з різною ефективністю, в результаті в базі БД1 міститься
# 9; Для отримання рішення досить використовувати тільки чотири рівняння з цих семи, і таких четвірок можна скласти:
Іншими словами, можна отримати 35 комплектів рішень. Не всі з них рівноцінні, і ось чому. Відносна точність визначення дискретної випадкової величини обернено пропорційна кореню квадратному з цієї величини (відповідно до формулами (6)), а в розрахункових формулах з множенням і діленням таких випадкових величин їх відносні помилки підсумовуються, як показано в виразах (7). Якщо врахувати, що всі n i. як правило, більше будь-якого з n ij. а ті, в свою чергу, істотно більше n ijk. то це означає, що по можливості слід уникати використання n ijk в розрахунках, тобто не користуватися останнім (сьомим) рівнянням з набору (10). Тоді число комбінацій рівнянь зменшиться до
Ці 15 рівнянь можна розділити на 4 групи, в кожній з яких рішення виходять циклічної перестановкою індексів:
1. Є три системи типу:
2. Є шість систем типу:
3. Є три системи типу:
Система нерозв'язна, тому що рівняння лінійно залежні:
4. Є три системи типу:
# 9; Отже, отримано 12 комплектів рішень, причому розрахункові формули в цих комплектах частково повторюються:
# 9; При обчисленні середнього значення, дисперсії і середньоквадратичного відхилення кожної з цих величин частота повторення формул повинна бути врахована введенням відповідних вагових коефіцієнтів. У найпростішому випадку розрахунок усереднених величин можна проводити за формулами:
# 9; Дисперсія і середньоквадратичне відхилення для a 1m розраховуються за формулами (21) і (22), відповідно:
Аналогічні формули можна записати і для інших трьох змінних (ми тут цього не робимо тільки з міркувань економії місця).
# 9; Незважаючи на громіздкість наведених формул, всі ці розрахунки легко і швидко реалізуються в комп'ютерному виконанні з застосуванням будь-яких електронних таблиць (в даній роботі використовувалися електронні таблиці Excel5.0).
# 9; Цікаво, що при наявності відомостей про трьох базах з'являється можливість і заглянути в "кухню" кожного з розробників баз. Справа в тому, що якщо вихідні дані для розрахунку представити в дещо іншій формі:
- число документів, присутніх тільки в БД1;
- число документів, присутніх тільки в БД2;
- число документів, присутніх тільки в БД3;
-число документів, наявних тільки в БД1 і в БД2;
-число документів, наявних тільки в БД1 і в БД3;
-число документів, наявних тільки в БД2 і в БД3;
-число документів, наявних у всіх трьох базах,
то з'являється можливість виявити і недобросовісна поведінка розробника, "відкачує" документи з чужої бази в свою, і зворотну ситуацію - наявність потужного джерела інформації, доступного тільки одному з розробників, і, нарешті, наявність якогось "джентльменського набору" документів, зобов'язаних бути представленими в будь-якій базі даних, що відноситься до заявленої теми.
# 9; Зв'язок між числами m і n очевидна:
3. Модельний експеримент
# 9; Для перевірки якості методики розрахунку був поставлений наступний модельний експеримент. Припустимо, об'єктивно існує масив з N0 документів (наприклад, нормативних актів, що регулюють науково-дослідницьку діяльність). Припустимо також, що k розробників пропонують свої бази даних з цього питання, причому кожен i -й розробник розшукує для своєї бази ці нормативні акти із заданою вірогідністю ai0. в результаті чого в його базі міститься ni0 = N ai0 документів відповідної тематики. Якщо все числа ni0. nij0. в точності відповідають заданим N0 і ai0 (i = 1. k), то, підставивши ці числа в формули, виведені в попередніх розділах, ми автоматично реконструюємо ті величини N0 та ai0. які самі заклали в модель.
# 9; А тепер дещо змінимо умови модельного експерименту. Адже кожна з вихідних величин ni. nj. реально схильна нагоди, і середньоквадратичний розкид їх визначається формулами (5), причому у відповідності з теорією ймовірності в 80% випадків відхилення реальної величини ni від істинної ni0 не перевищує D ni. в 95% випадків це відхилення не перевищує 2 D ni і лише в 0,3% випадків відхилення виявляється більше 3 D ni. Тому модифікуємо нашу модель наступним чином: всі вихідні ( "ідеальні") величини х0 (x0 = n10. N20. N120.) Замінюємо на
де D x0 = -среднеквадратічная помилка,
f і w - випадкові числа з рівномірним розподілом в інтервалі від нуля до одиниці,
# 9; А - масштабний коефіцієнт, що задає амплітуду випадкового впливу (А = 0. 4).
# 9; Підставляючи ці змінені вихідні величини в наші розрахункові формули, ми, природно, отримаємо результат, в якійсь мірі близький до "ідеального", але все ж від нього відрізняється. Для оцінки точності реконструювання параметрів N0 і ai0 модельний експеримент даного типу можна повторювати неодноразово, кожен раз за допомогою генератора випадкових чисел варіюючи набір вихідних даних. Це і було виконано для двох моделей:
Щоб відчути масштаб відхилень вихідних величин в кожній серії експериментів, в таблицях 2 і 3 показана частина результатів (вся серія включала по 60 експериментів для кожного значення амплітуди А).
Таблиця 2. Вихідні числа для модельного експерименту з двома базами
(N1 = 300, n2 = 200, n12 = 100)
# 9; В цій таблиці в другому стовпці поміщені найменування шуканих величин, в третьому - середнє по серії з 60 експериментів значення кожної величини, в четвертому стовпці - розрахункова помилка одиничного вимірювання, в останніх двох стовпчиках - максимальне і мінімальне значення шуканої величини, що трапилося в серії.
# 9; Видно, що навіть в разі А = 3 (ймовірність максимального відхилення при такому А в теорії оцінюється в 0,3%) результати розрахунку дуже непогані. Числа четвертого стовпця, відповідні середньої помилку кожного одиничного розрахунку, визначають допустимий розкид, набагато перекриває відхилення будь-який з середніх величин (третій стовпець) від "теоретичної". Для другої серії вимірювань (при А = 2) помилка одиничного розрахунку найближче відповідає максимальному і мінімальному відхилень розрахункових величин від середніх (а ймовірність такого екстремального відхилення теорією визначається в 5%). Середні ж величини, отримані в цій серії, збігаються з теоретичними з точністю до часток відсотка. І тільки в третій серії експериментів з сильно завищеною величиною розкиду (ймовірність такої ситуації оцінюється всього в 0,3%) трапляються варіанти, коли реконструйовані величини більш ніж на 20% відрізняються від справжніх (хоча середні по серії значення як і раніше дуже близькі до дійсних).
# 9; Експеримент з трьома базами дав результати, зведення яких приведена в Таблиці 5.
Середнє по серії
Помилка кожної моделі,%
Максимальне значення в серії
Максимальне значення в серії
# 9; Все висновки, отримані на моделі двох баз, тут справедливі навіть в посиленому вигляді. Тому ми зважилися на розширення експерименту в бік ще більшої "розгойдування" вихідних даних. Випадково така розгойдування вже практично не може статися, але комплектування баз - процес не чисто статистичний і не можна виключити можливість як негласного використання вмісту чужих баз, так і приватного доступу до багатого інформацією першоджерела (наприклад, до архіву потужного емітента документів); крім того, неминуче і вплив ненульового "джентльменського набору" документів, обов'язкових у всіх базах (більш докладно це фактор буде розглянуто нижче). Четверта серія експериментів показала, що і в цьому випадку максимальне відхилення реконструйованих величин від точних значень укладається в 15-25%.
# 9; В цій групі експериментів виявилася не надто помітна особливість: чим менше величина a i. тим більше виявляється розкид реконструйованої величини цього параметра. Якщо тепер повернутися до даних Таблиці 5 для двох баз, то і там можна помітити ту ж тенденцію.
4. Три бази і "джентльменський набір"
# 9; Вище згадувалося, що, крім суто статистичних механізмів комплектування баз даних, існує певна кількість документів, які є "індикаторами" тематики бази даних. Наприклад, навряд чи хто наважиться назвати базу правової інформації найменуванням "Федеральне законодательствоУкаіни", якщо в цій базі буде відсутній такий документ, як Конституція РФ. Або якщо в базі даних "Неорганічні матеріали" будуть відсутні відомості про простих хімічних елементах (не з'єднання, а саме елементах). З точки зору завдань цієї роботи існування "джентльменського набору" обов'язкових документів додає ще одну невідому до наших чотирьох і надмірність системи рівнянь (10) - (16) зменшується. Але при цьому істотну роль починає грати саме останнє з цих рівнянь, тому що саме там в максимальному ступені позначається вплив нової невідомої величини. І самі рівняння з урахуванням цієї невідомої виглядають тепер трохи інакше:
# 9; Отже, з перелічених систем можна отримати 18 приватних рішень (що враховують тільки частину рівнянь загальної системи (24) - (30)). Чи не захаращуючи текст формулами для обчислення середніх значень, дисперсії і середньоквадратичної помилки, скажімо тільки, що всі ці обчислення проводяться за тією ж методикою. що і в розділі 3 цієї роботи, оформлені вони також у формі електронних таблиць Excel5.0.
# 9; Розрахункові формули цього розділу дещо складніше, ніж в розділі 3, тому цікаво було перевірити, наскільки хороша збіжність і стійкість рішень при обліку "джентльменського набору" документів, для чого був знову поставлений модельний експеримент, описаний в наступному розділі.
5. Модельний експеримент-2
# 9; Вихідні посилки модельного експерименту такі. Об'єктивно існує масив з N0 документів по заданій темі, причому Y0 документів з цієї кількості є загальнодоступними і обов'язковими для будь-якої бази даних, які претендують на обслуговування саме цієї теми. Таким чином, кожен з k розробників має в своїй базі ці Y0 документів, а решту документів, як і раніше, розшукує і включає в свою базу з ймовірністю a i0. так що в його базі міститься ni0 = Y0 + (N0 -Y0) a i0 документів. Фактор випадковості врахуємо точно так же, як це було зроблено в розділі 3, тобто всі вихідні ( "ідеальні") величини х0 (x0 = n10, n20, n120.) замінюємо на x = x0 + D x0 (f-w) A. де D x0 = -среднеквадратічная помилка, # 9; f і w - випадкові числа з рівномірним розподілом в інтервалі від нуля до одиниці, А - масштабний коефіцієнт, що задає амплітуду випадкового впливу (А = 0. 3).
# 9; Оскільки мінімальна кількість баз даних в цьому випадку не може бути менше трьох (при двох базах виходить три рівняння з чотирма невідомими і система рівнянь виходить недостатньою), то в даному розділі досліджувалася тільки одна модель з наступними вихідними даними: N0 = 1050, Y0 = 50, a 10 = 0,3, a 20 = 0,5 і a 30 = 0,7. Кожна серія включала 100 модельних експериментів при фіксованому значенні масштабного коефіцієнта А. У таблиці 6 наведено вихідні дані перших експериментів цих серій.
Таблиця 6. Вихідні числа для модельного експерименту з трьома базами
(Точні значення складають: n1 = 350, n2 = 550, n3 = 750, n12 = 200, n13 = 260, n23 = 400, n123 = 155)
# 9; Аналізуючи дані Таблиці 7, можна зробити наступні висновки:
# 9; 1. У 80% випадків (А = 1) точність визначення шуканих величин досить висока: помилка визначення ефективностей a в середньому становить 1,5-3%, і навіть максимальні відхилення в серії з 100 експериментів укладаються в 6-10%; величина "джентльменського набору" документів Y визначається менш точно (середньоквадратична помилка становить 15%, але максимальне відхилення в серії досягло 30-40%), втім, на точності визначення повного числа документів N це майже не позначається, 1,5% -ва помилка в середньому і 4-5% в максимальному відхиленні - цілком задовільно.
# 9; 2. Збільшення А до 1,5 збільшує похибку визначення всіх величин, хоча середні значення залишаються дуже близькі до "ідеальним". Найбільш відчутно відреагувала на зростання статистичного розкиду все та ж величина Y. Зауважимо, що в обох серіях все без винятку розрахунки пройшли коректно, ніяких збоїв типу поділу на нуль не було (хоча в знаменнику іноді з'являлися аномально маленькі величини, про що свідчить несиметричність максимальних відхилень N в сторону великих і малих значень).
# 9; 3. Збільшення А до двох помітно погіршило умови розрахунку: середні значення шуканих величин вже істотно відрізняються від "ідеальних", з'явилися збої в розрахунку, з'явилися і аномально великі Nмакс. і негативні величини a (в таблиці вони вилучені), середньоквадратичні помилки вже виросли до 30-50%.
# 9; 4. Остання серія (А = 3) показала, що такий розкид (а ймовірність його мимовільної реалізації не перевищує 0,3%) робить розрахунок безглуздим: 40% експериментів цієї серії не дали результату, розрахункові формули не працювали.
# 9; Такий результат дозволяє зробити висновок, що для баз з незалежними і однаковими технологіями комплектації розрахунок по даному алгоритму дасть розумні результати, статистичний розкид вихідних даних слабо впливає на кінцеві результати; однак, будь-яка взаємозалежність баз або будь-яка винятковість будь-якої бази обов'язково позначаться на коректності розрахунку і швидше за все в якійсь із розрахункових формул приведуть до нісенітниці. Очевидно, щоб з таких ситуацій зробити певні і цілком конкретні висновки, необхідно попередньо промоделювати деякі найбільш прості варіанти.