“Programming is the art of telling another human being what one wants the computer to do.”

Donald Knuth

18 - Banco de Dados

18.1 - Modelo de Dados.

Dados são valores resultantes de medições ou observações que atribuímos a objetos abstratos ou concretos. Quando adicionamos contexto a um dado, temos informação. Por exemplo, o dado 31/02/2023 é um valor que podemos identificar como uma data, mas é inválida, ou seja, é uma informação dentro do contexto de registro de tempo (dia, mês e ano). Entretanto, a interpretação depende do agente analisando o dado.

Uma forma de organizar valores coletados é por tipo, isto é, agrupar tipos de dados de acordo com símbolos utilizados, intervalos válidos, restrições, etc... Quando falamos de idades de humanos, por exemplo, podemos utilizar o tipo inteiro com limites entre 0 e 150. O nome de uma pessoa exige letras do alfabeto e espaços, com limite de até 200 caracteres em casos comuns (lembra do nome inteiro de Dom Pedro II?).

As informações coletadas de medições ou observações normalmente estão relacionadas entre si e podem ser arranjadas em diagramas, tanto para facilitar a visualização quanto para organizar e planejar futuras análises. Um modelo de dados então é uma representação visual dos valores (dados) e suas relações. Os tipos de modelos de dados são:

  • Modelos conceituais
  • Modelos lógicos
  • Modelos físicos

Modelos conceituais são representações abstratas e permitem análises em alto nível, sem entrar em detalhes de implementação, tipos e relacionamentos.

Modelos lógicos são uma evolução de um modelo conceitual, expondo relações mais claras entre os elementos e alguns atributos relevantes dos valores, mas sem definir uma implementação específica da estrutura. As operações podem ser organizadas em APIs para posterior programação.

Modelos físicos detalham todas as informações dos objetos e seus relacionamentos para a criação do banco de dados na ferramenta escolhida. Os tipos devem ser especificados conforme as instruções do manual do sistema, assim como as restrições e validações de cada campo.

Uma base de dados pode ser representada como uma tabela, onde as colunas determinam as variáveis de um registro e as linhas o registro em si. Uma base de dados pode ser uni, bi ou multivariada, com relação à quantidade de variáveis envolvidas. Por ex:

Nome CPF Idade
João Ferreira 123.321.456-56 32
Maria Pereira 333.512.490-01 19

Na tabela acima notamos que há dois registros e as variáveis são Nome, CPF e Idade.

18.2 - Modelagem e Projeto de Banco de Dados.

Quando começamos a organizar os dados coletados previamente eles podem ser estruturados de um modo mais amigável ao usuário ou à máquina. Alguns tipos de estrutura são: imagens, textos, grafos, tabelas, listas, etc... Dados podem ser estruturados em basicamente três formatos:

Dados Estruturados: Os dados estruturados são organizados de maneira predefinida, seguindo um esquema rigoroso. Eles são representados em tabelas com linhas e colunas, onde cada coluna tem um tipo de dado específico. Essa estrutura facilita a pesquisa, a análise e a consulta dos dados usando linguagens de consulta, como SQL. Exemplos comuns de dados estruturados incluem informações em bancos de dados relacionais, como registros de clientes em uma loja online, onde cada campo, como nome, endereço e número de telefone, é claramente definido.

Dados Semi-Estruturados: Os dados semi-estruturados estão em algum ponto intermediário entre os dados estruturados e não estruturados. Eles não seguem um esquema rígido como os dados estruturados, mas ainda têm alguma estrutura, muitas vezes representada em formato de árvore, grafo ou documentos hierárquicos. Um exemplo comum de dados semi-estruturados são os documentos XML ou JSON, amplamente usados em aplicações web e na troca de dados entre sistemas. Eles permitem flexibilidade na representação de informações, tornando-os ideais para contextos onde os requisitos de dados podem evoluir.

Dados Não Estruturados: Os dados não estruturados são o oposto dos dados estruturados. Eles não têm uma organização formal e não seguem um esquema específico. Em vez disso, são frequentemente representados como texto corrido, áudio, vídeo, imagens e outros formatos não organizados. Embora sejam desafiadores de analisar diretamente, os dados não estruturados contêm informações valiosas. Por exemplo, redes sociais estão repletas de dados não estruturados, incluindo postagens de usuários, imagens e vídeos, que podem ser usados para análises de sentimentos, detecção de tendências e muito mais.

Existem diversas modelos para criação de bancos de dados:

  • Hierárquica
  • Grafos
  • Tabelas / Relacional
  • Orientada à objetos
  • Dimensional
  • Redes
  • Documentos

No modelo hierárquico utilizamos uma estrutura semelhante a uma árvore para organizar as relações, onde certos objetos tem ordem de prioridade sobre os demais, como um tipo de escala de valor ou subordinação. Exemplos: Registro do Windows.

Grafos relacionam os dados sem hierarquia, onde todas as entidades estão no mesmo patamar, sem regras de pai / filho. São muito úteis para modelar relações complexas e redes. Exemplos: Neo4j e Amazon Neptune.

O modelo relacional é muito utilizado para visualizar e formar relações entre tabelas em uma base de dados. As tabelas se relacionam através de chaves representando valores em outras tabelas de referência. Tabelas têm esquemas e estrutura estável, facilidando a eficiência e análise de dados. Exemplos: MySQL, SQL Server, PostgreSQL.

Na programação Orientada à Objetos, interfaces, classes e objetos se relacionam entre si através de referências em propriedades e métodos. Exemplos: ObjectDB.

A modelagem dimensional permite pensar no armazenamento de dados e recuperação eficiente, além de processos de backup, redundância e distribuição.

O modelo de documentos é um tipo de extensão ao modelo orientado à objetos, onde normalmente se utiliza de dados semi-estruturados, que podem ser nos formatos JSON e XML. Exemplos: MongoDB.

Bancos de dados são estruturas de armazenamento de dados que tem algum tipo de relacionamento entre si, normalmente pertecentes a um domínio de negócio ou pesquisa. Os bancos de dados são compostos de arquivos que podem ser centralizados ou distribuídos e provêm métodos mais eficientes de armazenamento, extração e pesquisa.

As boas práticas de modelagem de sistemas relacionais são chamadas de formas normais ou normalização. São caracterizadas por regras para evitar falhas na construção de tabelas. Evita, por exemplo, redundância de dados e separação incorreta de responsabilidades nos relacionamentos.

A indexação é uma técnica fundamental em sistemas de bancos de dados que melhora significativamente o desempenho de consultas e operações de pesquisa em grandes conjuntos de dados. Ela envolve a criação de estruturas de dados adicionais para acelerar o acesso e a recuperação de registros de dados com base em critérios específicos, como valores de colunas ou termos de pesquisa. A indexação é amplamente utilizada em sistemas de bancos de dados para otimizar a eficiência das consultas. A indexação envolve a criação de estruturas de dados, conhecidas como índices, que armazenam informações sobre os dados do banco de dados de uma maneira otimizada para buscas. Os índices geralmente são criados com base em colunas específicas de uma tabela, e cada entrada do índice contém um valor de coluna e uma referência ao local do registro de dados correspondente.

Existem vários tipos de índices, incluindo índices simples, índices compostos, índices de texto completo, e índices espaciais, entre outros. Cada tipo é projetado para otimizar a recuperação de dados com base em diferentes tipos de critérios de consulta. Por exemplo, índices de árvores B são frequentemente usados para indexar valores numéricos ou alfanuméricos, enquanto índices de texto completo são usados para pesquisas de texto livre.

Alguns algoritmos, estruturas de dados e técnicas comuns para organizar e operar em dados são:

  • Árvores B ou B+: Para leitura e escrita, mas especialmente para indexação.Utiliza uma estrutura de árvore balanceada muito eficiente para grandes volumes de dados.
  • Tabelas hash (função de dispersão): Tem complexidade $O(1)$ para pesquisa, sendo extremamente eficiente na busca de dados e armazenamento. Ela é usada para transformar dados em uma sequência de números ou em uma representação fixa, chamada de valor de dispersão ou código hash. Essa representação é calculada com base em um algoritmo matemático. Um desafio na utilização de funções de dispersão é o potencial de colisões, onde duas entradas diferentes geram o mesmo valor de dispersão. As implementações de funções de dispersão devem lidar com colisões de forma eficaz, normalmente usando estratégias como encadeamento separado (chaining) ou endereçamento aberto (open addressing).
  • Cestos (buckets): Os cestos, também conhecidos como baldes ou buckets em inglês, são contêineres utilizados em estruturas de dados como tabelas de dispersão (hash tables) para organizar e acessar dados de forma eficiente. Eles são particularmente úteis para agilizar a busca e a recuperação de dados em tempo constante $O(1)$ quando se tem uma chave ou identificador conhecido. Cada cesto pode conter um ou mais itens de dados associados a uma chave ou valor específico. Por exemplo, imagine um banco de dados que armazena informações de clientes. Ao usar uma tabela de dispersão com cestos, você pode calcular rapidamente o cesto em que um cliente específico deve ser armazenado e acessar seus detalhes diretamente, sem a necessidade de percorrer a lista inteira de clientes.
  • Listas Invertidas: As listas invertidas são uma técnica frequentemente utilizada em sistemas de busca textual e recuperação de informações. Elas são especialmente úteis quando se deseja associar palavras-chave ou termos a documentos ou registros em um banco de dados. Nesse contexto, cada palavra-chave é mapeada para uma lista de documentos que a contêm. Isso permite que os sistemas de busca localizem rapidamente os documentos relevantes para uma consulta específica, evitando a necessidade de percorrer todo o conjunto de dados. Além disso, as listas invertidas podem ser usadas em indexação de texto, permitindo pesquisas de texto completo eficientes.
18.3 - Sistemas de Gerenciamento de Bancos de Dados (SGBD): Arquitetura, Segurança, Integridade.

Sistemas de gerenciamento de banco de dados (SGBDs) utilizam diversas técnicas para gerenciar operações em bancos de dados como consulta, atualização, inserção e exclusão, além de extrações diversas em formatos distintos dos utilizados nos arquivos originais. Originalmente eles resolveram o problema da descentralização entre arquivos de dados em várias máquinas de usuários e servidores, que não tinham um processo em comum para sincronia das mudanças, dependendo da troca de informações entre máquinas para serem atualizados.

SGBDs devem garantir a integridade dos dados armazenados, provendo consistência e estabilidade nas operações. A escabilidade também é um recurso importante visto que o crescimento das bases (número de registro e relacionamentos) é indefinido. SGBDs também gerenciam o acesso aos dados, através de usuários, controlando diferentes tipos de permissões e processos de auditoria.

Com relação à arquitetura, o SGBD é considerado um intermediário entre o usuário e os arquivos de dados. Há dois principais contextos de gerenciamento de dados:

  • OLTP (Online Transaction Processing): Utilizado com mais frequência, controla operações em pequenas partes do banco;
  • OLAP (Online Analytical Processing): Tem como uso principal a extração, análise e recuperação de dados.

Os sistemas do tipo OLTP tem como fundamento a transação, que é um conjunto de operações delimitadas em uma unidade de trabalho, que podem ser canceladas ou efetivadas (rollback e commit) ao final do processamento.

SGBDs devem lidar também com redundância de dados, acesso concorrente, arquivos distribuídos, backup, cache, etc.

A comunicação entre uma aplicação que deseja acessar os dados e o SGBD ocorre por um protocolo e uma porta. Um usuário conecta sua aplicação ao banco de dados normalmente utilizando login, senha e instância que deseja conectar. Uma instância pode ter uma ou mais bases de dados e suas próprias configurações de segurança, backup, discos, logs, etc...

Integridade e Consistência

Do ponto de vista de leitura e gravação, há uma técnica de cache para páginas de disco em buffers, na memória principal do SGBD. Podem ser gravadas de volta no disco quando necessário, observando dois parâmetros que ficam em uma tabela principal: bit sujo e bit preso-solto. O primeiro controla se o dado em buffer foi modificado enquanto o segundo indica se pode ou não usar a informação no momento para gravá-la em disco. Ao esvaziar o buffer, o SGBD pode sobrescrever o item original (atualização local) ou criar uma nova versão (sombreamento). A atualização local depende de um mecanismo para recuperação em caso de erro, ou seja, um log que possa ser consultado. Esse mecanismo é chamado de WAL, write-ahead logging.

A ideia fundamental por trás do Write-Ahead Logging é que, antes de realizar qualquer modificação nos dados de um banco de dados, as informações sobre essa modificação são registradas em um log de transações (o log WAL). Essas informações incluem os detalhes da transação, como as operações que serão realizadas e os dados afetados. Esse registro ocorre antes das mudanças efetivas serem aplicadas aos dados no armazenamento principal.

O uso do Write-Ahead Logging também pode melhorar o desempenho em comparação com a gravação direta dos dados. Isso ocorre porque o log de transações pode ser gravado de maneira mais eficiente, já que as gravações podem ser feitas sequencialmente, e as operações de leitura e gravação nos dados principais podem ser otimizadas.

Normalmente quando há atualização de um registro, o SGBD precisa recuperar o bloco de tamanho fixo que contém o dado do disco rígido, bloqueá-lo de alteração por outras ferramentas, executar a mudança e liberar o bloco.

As regras steal / no-steal controlam quando uma transação está efetivada e o dado do cache pode ser enviado ao disco. No caso de force / no-force, são regras para obrigar a atualização das páginas do cache para o disco mesmo sem transação confirmada.

Um tipo de log importante no SGBD é o de checkpoint, que salva a lista de transações ativas periodicamente. O checkpoint fuzzy melhora o desempenho do SGBD porque não suspende as transações enquanto o checkpoint é executado. O rollback é a reversão das operações de uma transação.

Acesso e Segurança

Mecanismos de controle de acesso são componentes fundamentais dos SGBDs, que visam regular o acesso e a manipulação de dados para garantir a segurança e integridade dos dados. Dois modelos proeminentes de controle de acesso são o Controle de Acesso Discricionário (DAC) e o Controle de Acesso Obrigatório (MAC), cada um com características e propósitos distintos.

Controle de acesso discricionário (Discretionary Access Control=DAC):
Concentra-se em conceder aos usuários o poder de controlar o acesso a seus próprios recursos. Em um modelo DAC, os indivíduos que possuem ou criam um recurso têm autoridade para determinar quem pode acessar ou modificar esse recurso. Cada recurso, como uma tabela, arquivo ou registro, está associado a uma lista de controle de acesso (ACL) que especifica os usuários ou grupos com permissão para executar ações específicas, como ler, gravar ou excluir. O DAC é comumente usado em cenários em que os usuários têm um nível de confiança entre si e podem exercer responsabilidade sobre seus próprios dados.

Uma das vantagens do DAC é sua flexibilidade, pois permite que os usuários gerenciem seus dados sem a necessidade de intervenção constante dos administradores. No entanto, a desvantagem é que às vezes pode levar a riscos de segurança se os usuários não forem diligentes em definir as permissões apropriadas. O acesso não autorizado pode ocorrer se os usuários atribuirem direitos de acesso impróprios acidentalmente ou maliciosamente.

Em SQL, os comandos utilizados para prover acesso e revogá-los são: GRANT e REVOKE. É possível permitir que um usuário que recebeu a permissão de acesso ao recurso propague-a para outro usuário (WITH GRANT OPTION), criando uma cadeia de relações de segurança. Caso o primeiro usuário que recebeu a permissão perca seu acesso, pode-se configurar para que todos os outros beneficiários também percam seus acessos.

Controle de acesso obrigatório (Mandatory Access Control=MAC):
Opera com um princípio diferente, focando na aplicação de uma política de acesso pré-definida e rígida. Em um modelo MAC, os dados são classificados em diferentes níveis de sensibilidade e os usuários recebem níveis de autorização. Os usuários podem acessar os dados somente se seu nível de autorização for igual ou superior ao nível de confidencialidade dos dados. A decisão de conceder ou negar acesso é determinada por políticas de todo o sistema, e não pelo critério de usuários individuais.

O objetivo do MAC é estabelecer um modelo de segurança forte adequado para ambientes onde a confidencialidade e integridade dos dados são fundamentais, como aplicações militares ou governamentais. Ao impor uma hierarquia estrita de níveis de acesso, o MAC ajuda a evitar vazamentos de dados e modificações não autorizadas. No entanto, o MAC também pode ser menos flexível e mais complexo de administrar em comparação com o DAC. É baseado no modelo Bell-LaPadula para impor classificações aos objetos. Diferentes usuários, por exemplo, podem enxergar apenas certos registros em uma tabela. A presença de objetos que aparentam ter valores diferentes para usuários com diferentes passes (permissões) é chamada de Poli-Instanciação. Por exemplo, considere um banco de dados de funcionários em uma organização governamental. A poli-instanciação permitiria que os dados de um funcionário fossem representados em várias instâncias, cada uma com diferentes níveis de classificação de segurança. Dessa forma, os dados não classificados ou públicos podem coexistir com informações altamente confidenciais na mesma tabela, enquanto cada usuário ou grupo de usuários acessa apenas as instâncias relevantes para sua autorização. Quando as tuplas podem ser armazenadas com nível de classificação maior e dela são produzidas tuplas correspondentes com nível menor, falamos do processo de Filtragem. Por exemplo, em um sistema de gerenciamento de saúde, a filtragem pode ser usada para garantir que apenas profissionais de saúde autorizados tenham acesso a informações médicas confidenciais de pacientes. As políticas de filtragem podem restringir o acesso com base em critérios como função, departamento ou autorização legal.

18.4 - Concorrência, Recuperação após Falha, Gerenciamento de Transações.

Quando uma ou mais transações tentam acessar o mesmo recurso para operações de leitura ou gravação o SGBD precisa ter mecanismos para organizar esses acessos. Essa coordenação tem como base o princípio ACID: Atomicidade, Consistência, Isolamento e Durabilidade.

  • Atomicidade (A - Atomicity): A atomicidade garante que uma transação seja tratada como uma unidade indivisível. Isso significa que todas as operações dentro de uma transação são executadas com sucesso ou nenhuma delas é executada. Se uma parte da transação falhar, todas as alterações são revertidas (rollback).
  • Consistência (C - Consistency): A consistência garante que uma transação leve o banco de dados de um estado válido para outro estado válido. Isso significa que todas as restrições e regras de integridade definidas no banco de dados devem ser mantidas após a conclusão de uma transação. Se uma transação violar qualquer regra de integridade, ela será revertida.
  • Isolamento (I - Isolation): O isolamento controla a concorrência entre transações simultaneas. Ele garante que uma transação não veja ou afete o trabalho de outras transações até que todas as transações estejam concluídas. Isso evita problemas como leituras sujas, leituras não repetíveis e escritas fantasmas.
  • Durabilidade (D - Durability): A durabilidade garante que as alterações realizadas em uma transação sejam permanentes e não sejam perdidas, mesmo em caso de falhas do sistema, como panes de energia. Os dados modificados em uma transação são gravados de forma persistente no armazenamento antes que a transação seja confirmada.

As técnicas principais para o controle de objetos são o bloqueio exclusivo e compartilhado. No primeiro, somente uma transação tem acesso ao recurso, enquanto as outras ficam aguardando. No segundo, operações de leitura podem ser efetuadas no objeto em concorrência.

Uma recuperação de falha é o processo de restaurar um banco de dados para um estado anterior ao problema, ou seja, um momento de consistência da estrutura antes da falha ter ocorrido.

Isso é possível através de backups ou recuperação de registros através de logs, pelas seguintes técnicas:

  • Atualização adiada: utiliza o algoritmo NO-UNDO/REDO, onde o BD só atualizado fisicamente depois que a transação é efetivada. Enquanto isso, as informações são registradas em buffers ou espaço de local de trabalho. Também há gravação de log. O procedimento RAA_M com checkpoint usa 2 listas de transações, confirmadas e ativas, e executa o REDO. O RAI_M também usa 2 listas, confirmadas e ativas, mas executa o UNDO e as operações WRITE_OP são percorridas na ordem inversa de que foram gravadas no log. Depois executa-se o REDO da operação.
  • Atualização imediata: atualiza o BD assim que determinadas operações são executadas, antes que a transação seja efetivada. As atualizações devem ser registradas em disco antes da confirmação da transação. O resultado da recuperação deve espelhar a execução inicial da transação.
  • ARIES (Algorithms for Recovery and Isolation Exploiting Semantics): É um algoritmo de recuperação usado em grandes SGBDs. Usa a técnica steal / no-force para gravar páginas em disco e minimiza o trabalho de recuperação através de processos incrementais em caso de falha na recuperação. Tem como base 3 conceitos: Write-Ahead Logging, Histórico repetitivo e logging quando acontece o UNDO. É divido em fases : Análise, REDO e UNDO.
  • Paginação de sombra: Grava diferentes versões do mesmo arquivo em banco e mantém controle do ativo.

Uma transação pode ser definida como uma unidade de execução que acessa e/ou atualiza um ou vários itens de dados. Sempre que usamos transações precisamos lidar com recuperação de falhas e concorrência, ou seja, o que fazer quando problemas acontecem durante a execução da transação e como controlar múltiplas transações simultaneamente.

Em um modelo de transação temos duas operações:

  • READ_ITEM(x) : Leitura de um item de dado X para ser armazenado em variável.
  • WRITE_ITEM(x) : Escreve de uma variável para item de dados no banco.

O banco de dados utiliza um conjunto de buffers para agilizar e otimizar o acesso aos dados, sem precisar acessar a todo momento as tabelas para escrita e leitura.

Para organizar a execução das transações, os SGBDs utilizam o método de escalonamento, que provê uma sequência de instruções em ordem para a execução simultânea das transações e deve preservar a ordem das instruções em cada transação individual. Quando uma transação é executada com sucesso, a instrução COMMIT é a última operação. Em caso de falha e não conclusão, a última instrução é ABORT. Nesse último caso, as alterações devem ser desfeitas para deixar o banco de dados em um estado consistente. O escalonamento é construído pelo Sistema Operacional.

Tipos de escalonamento:

  • Serial: Todas as transações não são executadas simultaneamente, ou seja, execução das instruções em série (uma após a outra). Dadas as transações $T_1, T_2$, onde $T_1$ é executada primeiro e depois $T_2$, ou vice-versa.
  • Não serial: As transações são executadas simultaneamente. A vantagem é explorar a concorrência, preservando as ordem corretas de operações.

Um escalonamento é dito serializável se cada transação preserva individulamente a consistência do banco de dados, ou seja, é equivalente ao escalonamento serial. Há dois tipos de serializabilidade: por conflito e por visão. Quando há um conflito entre uma instrução $a_i$ de uma transação $T_i$ e uma instrução $a_j$ de uma transação $T_j$, ou seja, uma tentou ler e a outra escrever (ou vice-versa) ou as duas estão tentando escrever ao mesmo tempo, temos uma ordem temporal (lógica) entre eles.

A serialização por conflito é tal que, se S pode ser transformado em S' por uma série de trocas na ordem das instruções que não são conflitantes, dizemos que S e S' são equivalentes por conflitos.

Um grafo de precedência é um grafo dirigido utilizado para organizar as informações de conflito entre $n$ transações, $T_1, T_2, ..., T_n$, onde os vértices são transações e os arcos, por ex, de $T_i$ para $T_j$, indica que $T_i$ acessou o dado primeiro que $T_j$. O rótulo do arco indica o item de dados onde o conflito ocorreu. Se o grafo for acíclico, o escalonamento é serializável.

Quando um escalonamento é dito recuperável, uma transação $T_j$ que usa dados escritos por uma transação $T_i$, o COMMIT de $T_i$ deve ter ocorrido antes do COMMIT de $T_j$, caso contrário, o escalonamento é dito não recuperável.

Um rollback em cascata ocorre quando uma falha em uma transação $T_i$ afeta transações dependentes, $T_{i+j}$, causando uma sequência de instruções de ABORT. Esse processo deve ser evitado.

Algumas aplicações podem lidar com níveis fracos de consistência dos dados para desempenho, usando escalonamentos não serializáveis. Em bancos tipo SQL, a serializabilidade é ativada por padrão.

18.5 - Linguagens de Consulta.

A principal linguagem utilizada para manipular dados em SGBDs, no caso relacional, é a SQL (Structured Query Language). Cada SGBD pode implementar sua versão do SQL, como por exemplo a T-SQL da Microsoft ou a PL/SQL da Oracle. Os comandos SQL podem ser agrupados em diferentes tipos como o DML (Data Manipulation Language), DDL (Data Definition Language), DQL (Data Query Language), DTL (Data Transaction Language), DCL (Data Control Language), etc...

  • A Linguagem de Manipulação de Dados (DML) é usada para realizar operações de modificação nos dados armazenados no banco de dados. Isso inclui inserir novos registros, atualizar dados existentes e excluir registros. Exemplos de comandos DML incluem INSERT, UPDATE e DELETE. A DML permite que os aplicativos interajam com os dados, alterando seu conteúdo de acordo com as necessidades.
  • A Linguagem de Definição de Dados (DDL) é usada para definir e gerenciar a estrutura do banco de dados. Isso inclui a criação de tabelas, índices, restrições e outros objetos do banco de dados. Exemplos de comandos DDL incluem CREATE TABLE, ALTER TABLE e DROP TABLE. A DDL permite que os administradores de banco de dados configurem e personalizem o esquema do banco de dados.
  • A Linguagem de Consulta de Dados (DQL) é usada para consultar e recuperar dados do banco de dados. O principal comando DQL é o SELECT, que permite que os usuários recuperem informações específicas de uma ou várias tabelas. A DQL é amplamente utilizada por aplicativos e sistemas para obter dados relevantes para análise ou exibição.
  • A Linguagem de Transação de Dados (DTL) é usada para controlar transações em bancos de dados. As transações são unidades de trabalho que envolvem uma ou mais operações DML. Comandos DTL, como BEGIN TRANSACTION, COMMIT, e ROLLBACK, permitem que os desenvolvedores controlem a execução de várias operações DML como uma única unidade atômica.
  • A Linguagem de Controle de Dados (DCL) é usada para gerenciar as permissões de acesso aos dados no banco de dados. Comandos DCL, como GRANT e REVOKE, permitem que os administradores de banco de dados concedam ou revoguem direitos de acesso a usuários ou grupos de usuários. A DCL é fundamental para garantir a segurança dos dados e controlar quem pode executar quais operações no banco de dados.

Em sistemas tipo NoSQL, altamente flexíveis e sem relacionamentos por chaves, os dados podem ser representados em padrões distintos. Esse tipo de arquitetura pode facilitar em muito o processo de desenvolvimento, evitando longos períodos de modelagem e a construção de objetos de manipulação. Além disso, é altamente escalável. Há quatro tipos principais de bases NoSQL:

  • Documento
  • Pares Chave-Valor
  • Colunas
  • Grafos

Documentos armazenam dados no formato JSON, BSON, XML, etc... Há possibilidade de indexação de dados, facilitando a busca. A grande vantagem é a maior eficiência na serialização e deserialização de objetos pela aplicação, já os registros são retornados em um formato muito parecido do pelo utilizado no sistema.

A estrutura chave-valor é bem simples, onde um atributo possui um nome (chave) e o valor associado.

No tipo colunas, os registros são organizados por linhas e colunas previamente especificadas, facilitando a organização, mas podem perder performance pela forma de armazenamento dos dados em disco de forma não contígua.

No caso de estrutura de grafo, há ponteiros que podem ser utilizados para percorrer os nós, tendo uma implementação totalmente diferente das consultas em SQL.

Álgebra e cálculo relacional são dois pilares teóricos fundamentais no estudo e na implementação de sistemas de gerenciamento de banco de dados relacionais. Ambos fornecem uma base formal para operações e consultas em bancos de dados, mas fazem isso de maneiras ligeiramente diferentes. Entender esses conceitos é crucial para quem deseja aprofundar-se em bancos de dados e otimizar o desempenho das consultas.

Álgebra Relacional

A álgebra relacional é um sistema de operações que são aplicadas a um ou mais relações (tabelas) de um banco de dados para produzir outra relação como resultado. É uma linguagem procedural, o que significa que o usuário especifica o que deseja obter (o resultado) e também como obter esse resultado (os passos ou operações). As operações básicas da álgebra relacional incluem:

  • Seleção (σ): Filtra as linhas de uma relação que satisfazem uma condição especificada.
  • Projeção (π): Extrai colunas específicas de uma relação, removendo duplicatas.
  • União (∪): Combina as linhas de duas relações, removendo duplicatas.
  • Diferença (-): Retorna as linhas que estão em uma relação, mas não na outra.
  • Produto Cartesiano (×): Combina cada linha de uma relação com cada linha de outra.
  • Junção (⨝): Combina linhas de duas relações baseadas em uma condição de correspondência.

Essas operações permitem a manipulação de dados de maneiras complexas, possibilitando a realização de consultas sofisticadas.

Cálculo Relacional

Por outro lado, o cálculo relacional oferece uma perspectiva não procedural para a manipulação de bancos de dados. Ele se concentra em descrever o que resultado se deseja obter, sem especificar como realizar a operação. Existem duas variantes principais do cálculo relacional:

  • Cálculo Relacional de Tuplas (TRC): Usa variáveis que representam tuplas de uma relação. As consultas são formuladas especificando propriedades que essas tuplas devem satisfazer.
  • Cálculo Relacional de Domínio (DRC): Usa variáveis que representam elementos de domínios de atributos de relações. As consultas definem condições sobre os valores desses domínios.

Ambas as variantes permitem expressar consultas de maneira declarativa, focando no "o quê" em vez de no "como". Isso proporciona uma abordagem mais abstrata e, frequentemente, mais intuitiva para definir consultas, especialmente aquelas de natureza mais complexa.

Suponha que temos duas tabelas em um banco de dados relacional: Funcionarios e Departamentos:

  • Funcionarios tem as colunas FuncionarioID, Nome, DepartamentoID.
  • Departamentos tem as colunas DepartamentoID, NomeDepartamento.
Exemplo 1: Seleção

Para encontrar todos os funcionários que trabalham no departamento de TI, podemos usar a operação de seleção:

$$ \sigma_{\text{NomeDepartamento='TI'}} \text{Departamentos} $$ Exemplo 2: Junção

Para listar o nome de cada funcionário junto com o nome de seu departamento, usamos a operação de junção:

$$ \text{Funcionarios}_{\Join \text{Funcionarios.DepartamentoID=Departamentos.DepartamentoID}} \text{Departamentos} $$

Isso retorna uma tabela combinada onde cada funcionário está alinhado com seu respectivo departamento.

Para os mesmos exemplos acima, vamos ver como eles seriam expressos em cálculo relacional.

Exemplo 1: Cálculo Relacional de Tuplas (TRC) para Seleção

Para encontrar funcionários do departamento de TI, a consulta em TRC seria algo como:

$$ \{f|f \in \text{Funcionarios} \land \exists \; d \in \text{Departamentos(d.DepartamentoID = f.DepartamentoID} \land \text{ d.NomeDepartamento = "TI")}\} $$

Isso seleciona as tuplas $f$ de Funcionarios onde existe uma tupla $d$ em Departamentos tal que o DepartamentoID é o mesmo e o NomeDepartamento é "TI".

Exemplo 2: Cálculo Relacional de Domínio (DRC) para Junção

Para listar o nome de cada funcionário com o nome de seu departamento, a expressão em DRC pode ser:

$$ \{ \text{(f.Nome,d.NomeDepartamento)} \;∣\; f\in \text{ Funcionarios,d } \in \text{ Departamentos,f.DepartamentoID=d.DepartamentoID } \} $$

Isso cria pares de Nome de Funcionarios e NomeDepartamento de Departamentos onde os DepartamentoID correspondem.

18.6 - Bancos de Dados Distribuídos.

A organização mais simples de uma arquitetura de sistemas com persistência em disco é quando o banco de dados reside na mesma máquina que a aplicação, ou seja, todos os processos se comunicam através do mesmo sistema operacional e hardware. Há diversas vantagens e problemas com essa abordagem, principalmente do ponto de vista de eficiência no processamento, redundância, controle de acesso simultâneo, etc... Porém, é muito mais fácil de configurar e utilizar em operações simples. Em sistemas embarcados, onde há necessidades de economizar espaço e processamento, o SGBD é normalmente acoplado ao mesmo ambiente da aplicação.

No modelo de duas camadas, a aplicação e o banco de dados ficam em máquinas separadas. Esse é modelo cliente-servidor. Essa é a estrutura distribuída mais simples e os servidores devem se conectar utilizando protocolos de rede. O SGBD monitora a porta que vai receber e enviar o resultado das operações requisitadas. O isolamento da base de dados em um servidor próprio é uma arquitetura muito comum.

No caso da arquitetura em três camadas, parte do código fica na máquina do cliente, outra fica em um servidor de aplicação e o banco de dados em um terceiro computador. A primeira camada é chamada de apresentação, a segunda de lógica de négocio e a terceira de serviços de bancos de dados. A separação das camadas provê maior eficiência de processamento, uso de memória e disco, isolamento, segurança, etc..., mas aumenta os custos de manutenção e monitoria de modo relevante.

Com o aumento da complexidade e o risco de se manter os dados em um único servidor, bancos de dados distribuídos surgiram como uma alternativa. Há vários métodos para distribuir os dados e facilitar o acesso, incluindo réplicas e algoritmos de acesso e manipulação. As máquinas podem compartilhar uma memória e reter partes do dado requisitado. Outra arquitetura comum é compartilhar um disco entre as máquinas.

O modelo mais novo e complexo é o de rede, onde o processamento e os dados estão distribuídos e há um coordenador para sincronizar quais máquinas vão processar quais partes dos registros para síntese no computador principal.

Com o advento do Big Data, volumes massivos de dados coletados de diferentes dispositivos, novas formas de organizar e operar os registros foram criadas, principalmente utilizando modelos distribuídos, onde clusters se comunicam em regiões diferentes do planeta, exigindo algoritmos complexos para coordenar diferentes servidores e estruturas de dados.

Os bancos de dados distribuídos são sistemas que armazenam dados em vários nós ou servidores interconectados em uma rede. Essa arquitetura é amplamente adotada em ambientes onde a escalabilidade, a disponibilidade e a tolerância a falhas são cruciais. No entanto, gerenciar dados em um ambiente distribuído apresenta desafios significativos, o que levou ao desenvolvimento de técnicas avançadas de replicação, algoritmos de sincronização e protocolos de comunicação.

Replicação de Dados:

  • A replicação de dados é uma técnica essencial em bancos de dados distribuídos. Envolve a criação de cópias de dados em vários servidores ou nós da rede. Essas réplicas podem ser usadas para melhorar a disponibilidade e a capacidade de resposta do sistema, bem como para aumentar a tolerância a falhas.
  • Principais Técnicas de Replicação: Existem várias abordagens para replicação de dados, incluindo replicação síncrona, replicação assíncrona e replicação por demanda. A replicação síncrona garante que todas as réplicas sejam atualizadas antes que uma transação seja confirmada, enquanto a replicação assíncrona permite que as atualizações sejam propagadas posteriormente. A replicação por demanda envolve a replicação apenas quando necessário.

Algoritmos de Sincronização:

  • Sincronizar as réplicas de dados é crítico para manter a consistência e a integridade dos dados em um banco de dados distribuído. Algoritmos de sincronização, como o algoritmo de sincronização de relógio vetorial, o algoritmo de carimbo de data/hora e o algoritmo de controle de concorrência, garantem que as atualizações sejam aplicadas de maneira ordenada e consistente em todos os nós.

Protocolos de Comunicação:

  • Os protocolos de comunicação desempenham um papel vital na troca de dados entre os nós de um banco de dados distribuído. Protocolos como o TCP/IP são comuns para a comunicação entre nós, enquanto protocolos específicos de replicação, como o protocolo de replicação de bancos de dados MySQL, são projetados para garantir que as réplicas sejam mantidas atualizadas.

Acesso e Manipulação de Dados:

  • Para acessar e manipular dados em bancos de dados distribuídos, os sistemas devem oferecer suporte a consultas distribuídas, transações distribuídas e coordenação de acesso concorrente. Protocolos como o protocolo de transações distribuídas XA (eXtended Architecture) são usados para garantir a consistência das transações em ambientes distribuídos.
18.7 - Mineração de Dados.

Mais conhecido como Data Mining, é o processo de procurar padrões em uma vasta quantidade de dados. Há uma enorme discussão sobre o que é considerado "vasto", pelo termo Big Data, ou volumes massivos de dados, mas podemos assumir algo na ordem de petabytes ($10^{15}$ bytes). As técnicas para explorar os dados vem de algoritmos de inteligência artificial, principalmente redes neurais e estatística.

Alguns tipos de mineração de dados são:

  • Agrupamentos ou Clusterização
  • Hipóteses
  • Regras de Associação
  • Árvores de decisão / Classificação
  • Grafos
  • Dendrogramas (diagramas com hierarquia)
  • Redes Neurais
  • Séries Temporais

Um cluster é uma coleção de objetos similares dentro de um grupo ou diferentes em comparação com outro grupo. A análise de cluster é também chamada de segmentação de dados, ou seja, particionar os dados em grupos dadas certas características. É um tipo de aprendizado sem supervisão. Pode ser usado como processo intermediário na análise de dados, gerando um resumo para classificação, descoberta de padrões, etc... Também é útil na compressão, filtragem e redução de dados.

Em estatística, testes de hipóteses são métodos comuns de avaliar relações entre variáveis. Quando definimos que uma varíavel $x$ tem correlação com outra $y$, dizemos que quando $x$ varia (cresce ou diminui), $y$ também varia, de modo que podemos encontrar uma equação $y=f(x)$ que explica razoavelmente essa relação. A hipótese nula nos diz que não há relação entre $x$ e $y$ e podemos utilizá-la para avaliar se nosso modelo explica ou não as variações entre $x$ e $y$, ou seja, a hipótese alternativa. Técnicas em variáveis aleatórias devem ser estudadas para descartar ruídos, chamados de "correlações espúrias".

As regras de associação são utilizadas para descobrir padrões de relação entre eventos, não necessariamente causalidade, mas um indício de que quando A acontece, B também ocorre (ou o inverso). Do ponto de vista lógico, se $A$ é um evento e $B$ é outro, $A\Rightarrow B$ em $x$% dos casos. Para avaliar essa relação, dois parâmetros são utilizados: suporte e confiança. O primeiro revela a frequência de $A$ no conjunto total $T$ de transações. O segundo informa o percentual da relação entre $A$ e $B$. O algoritmo "Apriori" é utilizado para encontrar regras de associação em um conjunto de transações.

Classificadores são utilizados para identificar, a partir de determinados atributos, qual classe aquele valor pertence (mais provavelmente). Um algoritmo de classificação precisa de dados de treinamento para a construção do classificador. A acurácia do modelo vai determinar se seu uso será útil ou não. O método de árvores de decisão gera representações que facilitam a visualização das relações. Ele pode ser utilizado com fins de previsão ou descrição dos dados.

A mineração com grafos é muito utilizada para avaliar redes complexas, onde padrões são irregulares e, por isso, os dados semi-estruturados. Algoritmos apresentados anteriormente não são muito eficientes nesses casos. Grafos são objetos compostos de arestas e nós, indicando uma relação entre dois itens.

Séries temporais são relações entre uma variável ao longo de um período ou intervalo de tempo. O objetivo é identificar tendências que possam ser úteis na previsão de fenômenos. Pode-se identificar em uma série:

  • Estacionariedade: Quando parâmetros estatísticos não variam;
  • Sazonalidade: Valores flutuando em determinados pontos do tempo;
  • Autocorrelação: Relação indica função periódica.

Alguns modelos importantes em séries temporais são: ARIMA Box-Jenkins (médias móveis), Box-Jenkins (multivariados) e Holt-Winters.

O processo de avaliação dos padrões normalmente tem 3 passos:

  1. Geração do modelo
  2. Definição do padrão a ser buscado
  3. Validação