Bancos de Dados Temporais: Teoria e PráticaNina EdelweissInstituto de InformáticaUniversidade Federal do Rio Grande do SulE-mail: nina@inf.ufrgs.brResumoBancos de Dados Temporais permitem armazenar todos os estados de uma aplicação (presentes, passad os e futuros), registrando sua evolução com o passar do tempo. Informações temporais são associadas aos dados armazenados (tempo de transação e/ou tempo de validade) para identificá-los ao longo do tempo. Modelos de dados temporais são também utilizados nos processos de modelagem de aplicações, devido ao seu poder de representar não somente os aspectos estáticos da aplicação, mas também seus aspectos dinâmicos e sua evolução temporal. Neste curso serão apresentados conceitos básicos de modelagem temporal e de bancos de dados temporais, aspectos relativos a consultas sobre bancos de dados temporais, análise da evolução de esquemas conceituais quando forem utilizados bancos de dados temporais, diferentes formas de implementação e algumas aplicações onde dados temporais são fundamentais.AbstractThe whole temporal evolution of an application, including all the assumed states (past, present and future), can be available when Temporal Databases are used. The identification of data along time is made associating t emporal information to stored data (transaction and/or valid time). Temporal data models are also used in application modeling processes, due to their ability of representing not only the static aspects, but also the dynamic ones and the evolution of the application with time. The issues presented in this course include basic concepts of temporal modeling and temporal databases, temporal queries, and considerations about schema evolution in temporal databases, different implementation forms, and some applications that require temporal data.1 IntroduçãoA maior parte das aplicações atuais têm necessidade de manipular, de alguma maneira, informações históricas – dados relativos a estados passados da aplicação. Os SGBD convencionais, no entanto, não proporcionam suporte a estas informações. A necessidade de suprir esta lacuna fez com que nos últimos 20 anos muitas pesquisas tenham sido realizadas na área de Bancos de Dados Temporais, com o objetivo de definir conceitos e estratégias para tratar de informações históricas. Aspublicações destas pesquisas foram reunidas em diversas coletâneas debibliografias [Bolour 82, McKenzie 86, Stam 88, Soo 91, Kline 93, Tsotras 96, Wu 97].Bancos de Dados Temporais permitem armazenar todos os estados de uma aplicação (presentes, passados e futuros), registrando sua evolução com o passar do tempo [Clifford 95, Edelweiss 94, Jensen 97, Özsoyoglu 95, Tansel 93, Zaniolo 97]. Para que isto seja possível, informações temporais são associadas aos dados armazenados, identificando quando a informação foi definida ou o tempo de sua validade.A noção de tempo, como datas, períodos, duração de validade de informações, intervalos temporais, surge em diferentes níveis: (i) na modelagem de dados, (ii) na linguagem de recuperação e manipulação de dados, e (iii) no nível de implementação do SGBD.No presente curso serão abordados diversos aspectos relativos a Bancos de Dados Temporais. No capítulo 2 será feita uma breve apresentação de conceitos relativos a representação de informações temporais, sendo os diferentes tipos de Bancos de Dados Temporais apresentados no capítulo 3. O capítulo 4 apresenta algumas considerações a respeito de consultas realizadas sobre Bancos de Dados Temporais. Diferentes enfoques para modelos de dados temporais, base ados em modelos relacionais, E-R e orientados a objetos serão vistos no capítulo 5.A evolução do esquema conceitual com o passar do tempo é outro aspecto importante, necessário para a representação da evolução da aplicação que está sendo modelada. As implicações desta evolução quando se trabalha com Bancos de Dados Temporais são abordadas no capítulo 6. Alguns aspectos de implementação de BD Temporais são analisados no capítulo 7 e, para concluir, no capítulo 8 são analisadas algumas áreas de aplicação nas quais a utilização deste tipo de bancos de dados é importante.2 Conceitos de Representação TemporalEste capítulo tem por finalidade introduzir o leitor nos principais conceitos relativos à representação de aspectos temporais em bancos de dados. A forma de representação escolhida se reflete em interpretações diferentes dos conceitos temporais. As definições completas dos conceitos aqui apresentados podem ser encontradas em [Jensen 94], num glossário consensual de termos relativos a Bancos de Dados Temporais elaborado pela comunidade desta área através de uma discussão realizada através de correio eletrônico.2.1 Dimensão TemporalOs modelos de dados tradicionais apresentam duas dimensões, representando (1) as instâncias dos dados (linhas de uma tabela), e (2) osatributos de cada instância (colunas desta tabela). Cada atributo de umainstância apresenta um só valor. Se for feita uma alteração deste valor, o anterior é perdido. Por exemplo, se o atributo representa o salário de umfuncionário, o banco de dados somente armazena o último valor.Os modelos temporais acrescentam mais uma dimensão aos modelos tradicionais – a dimensão temporal. Esta dimensão associa alguma informação temporal a cada valor. Caso o valor de um atributo seja alterado, o valor anterior não é removido do banco de dados – o novo valor é acrescentado, associado a alguma informação que define, por exemplo, seu tempo inicial de validade. Todos os valores definidos ficam armazenados no banco de dados. No exemplo anterior, todos os valores do salário do funcionário ficam armazenados, cada um associado ao seu tempo de validade. Deste modo é possível acessar toda a história dos atributos, sendo possível analisar sua evolução temporal.2.2 Ordem no TempoA dimensão temporal é composta por uma seqüência d e pontos consecutivos no tempo, que recebe o nome de eixo temporal. A definição de uma ordem a ser seguida no tempo é fundamental quando utilizada alguma representação temporal. O mais comum é que se assuma que o tempo flui linearmente; isto implica em uma total ordenação entre quaisquer dois pontos no tempo. Em alguns casos pode ser considerado tempo ramificado ("branching time"). Para estes a restrição linear é abandonada permitindo a possibilidade de dois pontos diferentes serem sucessores (ramificação no futuro) ou antecessores (ramificação no passado) imediatos de um mesmo ponto. Uma ramificação no futuro implica que podem ser considerados múltiplos possíveis desenvolvimentos futuros do domínio (por ex., diferentes hipóteses da história futura), enquanto que uma ramificação no passado admite múltiplas histórias passadas do domínio em questão. A combinação "passado linear, futuro ramificado" trabalha com uma só história passada e admite múltiplas histórias futuras, representando desta maneira a realidade atual de uma forma bastante fiel. Uma última opção de ordenação temporal é considerar o tempo circular. Esta forma pode ser utilizada para modelar eventos e processos recorrentes.2.2.1 Tempo Totalmente OrdenadoA maior parte dos modelos temporais se baseia no t empo linearmente ordenado. A ordenação total do tempo pode ser definida com mais precisão através da teoria dos conjuntos, conforme mostrado a seguir [Antunes 97].Seja T o conjunto não vazio de todos os pontos do tempo. Por definição, T é um conjunto totalmente ordenado pela relação B EFORE (A NTES), a qual satisfaz à seguinte condição:∀t a, t b:t a, t b∈T∧t a≠t b→ (t a B EFORE t b∨t b B EFORE t a) Para que a relação B EFORE seja uma relação de ordem estrita total énecessário que possua as seguintes propriedades:Irreflexibilidade:∀t :t∈T→¬(t B EFORE t)Transitividade:∀t a, t b, t c:t a, t b, t c∈T ∧t a B EFORE t b∧t b B EFORE t c→t a B EFORE t cAssimetrias:∀t a, t b:t a, t b∈T∧t a B E FORE t b →¬(t b B EFORE t a)A relaçãoB EFORE é equivalente à relação “ < ” utilizada no âmbito dos números inteiros, sendo este operador muitas vezes utilizado pararepresentar a ordem temporal.2.3 Tempo Absoluto e Tempo RelativoOutro conceito importante é o que diferencia tempo absoluto de relativo. Tempo absoluto consiste de uma informação temporal que define um tempo específico, definido com uma granularidade determinada, associadoa um fato. Exemplo: Flávio nasceu no dia 30/08/73.Um tempo é relativo quando sua validade é relacionada à validade de outro fato, ou ao momento atual. Exemplo: o salário aumentou ontem; a loja abriu dois meses depois da abertura do Shopping.2.4 Variação TemporalDuas formas basicamente diferentes de variação temporal podem serconsideradas: tempo contínuo e tempo discreto. Supõe-se que o tempo é contínuo por natureza. Entretanto, sem grande perda de generalidade, o tempo pode ser considerado como discreto. Esta segunda forma de representação simplifica consideravelmente a implementação de modelos de dados.Modelos de dados que suportam uma noção discreta de variaçãotemporal são baseados em uma linha de tempo composta de uma seqüência de intervalos temporais consecutivos, que não podem ser decompostos, de idêntica duração. Estes intervalos são denominados chronons. A duração particular de um chronon não é necessariamente fixada no modelo de dados, podendo ser definida em implementações particulares do modelo de dados.Considerando variação temporal discreta, a definição de informações ao longo do tempo, sob ponto de vista de sua validade, pode ser feita das seguintes formas (Figura 2.1):• variação ponto a ponto – o valor definido vale somente no ponto temporal onde foi definido. Não existe valor válido nos pontos para os quais não foram definidos valores;• variação por escada – o valor fica constante desde o ponto em que foi definido até o instante em que outro valor seja definido. Corresponde,geralmente, à definição de valores em conseqüência da ocorrência de eventos (variação por eventos);• variação temporal definida por uma função – existe uma função que define os valores e que permite a interpolação para obter os valores nos pontos não definidos. Esta função de interpolação pode ser definida2.5 Granularidade TemporalA granularidade temporal de um sistema consiste na duração de um chronon. Entretanto, dependendo da aplicação considerada, às vezes é necessário considerar simultaneamente diferentes granularidades(minutos, dias, anos) para permitir uma melhor representação da realidade. Por exemplo, em um determinado segmento modelado, agranularidade pode ser diária (o chronon equivale a um dia), enquanto que em outro segmento a granularidade pode ser mensal. Embora o chronon do sistema seja único, é possível manipular estas diferentes granularidades através de funções e operações disponíveis nos sistemas gerenciadores do banco de dados que implementam o mode lo.2.6 Elementos Primitivos de Representação Temporal2.6.1 Instante no TempoO conceito de instante, representando um particular ponto no tempo, depende da forma de variação temporal considerada. Quando é considerado tempo contínuo, um instante é um ponto no tempo deduração infinitesimal. Neste caso os instantes são isomórficos com osnúmeros reais, o que significa que entre dois pontos do tempo sempre existe um outro ponto no tempo.Quando, no entanto, é considerada a variação temporal discreta, um instante é re presentado por um dos chronons da linha de tempo suportada pelo modelo. Na variação discreta, os instantes são isomórficos aos números inteiros ou a um subconjunto destes. Assim, entre dois pontos do tempo consecutivos não existe outro ponto do tempo. Diz-se que um evento ocorre no tempo t se ocorre em qualquer tempo durante o chronon representado por t. Um chronon, que é a menor duração de tempo suportada por um SGBD temporal, pertence à representação discreta de tempo.Considerando a ordem de variação temporal linear, temos a existênciade um instante especial, correspondente ao instante atual (now), o qual se move constantemente ao longo do eixo do tempo. Este ponto define o que é considerado como passado (qualquer ponto anterior a este) e como futuro (qualquer ponto posterior a ele).2.6.2 Intervalo TemporalUm intervalo temporal é caracterizado pelo tempo decorrido entre dois instantes – um subconjunto de pontos do eixo temporal. Depende também da forma de representação temporal definida no modelo. Quando é considerado tempo contínuo, o intervalo consiste de infinitos instantes de tempo. Na variação discreta um intervalo é representado por um conjunto finito de chronons consecutivos.É representado pelos dois instantes que o delimitam. Dependendo da pertinência ou não dos instantes limites ao intervalo este pode ser aberto (os limites não pertencem ao intervalo), semiaberto (um dos limites pertence ao intervalo) ou fechado (ambos os limites pertencem ao intervalo). Quando um dos limites é representado pelo instante atual (now) temos a representação de um intervalo particular cujo tamanho varia com a passagem do tempo.Um intervalo temporal é representado por [t1, t2], onde t1 é o primeiroponto do intervalo (limite inferior) e t2 é o último (limite inferior). O próprio eixo temporal T pode ser considerado um intervalo de tempo, identificado pela expressão [«, »], onde o símbolo « o instante temporal de início da contagem de tempo e o símbolo » representa o final. Para qualquer intervalo temporal, uma das duas fórmulas a seguir deve ser verdadeira:t1 < t2 ou t1 = t2.A segunda representa um intervalo cuja duração é exatamente um chronon.Um intervalo temporal também é totalmente ordenado pela relaçãoB EFORE, sendo possível, através dos operadores first e last [Clifford 88], extrair-lhe o primeiro e o último ponto de tempo. É o que se passa ademonstrar.Seja I, um intervalo de tempo e I⊆T, então:first ( I )é o elemento t∈I tal que, ∀t' ∈I:t B EFORE t' ∨t = t'last ( I )é o elemento t ∈I tal que, ∀t' ∈I: t' B EFORE t ∨t' = t Para que um conjunto de pontos do tempo seja realmente considerado um intervalo,é necessário que sejam consecutivos, isto é, não pode haver qualquer lacuna entre eles. Esta condição é formalmente representada pela expressão abaixo:Seja I⊆T um intervalo, então∀t a∈I:t a≠ last(I ) →∃t b ∈I: (t a B EFORE t b∧¬∃t c∈T: t a B EFORE t c ∧t c B EFORE t b )2.6.3 Elemento TemporalElemento temporal é uma união finita de intervalos de tempo. Estes intervalos podem ser disjuntos, o que realmente o diferencia dos demais e enriquece o seu poder de expressão – por exemplo, um possível elemento temporal seria a união dos intervalos [25, 40] e [51, 70]. O elemento temporal é fechado para as operações de união, interseção e complemento da teoria dos conjuntos, isto é, qualquer destas operações sobre um elemento temporal produz um novo elemento temporal. Como estas operações encontram contrapartida nos operad ores booleanos or, and e not, isto produz uma substancial simplificação na habilidade do usuário de expressar consultas temporais. Tendo em vista que todos os intervalos temporais são subconjuntos do eixo temporal T, um elemento temporal, sendo composto por diversos intervalos temporais, também o é. Tanto um intervalo temporal como um instante temporal ([t, t]) são elementos temporais.Em termos de modelagem, o elemento temporal se mostra superior aouso da primitiva intervalo de tempo pois, quando os intervalos são usados como rótulos temporais, os objetos são fragmentados em várias tuplas, uma para cada intervalo. Outro aspecto importante desta primitiva temporal é que possibilita a representação da “reencarnação” de objetos com facilidade. Um exemplo da n ecessidade deste aspecto seria uma pessoa ser funcionário de uma empresa durante o intervalo [1992, 1995], tendo saído da empresa em 1995 e sendo readmitida dois anos depois (1997). A validade da existência desta pessoa na empresa seria a união dos intervalos [1992, 1995] U [1997, »].2.6.4 Duração TemporalA representação de um duração temporal pode também ser considerada como primitiva. Durações temporais podem ser basicamente de dois tipos, dependendo do contexto em que são definidas: fixas e variáveis. Uma duração fixa independe do contexto de sua definição. Um exemplo típico de uma duração fixa é uma hora que tem sempre, independentemente do contexto de sua utilização, a duração de 60 minutos. Já a duração variável depende do contexto, sendo um exemplo típico a duração de um mês, que pode ser de 28, 29, 30 ou 31 dias.2.7 Limites do TempoO conceito de limites no tempo pode variar dependendo da representação temporal utilizada. Quando considerados somente pontos no tempo, os limites do tempo se referem a considerar ou não o tempo como infinito. O conceito de tempo infinito consiste em considerar que todo ponto no tempo apresente sempre um sucessor e um antecessor. Em modelos orientados a objetos este conceito fica limitado, por exemplo, ao tempo de vida de um objeto. No caso das teorias baseadas em intervalos, os limites do tempo se referem geralmente à pertinência ou não dos pontos limites ao intervalo, definindo se os intervalos são abertos ou fechados em um ou em ambas as extremidades.2.8 Representação Temporal Explícita e ImplícitaA definição de tempo pode ser feita de forma explícita, através por exemplo da associação de um valor temporal a uma informação na forma de um rótulo temporal (timestamping), ou de forma implícita através da utilização de uma linguagem de lógica temporal.A associação explícita de tempo às informações consiste em associar a cada valor atribuído a um atributo, o valor que corresponde à sua primitiva temporal. A representação temporal implícita é feita através da manipulação de conhecimentos sobre a ocorrência de eventos ou do relacionamento de intervalos de tempo como, por exemplo: a aula de lógica temporal ocorreu ontem.2.9 Tempo de Transação e Tempo VálidoTrês diferentes conceitos temporais podem ser identificados em aplicações de bancos de dados [Snodgrass 85]: (i) tempo de transação, tempo no qual o fato é registrado no banco de dados; (ii) tempo de validade, tempo em que o valor é válido na realidade modelada; e (iii) tempo definido pelo usuário, consistindo de propriedades temporais definidas explicitamente pelos usuários em um domínio temporal e manipuladas pelos programas de aplicação. Estes tempos são ortogonais, podendo ser tratados separadamente ou em conjunto. O tempo de transação é supridoautomaticamente pelo sistema gerenciador d e banco de dados, enquanto que o tempo de validade é fornecido pelo usuário.O tempo de validade pode ser representado de formas distintas, dependendo do elemento temporal básico utilizado no modelo. Quando for utilizado o elemento temporal ponto no tempo, o tempo de validade pode ser representado: (i) através de um ponto no tempo indicando o início da validade, permanecendo o valor válido até que inicie o tempo de validade de outro valor; ou (ii) através de dois pontos no tempo, o primeiro indicando o início da validade e segundo, o final da validade. Nos modelos que utilizam o intervalo temporal como elemento temporal básico, o tempo de validade é definido através do intervalo de validade do valor.3 Bancos de Dados TemporaisUm banco de dados temporal é aquele que apresenta alguma forma implícita de representação de informações temporais. Podem ser utilizados o tempo de transação e/ou o de validade para representar esta informação temporal. Conforme a forma utilizada, os bancos de dados podem ser classificad os em quatro tipos diferentes: bancos de dados instantâneos, de tempo de transação, de tempo de validade e bitemporais.3.1 Bancos de Dados InstantâneosCorresponde aos bancos de dados convencionais, onde são armazenados somente os valores presentes. A cada modificação no valor de uma propriedade, o valor anteriormente armazenado é destruído e somente o último valor está disponível. A figura 3.1 apresenta algumas atualizações feitas em momentos diferentes em um banco de dados instantâneo. Cada estado do banco de dados corresponde a um instantâneo (snapshot). A manutenção de informações temporais neste tipo de banco de dados somente pode ser realizada explicitamente, pela inclusão de atributos definidos sobre o domínio tempo, e pela sua manipulação através dos programas de aplicação.Figura 3.1: Banco de Dados Instantâneo3.2 Bancos de Dados de Tempo de TransaçãoUma alternativa para armazenamento de informações temporais é associar a cada valor definido o tempo de transação, sob forma de um rótulo temporal (timestamp). Este tempo é fornecido automaticamente peloSGBD, sendo esta operação transparente ao usuário. A alteração do valor de uma propriedade não destrói o valor anteriormente definido, ficandotodos os valores armazenados no banco de dados. O estado atual do BD é composto pelos últimos valores definidos para cada uma das propriedades. Bancos de dados deste tipo são denominados de bancos de dados de tempo de transação. Na figura 3.2 estão representadas atualizações do3.3 Bancos de Dados de Tempo de ValidadeUm terceiro tipo de banco de dados, denominado banco de dados de tempo de validade, associa a cada informação somente o tempo de sua validade no mundo real. Este pode representar o início de sua validade(ponto no tempo, variação por degraus), a validade somente naquele ponto no tempo (variação discreta), ou seu intervalo de validade. O tempo devalidade deve sempre ser fornecido pelo usuário. Em bancos de dados de tempo de validade não se tem acesso ao tempo em que a informação foi3.4 Bancos de Dados BitemporaisA forma mais completa de armazenar informações temporais são os bancos de dados bitemporais, nos quais os tempos de transação e de validade são a ssociados a cada informação. Toda a história do banco de dados fica armazenada. É possível ter acesso a todos os estados passados do banco de dados - tanto a história das transações realizadas, como a história da validade dos dados. O estado atual do banco de dados é constituído pelos valores atualmente válidos. Valores futuros podem ser definidos através do tempo de validade, sendo possível recuperar o momento em que estes valores foram definidos para eventuais alterações.Como exemplo deste tipo de banco de dados apresentamos, na figura 3.5,também esteja disponível uma linguagem de consulta temporal. Esta linguagem deve possibilitar a recuperação de todas as informaçõesarmazenadas no banco de dados (temporais ou não), de modo a que seja tirado real proveito do acréscimo da dimensão temporal. Consultatemporais permitem:• fornecer valores de propriedade s cujo domínio é temporal. Exemplo: fornecer o valor da propriedade que armazena a data de nascimento de uma pessoa;• se referir a um determinado instante ou intervalo temporal. Exemplo: qual o valor do salário no dia 01/01/94;• recuperar valores com base em restrições temporais. Exemplo: recuperar todos os valores do salário antes do dia 01/01/94;• fornecer informações temporais (datas, intervalos). Exemplo: qual a data em que foi alterado o salário de um funcionário.Para que isto seja possível, as linguage ns de consultas temporaisdevem ser enriquecidas para manipular a dimensão temporal, e ter capacidade de dedução sobre tempo com base nas informações temporaisarmazenadas. Isto é possibilitado através da utilização de lógica temporal,a qual permite inferências de valores não explicitamente armazenados.4.1 Problemas no Processamento de Consultas TemporaisO processamento de consultas temporais apresenta diversos problemas além daqueles usualmente enfrentados. Entre eles podemos citar:• o grande volume de dados armazenado em um banco de dados temporal implica na necessidade de novos métodos de indexação (estruturas e algoritmos de busca);• métodos tradicionais de indexação só podem ser utilizados para valores com algum tipo de ordenação completa, com estruturas de acesso para intervalos;• manipulação de informações incompletas, devido a valores incompletos ou inexistentes, a partir dos quais devem ser inferidas informações.Podem ser devido (i) à incerteza quanto à existência do objeto em certos pontos no tempo, ou (ii) à indeterminação temporal, causada por eventos cujo tempo de ocorrência não é conhecido4.2 Tipos de Bancos de Dados e Diferentes HistóriasAs consultas temporais que podem ser formuladas a um banco de dados temporal dependem do tipo de banco de dados e da história considerada.Os bancos de dados instantâneos não apresentam suporte para informações temporais, não permitindo portanto consultas temporais.Nos bancos de dados de tempo de transação podem ser feitas consultasa (i) valores atuais das informações armazenadas, (ii) valores definidos em tempos passados. O tempo de transação associado implicitamente à informação identifica o instante para o qual se quer a informação. A validade das informações somente pode ser armazenada através de atributos explícitos, e sua recuperação seria através destes atributos. Exemplo: recuperar o salário de um funcionário no dia (tempo de transação) 01/01/97.Nos bancos de dados de tempo de validade podem ser recuperadas informações válidas em momentos presentes e passado s, além de valores armazenados sob forma de previsão para o futuro, de acordo com a atual percepção da história dos dados. Exemplo: recuperar o salário válido de um funcionário no dia 01/01/98.Os bancos de dados bitemporais permitem que sejam feitas consultas a respeito de valores atuais, passados e futuros, considerando o tempo de transação e o de validade. Qualquer estado do banco de dados pode ser consultado (atual, passado, ou previsto para o futuro). Quando。
