Instituto de Computação
Universidade Estadual de Campinas
MC202 – Estruturas de Dados (A, B, C, D)
BDMoSS
30 de setembro de 2011
1
Problema
Desta vez um Banco de Dados, em Memória, Super Simples (BDMoSS) precisa ser criado
para gerenciar pequenas coleções de registros. Esse Banco de Dados (BD) suporta, de forma
restrita, apenas 6 cláusulas: CREATE, DELETE, DUMP, INSERT, SELECT e UPDATE. O formato de
cada uma destas cláusulas pode ser visto nas Figuras 1–5.
,
CREATE
TABLE
(
nome
nome
)
tipo
;
;
DUMP
Figura 1: Cláusulas CREATE e DUMP
DELETE
FROM
nome
WHERE
nome
IN
..
start
;
end
Figura 2: Cláusula DELETE
,
INSERT
INTO
(
nome
,
)
nome
(
valor
)
;
Figura 3: Cláusula INSERT
,
SELECT
(
)
nome
WHERE
FROM
nome
nome
IN
..
start
;
end
Figura 4: Cláusula SELECT
,
UPDATE
nome
(
nome
WHERE
,
)
(
nome
)
valor
IN
start
Figura 5: Cláusula UPDATE
1
..
end
;
Um retângulo qualquer nas Figuras 1–5 com o texto “tipo” indica que o conteúdo do mesmo
será substituído por INTP (chave primária de tipo inteiro), INT, ou TEXT (uma string qualquer).
Caso o texto seja “nome” então o mesmo pode representar ou um nome de uma tabela ou o nome
de uma das colunas da tabela. No lugar do texto “valor” estará presente ou um número inteiro
ou uma string. Por último, “start” e “end” são números inteiros (start ≤ end) e representam
uma faixa de valores.
A leitura das cláusulas já está pronta, você precisa apenas implementar o BD. Na sua
implementação, as subcláusulas WHERE trabalharão somente com colunas que representam chaves primárias. Além disso, cada uma das tabelas do seu BD será descrito por uma Árvore
B+ onde as chaves dos nós serão dadas pelos valores das chaves primárias – a entrada criará
apenas tabelas contendo uma única coluna como chave primária. No seu BD, registros podem
ter valores vazios (representados por “NULL”) em qualquer uma das colunas com exceção do
campo da chave primária. A inserção de um registro em uma tabela com uma chave primária
já existente nesta tabela não tem efeito algum, assim como um UPDATE ou SELECT ou DELETE
com valores de chaves primárias que não existem na respectiva tabela. E, também, a entrada
nunca fornecerá cláusulas que: 1) criam duas tabelas com o mesmo nome; 2) utilizam tabelas
ou colunas inexistentes; 3) fazem uso de uma mesma coluna repetidas vezes.
Neste trabalho não é necessário que a cláusula DELETE realmente remova chaves, você
pode apenas marcar um item como removido (e tomar os devidos cuidados). Você também
não precisa se preocupar com a atualização de chaves primárias, pois esta operação não é
permitida no BDMoSS. A criação de uma tabela com n colunas implica em criar uma Árvore
B+ de ordem n + 2 + k, onde k = (1 + último digito do seu RA) mod 3. Logo, cada nó deverá
ter no máximo n + 2 + k registros.
Uma Árvore B+ é bastante semelhante à Árvore B comum. As duas principais diferenças
são: 1) todo conteúdo das chaves ficam nas folhas; os nós internos são utilizados apenas
para chegar até as mesmas; 2) todas as folhas ficam ligadas, tornando eficiente uma busca
sequencial em amplitude. Como todas as chaves (e seus respectivos conteúdos) ficam nas
folhas, uma inserção que requer divisão de nós não é exatamente igual àquela em uma Árvore
B. A diferença é que quando um nó folha é dividido, sua chave mediana é mantida na folha
e copiada para o nó pai. Se o nó pai precisar ser dividido, a chave mediana do pai é movida
para o pai do nó pai. A Figura 6 ilustra uma estratégia para esta situação.
17 35 50
3 5 17
20 35
17 35 50
48 50
83 90 91
3 5 17
20 35
48 50
83 90
91
(b) Nó folha é dividido; copia chave 90 no pai
(a) Árvore inicial
35
17 35
3 5 17
20 35
17
50 90
48 50
51 83 90
3 5 17
91
(c) Nó interno é dividido; propaga chave 35
50 90
20 35
48 50
51 83 90
(d) Nova raiz é criada
Figura 6: Exemplo de inserção da chave 51 numa Árvore B+ de ordem 3
2
91
2
Entrada
A entrada consiste em uma sequência de cláusulas bem formadas para o BDMoSS.
Exemplo:
CREATE
INSERT
INSERT
DUMP;
UPDATE
DELETE
SELECT
3
TABLE aluno (ra INTP, nome TEXT, semestre INT);
INTO aluno (ra, nome, semestre) (123, "Bob Esponja", 2);
INTO aluno (ra, semestre, nome) (321, 3, "Sandy");
aluno (semestre) (1) WHERE ra IN 123..123;
FROM aluno WHERE ra in 150..400;
(nome, semestre) FROM aluno;
Saída
Seu programa deve exibir os resultados das execuções das cláusulas DUMP e SELECT no momento
em que elas são especificadas. A saída de um DUMP deve exibir: 1) a quantidade de tabelas no
BD, quantidade total de linhas em todas tabelas e número de registros removidos, atualizados
e selecionados; 2) todas as tabelas do BD na ordem em que foram criadas. A saída de um
SELECT deve incluir o cabeçalho da tabela, conforme a ordem imposta pela cláusula, e os
resultados obtidos. Após cada tabela exibida, imprima uma linha em branco. O formato da
saída a seguir deve ser utilizado. Para decidir pela largura de uma coluna, utilize a fórmula:
max(|nome da coluna|, max(|item já inserido na coluna|), |00 N U LL00 |) + 2.
Exemplo:
1 tabela
2 linhas
0 deletes, 0 updates, 0 selects
aluno
+------+-------------+----------+
| ra
| nome
| semestre |
+======+=============+==========+
| 123 | Bob Esponja | 2
|
+------+-------------+----------+
| 321 | Sandy
| 3
|
+------+-------------+----------+
+-------------+----------+
| nome
| semestre |
+=============+==========+
| Bob Esponja | 1
|
+-------------+----------+
3
4
Avaliação
A nota deste laboratório será dada por:


SuSy



}|
z



{


n


X






(teste
==
correto)
?
1
:
0
i




 


i=1
 + 3 DQ
nota = CS 7 



n



















A variável DQ corresponde a documentação adequada (comentários no código fonte) e
qualidade do código entregue. A variável booleana CS indica se o código em C está coerente
com o enunciado da Seção 1.
Seu trabalho deve ser dividido da maneira seguinte:
btree.h : Protótipos para Árvore B+ ;
btree.c : Implementação da Árvore B+ ;
db.h : Protótipos para o BD (parcialmente fornecido);
db.c : Implementação do BD;
input.h : Contém os protótipos necessários para manuseio da entrada (fornecido);
input.c : Trata toda a entrada (fornecido);
main.c : Chama funções em input.c e encaminha consultas para o BD (fornecido);
5
Entrega
• Submissão de código ao SuSy (15 tentativas no máximo): de 30 de setembro às 12:00 a
14 de outubro às 02:00
6
Links extras
I http://www.db-class.org/course/video/preview_list
I The Ubiquitous B-tree
I Organization and Maintenance of Large Ordered Indices
4
Apêndice A – Construção de uma Árvore B+
A Figura 7 expande a Figura 6 de modo a apresentar a construção por etapas da árvore
resultante pela estratégia escolhida.
50
50
17 50
17 50 90
(a) Inserção das
chaves 17, 50 e
90 na árvore vazia
83 90
3
17 50
(b) Inserção da chave 83; nó folha (c) Inserção das chaves 3 e 91
é dividido e chave 50 é copiada
17 50
17 50
3
5
17
83 90 91
50
3
83 90 91
(d) Inserção da chave 5; nó folha é dividido e chave
17 é copiada
5
17
20 35 50
83 90 91
(e) Inserção das chaves 20 e 35
17 35 50
3
5
17
20 35
48 50
83 90 91
(f) Inserção da chave 48; nó folha é dividido e chave 35 é copiada
35
17
3
5
17
20 35
50 90
48 50
51 83 90
91
(g) Inserção da chave 51; veja Figura 6
Figura 7: Construção passo a passo de uma Árvore B+ de ordem 3 até chegar na árvore
resultante da Figura 6
5
Apêndice B – Entendendo as cláusulas
É importante entender as cláusulas das Figuras 1–5 para saber como seu BD deve operar. Se
você já conhece SQL (Structured Query Language), este Apêndice pode ser ignorado.
Uma cláusula CREATE determina que uma tabela de nome x deve ser criada com um mais
campos de nome ci e tipo ti . Durante a criação da tabela, a ordem das colunas é fixada
e a mesma deve ser respeitada na execução de um DUMP. Esta tabela, inicialmente vazia,
eventualmente será objeto de manipulação. As cláusulas SELECT, INSERT, UPDATE e DELETE
são aquelas que manipulam as tabelas existentes.
Um SELECT é divido em três partes: 1) definição das colunas dos registros a serem retornadas; 2) nome da tabela sobre a qual será feito a busca; 3) restrições a cerca de quais registros
devem ser retornados (opcional). Neste trabalho, o terceiro item é restrito a uma forma limitada para o WHERE. A subcláusula WHERE é a responsável por delimitar quais registros devem
ser retornados, sempre baseado unicamente nos valores das chaves (denominadas de chaves
primárias). O UPDATE é responsável por atualizar valores de certos registros em uma dada
tabela. Esta cláusula é divida da mesma forma que o SELECT, porém os registros definidos
serão atualizados ao invés de listados.
Para realizar um INSERT precisamos saber (nesta ordem): 1) o nome da tabela que será
manipulada; 2) nomes dos campos que terão algum valor; 3) valores para os campos especificados. Dessa forma, para inserir uma nova entrada na Árvore B+ , criamos um novo registro
no mesmo formato daquele definido durante a criação da tabela mas possivelmente deixamos
de preencher alguns campos e/ou utilizamos outra ordem. A inserção finaliza com a criação
de uma nova folha na Árvore B+ da tabela sob operação.
O DELETE, como o nome diz, remove registros criados por INSERTs. Para este trabalho, é
obrigatório o uso do WHERE para delimitar os registros a serem removidos.
Minha primeira tabela
Para por em prática os conceitos, vamos considerar a criação de uma tabela que tem registros
a cerca de países. Essa tabela é criada com a cláusula
CREATE TABLE country (id INTP, short TEXT, name TEXT);
definindo que a tabela tem 3 colunas: id que é um inteiro e é a chave da tabela, short e name
que são do tipo TEXT. Agora, vamos inserir 3 registros nesta tabela:
INSERT INTO country (short, name, id) ("BR", "Brazil", 76);
INSERT INTO country (name, short, id) ("Bahamas", "BH", 44);
INSERT INTO country (id, short, name) (1000, "YT", "Mayotte");
Neste momento, a Árvore B+ desta tabela tem 3 folhas com chaves 44, 76 e 1000. Cada
uma destas folhas leva ao conteúdo do registro que foi criado durante cada INSERT. Para buscar
esses registros, utilizamos a cláusula SELECT. Se desejamos encontrar os nomes dos países com
id entre 30 e 50 é feito um
SELECT (name) FROM country WHERE id IN 30..50;
6
que resulta em
+---------+
| name
|
+=========+
| Bahamas |
+---------+
Para atualizar o nome de algum país, utilizamos a cláusula UPDATE. Por exemplo, se queremos mudar o nome de “Brazil” para “Brasil”, fazemos o seguinte:
UPDATE country (name) ("Brasil") WHERE id IN 76..76;
para verificar a alteração podemos utilizar a cláusula DUMP que produz
1 tabela
3 linhas
0 deletes, 1 update, 1 select
country
+------+-------+---------+
| id
| short | name
|
+======+=======+=========+
| 44
| BH
| Bahamas |
+------+-------+---------+
| 76
| BR
| Brasil |
+------+-------+---------+
| 1000 | YT
| Mayotte |
+------+-------+---------+
A última operação que é possível fazer é a remoção de registros. No caso, se desejarmos
remover todas as entradas precisamos saber o valor mínimo e máximo das chaves na tabela.
Neste exemplo podemos fazer a operação seguinte:
DELETE FROM country WHERE id IN -1..1500;
seguido de um DUMP para visualização:
1 tabela
0 linhas
3 deletes, 1 update, 1 select
country
+------+-------+---------+
| id
| short | name
|
+======+=======+=========+
Repare que muitas chaves não existem entre −1 e 1500, portanto elas são ignoradas.
7