Uma Avaliação Experimental Sobre Técnicas de Indexação
em Banco de Dados Orientados a Objetos
Eduardo Ogasawara & Marta L. Q. Mattoso
[email protected] / [email protected]
Programa de Engenharia de Sistemas e Computação
COPPE/UFRJ
IDXGOA - Introdução
 Motivação

Necessidade de índices para os novos recursos
existentes em sistemas orientados a objetos



Expressões de Caminho
Herança
Métodos

Existência de diversas propostas para estruturas de
indexação

Pouca experiência com os índices propostos para
sistemas orientados a objetos

Conhecimentos obtidos por simulação em detrimento da
experimentação
IDXGOA - Introdução
 Objetivo do trabalho

Avaliar as novas estruturas de indexação

Selecionar índices para GOA++

Auxiliar o DBA na escolha dos índices
 Trabalho realizado

Projeto de uma arquitetura de indexação no GOA++

Definição de um ambiente para medições

Análise dos resultados obtidos
IDXGOA - Classificação dos Índices Estruturais
 Índices para Hierarquia de Classes
SCI - Índice para cada classe
 CHI - Índice para Hierarquia de classes
 Htree - Árvore H Aninhada
 tree - Índice de Árvore para hierarquia de classes

 Índices para Expressão de Caminho
PX - Índice para Expressão de Caminho
 NX - Índice Aninhado
 MX - Índice Múltiplo

 Índices Híbridos
IMX - Multi-Índice de Herança
 NIX - Índice Aninhado de Herança

Aplicação para estudo de caso
Modelo
Instâncias
Livro[L1]
0-201-59098-0
Banco de Dados
ACM Press
Kim
Periódico [P1]
0-201-59098-1
Banco de Dados
ACM Press
Vol. 8; N° 4
Livro[L2]
0-13-691643-0
Banco de Dados
Prentice-Hall
Ozsu
Periódico [P2]
0-07-052182-5
Eng. de Software
ACM Press
Vol. 9; N° 1
Livro[L3]
0-07-052182-4
Eng. de Software
McGraw-Hill
Pressman
Periódico [P3]
0-07-052182-6
Eng. de Software
ACM Press
Vol. 9; N° 2
Exemplo
Estrutura
SCI: Índice para cada Classe
Tamanho
Registro
Tamanho
chave
Tam Reg Tam chave
74
50
Valor
chave
Ponteiro para
Página de
Sobrecarga
N° OIDs = n
oid1…oidn
Chave
Sobrecarga
N° OIDs
Lista de OIDs
"Banco de
Dados"
0
2
[L1][L2]
Tamanho Tamanho
Registro
chave
Valor
chave
Ponteiro para
Página de
Sobrecarga
N°
classes =
n
id. da
classe1
deslocamento
Diretório de
N° OIDs = i
Classes
id. da
classen


oid1…oidi
N° OIDs = j
oid1…oidj
deslocamento
2
[L1][L2]
2
CID
[Livros]
0
CID
[Periódicos]
12
Deslocamento
Diretório de
Classes
CID
0
Deslocamento
"Banco de
Dados"
eri
ód
ic
1
OI
Ds
de
P
N°
OI
Ds
ivr
os
OI
Ds
de
L
N°
OI
Ds
So
bre
ca
rga
Ch
av
e
av
e
ch
Ta
m
50
CID
106
N° CIDs
Exemplo
Ta
m
Re
g
os
Estrutura
CHI: Índice para Hierarquia de Classes
[P1]
IDXGOA - Comparação entre Índices Hierárquicos
Índice
Critério
Distribuição de chaves
(desempenho)
Distribuição de chaves
(armazenamento)
Apoio a consultas sobre
atributo
Apoio a consultas sobre
classes
Apoio a consultas sobre faixa
de domínio
SCI
CHI
Sensível
Sensível
Sensível
Insensível
Baixo
Alto
Alto
Baixo
Baixo
Baixo
IDXGOA - Arquitetura do GOA++
Cliente
C++
Cliente
Java
Servidor TCP/IP
para o GOA
Gerente
Esquema
GerenteObjetos
Base de
Objetos
Processador
Consultas
IDXGOA
Servidorpáginas/cache
Núcleo do GOA++
IDXGOA - Modelagem da Estrutura de Indexação
GoaArvoreB
raiz
1..* GoaRegistroIntermediario
GoaNoIntermediario
0..1
0..1
0..1
GoaNoFolha
GoaChave
1..*
GoaIndice
GoaRegistroFolha
0..1
<<CID;OID>>
GoaIndiceCHI
TIndiceSimplesTemplate
TIndiceDicionarioTemplate
<<OID>>
GOAIndiceSCI
<<FZ>>
<<CID;OID>>
GOAIndiceIMX
GoaIndiceFz
<<OID>>
GoaIndiceMX
<<PX2Data>>
GoaIndicePX2
<<OID>>
GOAIndiceNX
<<NIXData;OID>>
GOAIndiceNIX
IDXGOA - Ambiente para Medições
DesignObj
Uso da Base de Dados OO7 no GOA++
id
type
buildDate
Module
1..*
ComplexAssembly
Assembly
0..*
BaseAssembly
1..*
CompositePart
1
1 root_part 1 AtomicPart
x
parts
y
1..* docID
Classes
Qtd.
Assemblies
166
CompositeParts
500
Documents
500
AtomicParts
10,000
Connections
60,000
N° de classes
16
1..*
Connection01
1
1..*
Document
ID
Title
Text
Connection02
Connection
type
length
. ..
Connectionxx
Plataforma: Windows NT Server 4.0 - Pentium II 266MHz
Resultados: Consultas pontuais
0,16
0,14
0,12
Tempo (s)
0,10
0,08
0,06
0,04
0,02
0,00
1
2
4
6
8
Classes
Deve-se usar sempre o CHI.
10
12
14
16
CHI
SCI
Resultados: Consultas por faixa - baixa repetição de valores
0.80
0.70
Tempo (s)
0.60
0.50
0.40
0.30
0.20
0.10
0.00
1
2
4
6
8
CHI (5%)
10
SCI (5%)
12
14
CHI (10%)
Até quatro classes, pode-se usar o SCI. Aumentando o
número de classes envolvidas, deve-se usar o CHI.
16
SCI (10%)
Resultados: Consultas por faixa - alta repetição de valores
4,00
3,50
3,00
Tempo (s)
2,50
2,00
1,50
1,00
0,50
0,00
1
2
4
6
8
CHI (5%)
Deve-se usar sempre o SCI.
10
SCI (5%)
12
14
CHI (10%)
16
SCI (10%)
IDXGOA - Conclusões
Pontual
-
Faixa
Conjunta
Disjunta
Distribuição
Tipo
Classes
Repetição
Índice
-
-
CHI
Baixa
Alta
Baixa
Alta
CHI/SCI
SCI
CHI
SCI
-
SCI
0..4
4..*
-
IDXGOA - Trabalhos futuros
 Índices para expressões de caminho

Avaliação de desempenho dos índices PX, MX e NX
 índices híbridos

Avaliação de desempenho dos índices NIX e IMX

Comparação de desempenho do uso conjunto de
índices de hierarquia de classes e expressões de
caminho versus a utilização única de um índice
híbrido