DESCRIÇÃO DAS BASES DE DADOS
Primeira Base de dados: BD1
Gerada pelo programa dbgen do TPC-H. Os registros dessa base não tem
tamanho fixo.
As relações escolhidas na geração dos dados foram Customer e Orders, os dados
foram gerados considerando que Os dados foram gerados considerando que 1/3
dos customers não possuem orders. Os atributos são separados pelo símbolo “|” e
o atributo de junção é O_CUSTKEY.
Relação Customer
CUSTOMER Table Layout
Column Name
Datatype
Requirements
C_CUSTKEY
Identifier
C_NAME
variable text,
size 25
C_ADDRESS
variable text,
size 40
C_NATIONKEY
Identifier
C_PHONE
fixed text, size
15
C_ACCTBAL
Decimal
C_MKTSEGMENT
fixed text, size
10
C_COMMENT
variable text,
size 117
Primary Key:
C_CUSTKEY
Quantidade
de Registros:
750.000
Comment
Foreign Key to
N_NATIONKEY
Tamanho: 116 MB
Exemplo de um registro da tabela:
1|Customer#000000001|IVhzIApeRb ot,c,E|15|25-989-7412988|711.56|BUILDING|to the even, regular platelets. regular, ironic
epitaphs nag e|
Relação Orders
ORDERS Table
Layout
Column Name
Datatype
Requirements
O_ORDERKEY
Identifier
O_CUSTKEY
Identifier
O_ORDERSTATUS
fixed text, size
1
O_TOTALPRICE
Decimal
O_ORDERDATE
Date
O_ORDERPRIORITY
fixed text, size
15
O_CLERK
fixed text, size
15
O_SHIPPRIORITY
Integer
O_COMMENT
variable text,
size 79
Primary Key:
O_ORDERKEY
Quantidade
de Registros:
7500.000
Comment
Foreign Key to
C_CUSTKEY
Tamanho: 829 MB
Exemplo de um registro da tabela:
1|221401|O|217606.77|1996-01-02|5LOW|Clerk#000005704|0|nstructions sleep furiously among |
Segunda Base de dados: BD2
Gerada pelo programa Spawner e por manipulações de arquivo usando
comandos do Linux.
Tabela 1
Tabela 1 Table Layout
Column Name
Datatype
Requirements
Comment
A
Texto
deTamanho
fixo
Composto por números, o
início do campo é
preenchido com espaços em
brancos (ver exemplo) para
se ter registros de tamanho
fixo
B
Texto de
Tamanho fixo
Composto por letras e
espaço em branco
Primary Key: A
Quantidade
de registros:
24.403.223
Tamanho: 535 MB
Exemplo de um registro da tabela:
Registro1: 14776252,sMd uywjpr
Registro2:
4533703,xBSRtFiNuh
Os valores do atributo A e do atributo B têm 10 bytes cada. Os campos são
separados por vírgula e o registro tem tamanho fixo de 21 bytes.
Tabela 2
Tabela 2 Table Layout
Column Name
Datatype
Requirements
Comment
A
Texto
deTamanho
fixo
Chave estrangeira que
referencia o campo A da
tabela 1
C
Texto de
Tamanho fixo
Composto por letras e
espaço em branco
Quantidade de registros 48.000.000
Tamanho: 1.02 GB
Dos 24.403.223 valores distintos da coluna A da primeira tabela 403.223 não
ocorrem na tabela 2. Os 48.000.000 registros da tabela2 possuem a seguinte
distribuição: 1/3 dos valores da coluna A não possuem repetições, 1/3 repete o
valor da chave duas vezes e 1/3 repete o valor da chave 3 vezes.
QUESTÕES IMPORTANTES
a) Parâmetros do programa
•
•
•
•
•
•
•
Nome do arquivo que contém os dados da relação menor
Nome do arquivo que contém os dados da relação maior
Tamanho do Buffer em MB (para os algoritmos que utilizam buffer)
Tamanho da Página em MB
Tabelas com registros de tamanho fixo.
Tamanho de cada atributo da relação menor.
Tamanho de cada atributo da relação maior.
b) Cálculo da quantidade de páginas no Buffer:
npb=tamanho do buffer/tamanho da pagina
Exemplo: tamanho do buffer=36MB, tamanho da página=4MB,
npb=36/4=8 páginas
c) Cálculo da quantidade de registros por Página:
•
Para registros de tamanho fixo:
nrp=tamanho da pagina/tamanho do registro, utilizar as medidas em Bytes,
fazer arredondamentos para ter uma quantidade inteira de registros na página.
Exemplo: tamanho da página=4MB, tamanho do registro=21 bytes
nrp=4*(1024*1024)/22=199.728 registros por página
•
Para registros de tamanho variável:
A quantidade de registros por página irá variar conforme o tamanho dos
registros. Nesse caso deve ser definida uma estratégia de ler sempre um número
de registros inteiros que não ultrapassem o tamanho da página.
Uma possível solução seria determinar o tamanho máximo de um registro na
base de dados e usar esse valor como referência para determinar o número de
registros por página.
d) Como definir o buffer e as páginas no programa:
Uma possibilidade
Definir o buffer como sendo uma estrutura de dados contendo uma lista de
páginas. A quantidade de página do buffer será dada pelo cálculo descrito
anteriormente. O buffer e a página terá o tamanho informado via parâmetro.
As páginas terão um identificador e poderão ser utilizadas para carregar
informações da Relação Menor, Maior ou o resultado da junção dos dados
conforme o algoritmo implementado.
Buffer tamanho= 16MB
Página 1
Página 2
1
Página 3
Página 4
INSTRUÇÕES PARA A PREPARAÇÃO DOS DADOS PARA OS TESTES DOS
ALGORITMOS UNION EXCEPT
TABELA R1
•
R1 = N primeiras tuplas da Tabela 2 (trata-se da tabela R de 1GB disponivel em
clique aqui), onde N = ¾ X, X = total de tuplas da Tabela 2
TABELA R2
•
R2 = N últimas tuplas da Tabela 2 (trata-se da tabela R de 1GB disponivel em
clique aqui), onde N = ¾ X, X = total de tuplas da Tabela 2
TABELA R3
•
•
•
•
Considere a Tabela 2 descrita aqui.
Os valores da coluna C são combinações de letras
Transforme tais valores em um número inteiro de no máximo 10 algarismos, da
seguinte: considere o número K obtido considerando-se o string substituindo-se
cada caracter pelo seu código ASCII e calcule K mod N, onde N = 1010
Tabela R3 = Tabela 2 com os valores da coluna C transformados em números
inteiros.