Створення Бази Даних Зображень
Подождите немного. Документ загружается.
Зосередженні (або централізовані) розподілені бази даних фізично
розміщені в одному місці. Для обміну інформацією поміж окремими (локальними)
півбазами використовуються канали зв’язку прямого доступу. Обмін даними поміж
взаємозв’язаними півбазами здійснюється без помітних обмежень на обсяги і характер
інформації, що передається. Такі бази даних мають ряд переваг: просту побудову бази
даних, зведення до мінімуму дублювання інформації, максимально уніфікацію методів
зберігання,коректування і пошуку інформації.
Проте зосереджені бази даних в одному місці – вузлі мережі – мають цілий ряд
недоліків: при централізації зберігання значно збільшується час на передачу інформації і
за рахунком цього зростає час реакції системи; централізована система обмежена
обсягами пам’яті ЕОМ тощо.
Розосереджені (або децентралізовані) розподілені бази даних
фізично розміщені в різних місцях – вузлах обчислювальної мережі. Обмін інформацією
поміж під базами здійснюються з використанням каналів зв’язку. Як під бази
розподіленої бази даних можуть використовуватись зосереджені (централізовані) бази
даних і окремі (локальні) під бази. Обмін інформацією поміж взаємозв’язаними під
базами здійснюється головним чином результатною (обробленою, узагальненою)
інформацією. При виконанні запиту в таких системах використовується декомпозиція
запиту на під запит до локальних під баз і паралельне виконання виділених під запитів у
різних вузлах обчислювальної мережі. Ці бази даних мають безперечні переваги у
порівнянні з централізованими: обсяги пам’яті обмежені пам’ятю не однієї ЕОМ, а
сумарною пам’ятю ЕОМ, які знаходяться в усіх вузлах мережі; зменшуються затрати на
передавання інформації, так як у кожному вузлі знаходиться та інформація, яка
необхідна конкретному користувачу і по можливості забезпечує всі його інформаційні
потреби. Однак розосереджена база даних призводить до неминучого дублювання деякої
інформації, безконтрольності її зростання, а також значно ускладнюється проблема
зберігання несуперечності інформації.
Розглянута концепція розподілених баз даних знаходить широке розповсюдження
при функціонуванні розподіленої обробки інформації. При цьому організація такої
обробки інформації відбувається, як правило, в рамках системної автоматизованої
обробки інформації як в окремих структурних ланках, так і по об'єкту управління в
цілому.
Технічною передумовою зазначених процесів є те. що одержують розповсюдження (і
занадто ефективно) ПЕОМ, які прості в експлуатації і обслуговуванні, мають відносно
11
низьку вартість і малі габарити тощо. Все це дозволяє наблизити їх до місць виникнення
і первинного використання інформації про процеси, які відбуваються в виробничо-
господарській діяльності об'єкта управління, а також розподілити їх на всіх рівнях
управління цього об'єкта.
В умовах системної обробки інформації, колі концепція розподіленої обробки
інформації реалізується на базі комплексів ПЕОМ і локальних мереж, знаходять широке
використання АРМ керівників і фахівців різних рівнів об'єкта управління.
Вимоги до оптимальних моделей баз даних та їх
характеристика.
Основні вимоги до оптимальної моделі баз даних[4].
1) Адекватність відображення логіки предметного середовища у відповідні моделі
даних.
2) Оптимальна надмірність даних. БД повинна являти собою єдину сукупність
інтегрованих даних.
В системах, що не використовують бази даних, кожне застосування має свої файли.
Наприклад, застосування, пов’язане з обліком персоналу, і застосування, пов’язане з
обліком навчання персоналу можуть мати свої власні файли з інформацією о персоналі.
Це призводить до надмірності даних, що зберігаються. Наслідком надмірності даних може
бути суперечність даних, наприклад, коли два записи про одного і того ж співробітника не
погоджуються одна з одною.
3) Наявність ефективних засобів ведення баз даних ( засоби створення, накопичення,
модифікації, видалення та пошуку даних ).
Засоби створення даних - це засоби завантаження даних з зовнішнього, орієнтованого
на користувача, уявлення у системне.
4) Цілісність даних ( наприклад, забезпечення вимоги унікальності усіх записів БД ) та
їх узгодженість при виконанні користувачами операцій над ними. Керування одночасними
модифікаціями.
Задача цілісності полягає в забезпеченні правильності і точності даних в базі даних.
Протиріччя між двома записами, що зображують один і той самий факт - є прикладом
недостачі цілісності. У більшості продуктів баз даних підтримка контролю цілісності
розвинена слабо.
12
5) Безпека даних - захист від несанкціонованого доступу до даних та від руйнування
БД з наміром або без наміру.
Централізована природа системи баз даних вимагає наявності хорошої системи
безпеки. Доступ до даних дозволяється лиш тим користувачам, що мають на те право.
6) Можливість реструктуризації БД - наявність засобів змінювання структури даних
при змінюванні запитів до БД.
7) Наявність повних, зручних та простих у вивченні мовних засобів визначення та
маніпулювання даними.
Такими засобами є мова визначення даних та мова маніпулювання даними. Автономну
мову даних, тобто мову, що не включена в універсальну мову, називають також мовою
запитів.
8) Наявність документації.
9) Простота вивчення.
10) Взаємна незалежність програм та даних.
БД повинна зберігати працездатність при розвитку програмного та апаратного
забезпечення. Зміна фізичної організації даних або параметрів запам’ятовуючих пристроїв
не впливають на користувача, або, точніше, на прикладну програму. Зміна уявлення
користувача не потребує затрат на реорганізацію та зміну механізму доступу до файлів
фізичних даних. Незалежність даних забезпечує можливість функціонування системи при
змінах з обох сторін ( тобто зі сторони користувача та фізичних даних ) і є найбільш
важливою властивістю і основною метою БД. Вона впливає на наявність інших
властивостей, таких як, надмірність даних, можливість забезпечення захисту та цілісності
та ін.
Незалежність даних можна визначити як імунітет програм до змін в структурах
зберігання даних і в методах доступу до даних. Наприклад, деяке застосування обробляє
файл з інформацією о співробітниках і цей файл проіндексований по деякому полю. Якщо
програма враховує, що послідовність записів у файлі визначена даним індексом, то
неможливо замінити індексований файл на хешований без внесення суттєвих змін у
програму.
13
Організація бази даних зображень
Великі бази даних зображень, як і інші крупні бази даних, дуже великі для того, щоб
про обробці пошукового запиту можна було би перебирати всі зображення що
зберігаються в базі даних. Замість цього зображення повинні бути організовані і
індексовані так, щоб лише частини з них роглядалася при обробці будь-якого запиту.
Існують ряд стандартних методів для індексації числових і текстових атрибутів, які
застосовуються в більшості реляційних систем управління базами даних. Вони
використовуються наприклад в геоінформаційних системах. В рамках сучасних
досліджень також розробляються методи індексації зображень, розрахованих на
використання в системах пошуку зображень на основі вмісту.
Стандартні індекси
В більшості реляційних СУБД користувач може вказати атрибут, по якому необхідно
побудувати індекс. Зазвичай цей атрибут являється ключовим значенням, зв’язаним з
кожним записом таблиці бази даних. Наприклад, якщо в базі даних зберігаються записи
про службовців деякої компанії, то в якості атрибута для індексації цих даних міг би бути
вибраний номер соціального страхування, то цей атрибут може бути вибраний в якості
первинного ключа. Якщо дані часто виймаються по якимось іншим атрибутам, наприклад
по прізвищу службовця, то по цим атрибутам також можливо побудувати окремі індекси.
В реляційних базах даних індекс представляє собою структуру даних, яка
використовується ситемою для пошуку по заданому атрибуту і дозволяє швидко знайти
всю множину записів бази даних, що має атрибут із заданим значенням. В реляційних
СУБД часто використовуються індекси двух типів: хеш –індекси(hash index), і індекси на
основі В-дерев(B-tree index). Хеш-індекси забезпечують швидке знаходження множини
записів, що мають атрибути з тим же значенням, яке задане в запиті. Індекси на основі В-
чи В+ дерев дозволяють швидко знайти записи, у яких атрибути мають значення, що
лежать в деякому діапазоні, що вказаний в запиті.
14
Хеш-індекси
В реалізації хеш-індексів для доступу до великої множини записів бази даних
використовуються хеш-таблиці. При цьому рахуємо, що наявна велика множина
можливих значень ключа, але в БД одночасно буде присутьня лише частина з них.
Допустимо що база даних містить файл з N записами. Кожен запис складається з
декількох різних полів, серед яких одне поле призначене для зберігання ключових
значень. Механізм доступу до хеш-індексу передбачає використання хеш функції, яка
перетворюєбудь-яке значення ключа в адресу в файлі, який містить запис(чи зберігає
покажчик на запис) БД, що містить задане ключове значення. Якщо ключові значення
являються числами, то одною з простіших хеш-функцій може бути f(x)=x mod N.
0
1
2
3
4
5
6
7
8
9
Ключ - 45
75 данні 45 данні
Запит
Хеш - таблиця
Рис. 1 Приклад хеш-індекса
15
Ця функція зменшує значення ключа х шляхом взяття залишку від цілочисельного
ділення на N і використовує це значення як номер запису для доступу до неї. На рис 1
приведена ілюстрація використання хеш-індекса для БД з числовими ключами. Хеш-
таблиця містить десять елементів, пронумерованих від 0 до 9 ( на практиці хеш-таблиці
можуть мати набагато більше). В якості хеш-функції використовується функція
f(x)=xmod10. Даний запит, вибирає всі запити, у яких ключовий атрибут рівний 45. Адреса
записів, що містять ключовий атрибут з таким значенням, є в 5-му елементі хеш-таблиці.
Якщо кожне ключове значення хешується у власному елементі таблиці, то час доступу
по любому ключовому значенню постійно. В загальному випадку це не так. Декілька
різних ключових значень можуть бути хешовані в одному і тому ж елементі індекса. Це
явище називається колізією. Способи вирішення цієї проблеми описані в большості книг
по структурам даних. Рішення, що використовується на рис.1 основується на використанні
звязного списку для зберігання адрес всіх записів, ключі яких хешовані в одному і томуж
елементі хеш-таблиці. Кінцевий результат – в будь-якому випадку – полягає в тому, що
при пошуку в базі даних переглядається невелика кількість даних, що набагато менше,
ніж при простому безпосередньому доступі. Для хороших хеш-функцій і не дуже
заповнених хеш-таблиць час доступу залишається приблизно постійним при будь-якому
значенні ключа. Використання хешування найкраще підходить для обробки записів з
обмеженнями вида KEY=VALUE і менш придатне для обробки запитів з вказанням
діапазону значень.
Індекси нав основі В+-дерев
В-дерева та В+дерева являються збалансованими деревами пошуку, які можна
використовувати для індексації баз даних. Вони зручні для обробки запитів, в яких
вказаний діапазон допустимих значень. В В-деревах значення ключів і даних зберігаються
у внітрішніх і в листових вузлах. В В+ деревах, так як дані в базі даних повинні
зберігатися окремо від індекса.
Дерево пошуку порядку р представляє собою дерево, в якому кожен вузол
містить не більше р-1 ключових значень і р вказівників. В+ дерево являється
деревом пошуку, у якого формати представлення внутрішніх і листових вузлів
розрізняються. Кожен внутрішній вузол В+ дерева повинен задовольняти
наступним умовам:
Вузол має формат (P1,K1,P2,K2,….,Pq-1,Kq-1,Pq), де кожне значення Рі
являється вказівником на інший вузол, а кожне Кі являється ключовим значенням.
Можна рахувати що Рі-1 вказує на піддерево, у якого вузли містять ключі,
16
значення яких менше чи рівне Кі а Рі вказує на піддерево, у якого ключі мають
значення, що перевищує Кі.
Якщо вузел не кореневий, то він містить мінімум [(p/2)] вказівників на
піддерева.
Кореневий вузол містить мінімум 2 вказівника на піддерева
Кожен листовий вузол В+ дерева задовольняє наступним умовам:
1. Вузол має формат (K1,Pr1,K2,Pr2,….,Kq-1,Pq-1>Pnext), де
Kiявляється ключем, Pri – вказівником на дані, а Pnext - вказівником на
наступний листовий вузол.
2. Вказівник Pri вказує чи на запис чи блок записів, що мають ключ
пошуку Кі.
3. В кожному листовому вузлі зберігається [(p/2)] значень
4. Всі листові вузли розміщені на одному рівні дерева.
Порядок внутрішніх вузлів р може відрізнятися від порядку листових вузлів. Часто
вузли мають такий обєм, щоб вузол кожного типу поміщався в фізичний блок диску.
Використання обємів даних, кратних розміру фізичного блоку, зазвичай забезпечує
найбільш ефективну передачу даних між диском і оперативною памяттю.
При пошуку з допомогою В+ дерева ключа з заданим значенням чи ключа, що
належить заданому діапазону значень, система пошуку починає обробку з кореневого
вузла дерева. Вона зчитує цей вузол в пам'ять і виконує двійковий пошук серед ключів,
що зберігаються в даному вузлі. Якщо в вузлі знаходяться два суміжних ключових
значення, між якими піддерево, яке буде містити шукане ключове значення чи найменше
значення із вказаного діапазону ключів. Якщо шукане ключове значення менше першого
ключового значення вузла, то вказівник зліва від цього ключа буде посилатися на
піддерево для подальшого пошуку. Аналогічно, Яякщо шукане ключове значення
перевищує останнє ключове значення у вузлі, то вказівник справа від цього ключа
посилається на піддерево для подальшого пошуку. Після знаходження дерва, яке
підходить, пошук продовжується з кореневого вузла цього піддерева. Пошук виконується
рекурсивно до досягнення листового вузла.
В листовому вузлі знову виконується двійковий пошук для виявлення шуканого
ключового значення чи початкового значення ключа Кі. Звязаний з ним вказівник Рі
17
вказує на запис даних, що містить це ключове значення. Якщо виконується пошук лише
одного ключового значення, то на цьому етапі можна повернути знайдений запис даних.
Якщо ж виконується пошук по діапазону, то вказівники Pnext на наступні листові
вузли можуть використовувати для знаходження записів даних що залишилися, поки не
буде знайдений кінець заданого в запиті діапазону ключів.
На рис 2 є приклад В+ дерева, що використовується для індексації записів бази даних з
числовими ключовими значеннями і даними зображень. Внутрішні вузли позначені
суцільним прямокутниками, а листові вузли – штрифовим прямокутниками. Кореневий
вузол вказує на три різних піддерева: одне піддерево зберігає значення ключів, мінші чи
рівні 100, інше зберігає значення ключів від 100 до 200, а третє – значення ключів, що
перевищує 200. На рис. 2 зображене дерево з ключовими значеннями від 100 до 200.
Кореневий вузол цього піддерева містить вказівники на два листових вузла: один зі
значенням ключів, які є меншими 110, а інший – зі значеннями ключів між 110 і 150.
Листові вузли містять деякі існуючі ключові значення і вказівники на відповідні цим
значенням файли з даними зображень.
В+ дерева являються гнучкими і ефективними структурами даних. Вони широко
використовуються в реляційних системах управління базами даних, про які я згадував
дещо вище. Вони можуть використовуватись і в базах даних зображень для індекв\сації
окремих числових чи текстових полів, співставлених із зображенням. Індекси даного типу
не призначені для використання з багатовимірними даними.
Просторова індексація.
В інформаційних системах, що обробляють просторову інформацію, зберігаються
багатовимірні дані. Для просторової індексації було запропоновано декілька різних
структур даних.
Квадратні дерева – це ієрархічні структури четвертого порядку, що дозволяють
розбити простір пошуку двовимірних даних на чотири квадранти на кожному рівні дерева.
Квадратні дерева можуть використовуватись для опису областей бінарних зображень.
К – вимірні дерева являються розширенням бінарних дерев пошуку, що призначені для
організації пошуку серед к-вимірних даних.
R-дерева – це розширення В-дерев на дані великої розмірності. Вони зручні для
використання в різних системах, що працюють з просторово упорядкованою інформацією.
В R-дереві обєкт даних індексується з використанням n-вимірного мінімального
описуючого прямокутника, який відмежовує область простору, яку займає обєкт. Кожен
18
існуючий обєкт даних позначається з допомогою унікального ідентифікатора. В листових
вузлах К-дерева зберігаються ідентифікатори обєктів даних. Внутрішні вузли містять
записи виду (MRB, CHILD), де CHILD – це вказівник на нижній вузол R-дерева, а MRB
охоплює всі прямокутники із записівнижніх кутів. На рис 13 показаний приклад індекса
на основі R-дерева для набору двовимірних обєктів. Розподіл прямокутників залежить від
порядка формування R-дерева і використовуваного для цього алгоритма.
19
Рис. 2 Приклад індексації на основі R-дерева для індексації двовимірних даних.
R1 R2
R3 R4 B C D
A E
A
B
C
Набір прямокутників, що індексуються
R1
R3
R2
20