Пример объектно-ориентированной БД

Сентябрь 2, 2022

Главная
Алгебра
Пример объектно-ориентированной БД

Содержание

2. 5.5. Пример объектно-ориентированной БД (XMLDB). СУБД ИНЕС (для ЕС ЭВМ), НИКА (для РС) Цели разработки: -
3. 5.5.1. База данных – совокупность двух файлов. ИмяБД.dod (схема БД) ИмяБД.tree (данные) Например. avto.dod и avto.tree
4. Назначение схемы БД: Шифровка имен. Вместо имен вершин (до 256 символов), в дереве данных хранятся шифры
5. 5.5.2. Метод записи деревьев в памяти В С D E F G H I J Рассмотрим
6. В С D E F G H I J Преобразование N-арной структуры в K А В
7. Разбивка на страницы БД разбита на страницы. На каждой странице хранится связный фрагмент дерева. Этот фрагмент
8. Длина данного - ссылка на следующую вершину дерева в смысле левого обхода. В каждой не терминальной
9. Если на странице внешней памяти есть сводное место >= ΔМ, то сдвигаются данные J и K
10. 5.5.3. Метод деления страниц. При вводе данных в пустую БД открывается 1-я страница, в которую данные
11. 5.5.3. Метод деления страниц (продолжение 1) Идентификатор следующего вводимого данного сравнивается с идентификаторами справочной. Вызывается соответствующая
12. 5.5.3. Метод деления страниц (продолжение 2) Такая организация памяти позволяет в любое место вставить произвольное количество
13. 5.5.3. Метод деления страниц (продолжение 3) На страницах справочных помещается в среднем примерно одно и тоже
14. Описатель блока Данные Свободная память
15. Описатель блока Данные Свободная память Описатель блока Данные Свободная память Справочная 1-го уровня
16. Описатель блока Данные Свободная память Описатель блока Данные Свободная память Описатель блока Данные Свободная память Описатель
17. Описатель блока Справочная 1-го уровня Свободная память Описатель блока Данные Свободная память Описатель блока Данные Свободная
18. 5.5.4. Доступ к данным Т.1. Если известен составной (конкатенированный) ключ, то время доступа минимально. Док. Доступ
19. Т.2. Если необходим перебор по всей БД или любому поддереву, время доступа минимально. Док. На каждой
20. 5.5.4. Доступ к данным (объем БД) Т.3. Объем минимален у слабо заполненных БД и БД со
21. № посл. вершины Типы верш. Имя вершины Шифр вершины Дескриптор Имя Словарь Шифры Шифр вершины Шифр
22. Автомобили Гос. номер Марка Цвет 5.5.6. Пример БД 1). Схема БД Автомобиль
23. Автомобили : массив Гос. номер : текст (ключ) Марка : текст Цвет : текст 2). Показ
24. Автомобили Марка : ВАЗ 2109 Цвет : синий 2). Показ самой БД МНЭ 50 - 25
25. Авто 137 (послед. занятый №) Автомобили 3). Описание данных ( Авто.dod) 1 2 30 Дескриптор (30,
26. Автомобили 3 Root 30 Автомобиль 30 31 Гос. номер 31 37 Марка 31 39 Цвет 31
27. 30 39 : ВАЗ 2109 42 : синий 4). Сами данные ( Авто.dod) 31 : МНЭ
28. 5.5.7. Оптимизация времени доступа Три подхода к реализации доступа: Интерпретация (dBASE) Трансляция (Clipper) Трансляция при первом
29. 5.5.8. Индексация в ООБД и XML DB Люди ФИО Адрес ФИО Люди R № пасп ФИО
30. Люди ФИО Адрес Инверсный вход в ООБД № пасп Образов Работы Адрес Адрес ФИО А ФИО
31. Индекс в СУБД НИКА
32. Индекс в СУБД НИКА
33. INDEX A . . . ai . . . a1 . . . . aN B
34. INDEX A . . . ai . . . a1 . . . . aN B
36. Скачать презентацию

Слайд 2

5.5. Пример объектно-ориентированной БД (XMLDB). СУБД ИНЕС (для ЕС ЭВМ), НИКА

(для РС)

Цели разработки:
- Объектное проектирование
- Снятие ограничений на размеры
- БД – произвольный граф
- Единый индекс
- Возможность менять схему БД без перезагрузки базы
- Эффективность хранения и доступа

Слайд 3

5.5.1. База данных – совокупность двух файлов.
ИмяБД.dod (схема БД)
ИмяБД.tree (данные)

Например. avto.dod и avto.tree
dod – дерево описания данных (ДОД)
tree – дерево данных (ДД)

Слайд 4

Назначение схемы БД:
Шифровка имен.
Вместо имен вершин (до 256 символов),

в дереве данных хранятся шифры (1-2 байта).
Обеспечение целостности БД.
Вводить данные в БД можно будет только в соответствие со схемой (структурой объектов и подобъектов и типами терминальных данных).

Слайд 5

5.5.2. Метод записи деревьев в памяти
В
С
D
E
F
G
H
I
J
Рассмотрим следующую структуру
K
А
N-арное дерево

Слайд 6

В
С
D
E
F
G
H
I
J
Преобразование N-арной структуры в
K
А
В
С
D
E
F
G
H
I
J
K
А
Бинарное дерево

Слайд 7

Разбивка на страницы
БД разбита на страницы. На каждой странице хранится связный

фрагмент дерева. Этот фрагмент превращается из N-арного в бинарный. В каждой вершине хранятся не более двух ссылок: на первую из подчиненных вершин и на следующую из соподчиненных вершин.
Бинарное дерево записывается в память подряд
(в порядке левого обхода):
A B C D E F G H I J K

Слайд 8

Длина данного - ссылка на следующую вершину дерева в смысле

левого обхода.
В каждой не терминальной вершине, вместо данного, хранится длина подчиненного поддерева.

Информация, записанная в каждой вершине

Идентификатор данного (шифр)
Значение данного, если вершина терминальная
Длина данного для терминальных вершин
Длина подчиненного поддерева для нетерминальных вершин

Слайд 9

Если на странице внешней памяти есть сводное место >= ΔМ,

то сдвигаются данные J и K на ΔМ.
В освободившееся место помещается данное М.
Длины поддеревьев А и G увеличиваются на ΔМ.
Если на странице свободное место <= ΔМ, то включается алгоритм деления страницы.

Ввод новых данных

Например, вершины М между I и J (ΔМ - длина М).

Слайд 10

5.5.3. Метод деления страниц.
При вводе данных в пустую БД открывается

1-я страница, в которую данные записываются в лексикографическом порядке.
Когда емкость 1-й страницы исчерпана, на диске открывается 2-я, и данные распределяются примерно поровну.
Старшие данные остаются на 1-й, младшие - на 2-й.
На 1-й странице организуется справочная, куда выносятся номера страниц и идентификаторы первых данных.

Слайд 11

5.5.3. Метод деления страниц (продолжение 1)
Идентификатор следующего вводимого данного сравнивается

с идентификаторами справочной.
Вызывается соответствующая страница и новое данное записывается в нее.
.

Слайд 12

5.5.3. Метод деления страниц (продолжение 2)
Такая организация памяти позволяет в

любое место вставить произвольное количество новых данных.
При переполнении одной из уже существующих страниц открывается следующая страница, куда пересылаются младшие данные; в справочную заносится старший ключ новой страницы.
При переполнении справочной возникает справочная второго уровня, в строках которой хранятся ссылки на справочные первого уровня. В дальнейшем - справочные более высоких уровней.
Это обеспечивает балансировку по вертикали.

Слайд 13

5.5.3. Метод деления страниц (продолжение 3)
На страницах справочных помещается в

среднем примерно одно и тоже число ключей, это приводит к балансировке по горизонтали.
Освободившиеся при удалении данных страницы поступают в резерв свободных, а освободившаяся память внутри страниц - в резерв свободной памяти страницы.

Слайд 14

Описатель блока
Данные
Свободная память

Слайд 15

Описатель блока

Данные
Свободная память
Описатель блока
Данные
Свободная память
Справочная

1-го уровня

Слайд 16

Описатель блока

Данные
Свободная память
Описатель блока
Данные
Свободная память
Описатель блока
Данные
Свободная

память

Описатель блока

Данные

Свободная память

Справочная
1-го уровня

Слайд 17

Описатель блока

Справочная
1-го уровня
Свободная память
Описатель блока
Данные
Свободная память
Описатель

блока

Данные

Свободная память

Описатель блока

Справочная
1-го уровня

Свободная память

Справочная
2-го уровня

Описатель блока

Данные

Свободная память

Описатель блока

Данные

Свободная память

Слайд 18

5.5.4. Доступ к данным
Т.1. Если известен составной (конкатенированный) ключ, то время

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

Слайд 19

Т.2. Если необходим перебор по всей БД или любому поддереву, время

доступа минимально.
Док. На каждой странице хранится связное поддерево. После вызова страницы в ОП совершается обход поддерева, страницы вызываются один раз без перевызовов.

5.5.4. Доступ к данным

Слайд 20

5.5.4. Доступ к данным (объем БД)
Т.3. Объем минимален у слабо заполненных БД

и БД со значениями реквизитов разной длины.
Док. Не отводится место под несуществующие реквизиты, реквизит всегда занимает минимальное место +2 байта (шифр и длина). Эффект может достигать нескольких порядков.
Задание. Привести пример, когда объем реляционной БД меньше?

Слайд 21

№ посл.
вершины
Типы
верш.
Имя
вершины
Шифр
вершины
Дескриптор
Имя
Словарь
Шифры
Шифр вершины
Шифр
отца
1
2
3
5.5.5. Структура описания данных

Слайд 22

Автомобили
Гос.
номер
Марка
Цвет
5.5.6. Пример БД
1). Схема БД
Автомобиль

Слайд 23

Автомобили : массив
Гос. номер : текст (ключ)
Марка : текст
Цвет :

текст

2). Показ Схемы БД на дисплее

Автомобиль : структура

Слайд 24

Автомобили
Марка : ВАЗ 2109
Цвет : синий
2). Показ самой БД

МНЭ 50 - 25

Марка : ВАЗ 2104

Цвет : белый

МНЭ 60 - 13

. . . . . . .

Слайд 25

Авто
137 (послед. занятый №)
Автомобили
3). Описание данных ( Авто.dod)
1
2
30
Дескриптор (30,

массив)

Автомобиль

Дескриптор (31, структура)

Гос. номер

Дескриптор (37, текст, ключ)

Марка

Дескриптор (39, текст)

Цвет

Дескриптор (42, текст)

Слайд 26

Автомобили
3
Root
30
Автомобиль
30
31
Гос. номер
31
37
Марка
31
39
Цвет
31
42
137
140
(определение шифра по имени)
(среди соподчиненных
нет одноименных)
……..

Слайд 27

30
39 : ВАЗ 2109
42 : синий
4). Сами данные (

Авто.dod)

31 : МНЭ 50 - 25

39 : ВАЗ 2104

42 : белый

31 : МНЭ 60 - 13

. . . . . . .

Слайд 28

5.5.7. Оптимизация времени доступа
Три подхода к реализации доступа:
Интерпретация (dBASE)
Трансляция

(Clipper)
Трансляция при первом обращении (НИКА)

(см. пред. слайд)

Слайд 29

5.5.8. Индексация в ООБД и XML DB
Люди
ФИО
Адрес
ФИО
Люди
R
№ пасп
ФИО
№ пасп
Обычный инверсный вход

Слайд 30

Люди
ФИО
Адрес
Инверсный вход в ООБД
№ пасп
Образов
Работы
Адрес
Адрес
ФИО
А
ФИО
Адр
А
Адр
Индекс

Слайд 31

Индекс в СУБД НИКА

Слайд 32

Индекс в СУБД НИКА

Слайд 33

INDEX
A . . .
ai . . .
a1 . . . .
aN
B

. . .

A=ai

B=bk

Пример двух веток индекса:
A = ai
B = bk

Индекс в СУБД НИКА

Слайд 34

INDEX
A . . .
ai . . .
a1 . . . .
aN
B

. . .

A=ai

B=bk

Пример выполнения логических операций:
«И» - объекты ,
«ИЛИ» - и объекты.

Индекс в СУБД НИКА

Пример объектно-ориентированной БД

Содержание

5.5. Пример объектно-ориентированной БД (XMLDB). СУБД ИНЕС (для ЕС ЭВМ), НИКА

5.5.1. База данных – совокупность двух файлов. ИмяБД.dod (схема БД)ИмяБД.tree (данные)

Назначение схемы БД: Шифровка имен. Вместо имен вершин (до 256 символов),

5.5.2. Метод записи деревьев в памяти ВСDEFGHIJРассмотрим следующую структуруKАN-арное дерево

ВСDEFGHIJПреобразование N-арной структуры вKАВСDEFGHIJKАБинарное дерево

Разбивка на страницыБД разбита на страницы. На каждой странице хранится связный

Длина данного - ссылка на следующую вершину дерева в смысле

Если на странице внешней памяти есть сводное место >= ΔМ,

5.5.3. Метод деления страниц. При вводе данных в пустую БД открывается

5.5.3. Метод деления страниц (продолжение 1) Идентификатор следующего вводимого данного сравнивается

5.5.3. Метод деления страниц (продолжение 2) Такая организация памяти позволяет в

5.5.3. Метод деления страниц (продолжение 3) На страницах справочных помещается в

Описатель блока ДанныеСвободная память

Описатель блока ДанныеСвободная память Описатель блока ДанныеСвободная память Справочная

Описатель блока ДанныеСвободная память Описатель блока ДанныеСвободная память Описатель блока ДанныеСвободная

Описатель блока Справочная 1-го уровняСвободная память Описатель блока ДанныеСвободная память Описатель

5.5.4. Доступ к данным Т.1. Если известен составной (конкатенированный) ключ, то время

Т.2. Если необходим перебор по всей БД или любому поддереву, время

5.5.4. Доступ к данным (объем БД)Т.3. Объем минимален у слабо заполненных БД

№ посл.вершиныТипыверш.ИмявершиныШифрвершиныДескрипторИмяСловарьШифрыШифр вершиныШифр отца1235.5.5. Структура описания данных

АвтомобилиГос.номерМаркаЦвет5.5.6. Пример БД1). Схема БДАвтомобиль

Автомобили : массивГос. номер : текст (ключ)Марка : текст Цвет :

АвтомобилиМарка : ВАЗ 2109 Цвет : синий 2). Показ самой БД

Авто137 (послед. занятый №) Автомобили3). Описание данных ( Авто.dod) 1230Дескриптор (30,

Автомобили3Root30Автомобиль3031Гос. номер 3137Марка3139Цвет 3142137140(определение шифра по имени)(среди соподчиненных нет одноименных)……..

3039 : ВАЗ 2109 42 : синий 4). Сами данные (

5.5.7. Оптимизация времени доступаТри подхода к реализации доступа: Интерпретация (dBASE) Трансляция

5.5.8. Индексация в ООБД и XML DBЛюдиФИОАдресФИОЛюдиR№ паспФИО№ паспОбычный инверсный вход

ЛюдиФИОАдресИнверсный вход в ООБД№ паспОбразовРаботыАдресАдресФИОАФИОАдрААдрИндекс

Индекс в СУБД НИКА

Индекс в СУБД НИКА

INDEXA . . .ai . . .a1 . . . .aNB

INDEXA . . .ai . . .a1 . . . .aNB

Похожие презентации

5.5.1. База данных – совокупность двух файлов.
ИмяБД.dod (схема БД)
ИмяБД.tree (данные)

Назначение схемы БД:
Шифровка имен.
Вместо имен вершин (до 256 символов),

5.5.2. Метод записи деревьев в памяти
В
С
D
E
F
G
H
I
J
Рассмотрим следующую структуру
K
А
N-арное дерево

В
С
D
E
F
G
H
I
J
Преобразование N-арной структуры в
K
А
В
С
D
E
F
G
H
I
J
K
А
Бинарное дерево

Разбивка на страницы
БД разбита на страницы. На каждой странице хранится связный

5.5.3. Метод деления страниц.
При вводе данных в пустую БД открывается

5.5.3. Метод деления страниц (продолжение 1)
Идентификатор следующего вводимого данного сравнивается

5.5.3. Метод деления страниц (продолжение 2)
Такая организация памяти позволяет в

5.5.3. Метод деления страниц (продолжение 3)
На страницах справочных помещается в

Описатель блока
Данные
Свободная память

Описатель блока

Данные
Свободная память
Описатель блока
Данные
Свободная память
Справочная

Описатель блока

Данные
Свободная память
Описатель блока
Данные
Свободная память
Описатель блока
Данные
Свободная

Описатель блока

Справочная
1-го уровня
Свободная память
Описатель блока
Данные
Свободная память
Описатель

5.5.4. Доступ к данным
Т.1. Если известен составной (конкатенированный) ключ, то время

5.5.4. Доступ к данным (объем БД)
Т.3. Объем минимален у слабо заполненных БД

№ посл.
вершины
Типы
верш.
Имя
вершины
Шифр
вершины
Дескриптор
Имя
Словарь
Шифры
Шифр вершины
Шифр
отца
1
2
3
5.5.5. Структура описания данных

Автомобили
Гос.
номер
Марка
Цвет
5.5.6. Пример БД
1). Схема БД
Автомобиль

Автомобили : массив
Гос. номер : текст (ключ)
Марка : текст
Цвет :

Автомобили
Марка : ВАЗ 2109
Цвет : синий
2). Показ самой БД

Авто
137 (послед. занятый №)
Автомобили
3). Описание данных ( Авто.dod)
1
2
30
Дескриптор (30,

Автомобили
3
Root
30
Автомобиль
30
31
Гос. номер
31
37
Марка
31
39
Цвет
31
42
137
140
(определение шифра по имени)
(среди соподчиненных
нет одноименных)
……..

30
39 : ВАЗ 2109
42 : синий
4). Сами данные (

5.5.7. Оптимизация времени доступа
Три подхода к реализации доступа:
Интерпретация (dBASE)
Трансляция

5.5.8. Индексация в ООБД и XML DB
Люди
ФИО
Адрес
ФИО
Люди
R
№ пасп
ФИО
№ пасп
Обычный инверсный вход

Люди
ФИО
Адрес
Инверсный вход в ООБД
№ пасп
Образов
Работы
Адрес
Адрес
ФИО
А
ФИО
Адр
А
Адр
Индекс

INDEX
A . . .
ai . . .
a1 . . . .
aN
B

INDEX
A . . .
ai . . .
a1 . . . .
aN
B