XML (Extensible Markup Language) tornou-se o padrão para representação e troca de dados em aplicações Web. Com o rápido desenvolvimento da Internet, especialmente o uso generalizado de comércio eletrônico, serviços Web e outras aplicações, os dados do tipo XML tornaram-se o atual. formulário de dados principal. Portanto, a tecnologia de gerenciamento de dados XML, especialmente a tecnologia de consulta de dados XML, tornou-se um ponto de acesso de pesquisa atual.
Comparado aos dados relacionais, o XML tem várias vantagens, mas sua maior desvantagem é a eficiência. Porque em arquivos de dados relacionais, os nomes dos campos de dados só precisam aparecer uma vez, enquanto nos arquivos de dados XML, os nomes dos elementos aparecerão repetidamente, o que certamente afetará a eficiência da consulta. Para melhorar ao máximo a eficiência da consulta XML, é necessário fornecer uma função de indexação para o tipo XML.
O World Wide Web Consortium identificou XPath 2.0 e XQuery 1.0 como padrões recomendados em 23 de janeiro de 2007, encerrando a situação anterior em que diversas linguagens de consulta competiam pelo domínio. Com base neste padrão, além dos fabricantes tradicionais, diversas instituições de pesquisa científica propuseram implementações de XPath e XQuery (há mais de uma dezena mencionadas na literatura), com diferentes modelos de armazenamento, diferentes algoritmos de consulta e métodos de otimização, em. Neste contexto, a Dameng Database Company também propôs seu próprio modelo de mecanismo de consulta XML com base em sua própria estratégia de desenvolvimento. Atualmente, o mecanismo de consulta XML da Dameng está em intenso desenvolvimento, e o estabelecimento de índices eficazes para dados XML é um fator importante que afeta o XML. desempenho de consulta de dados. Com base em uma análise aprofundada da tecnologia de indexação dos produtos de banco de dados existentes, uma estrutura de índice mais razoável é projetada para o mecanismo de consulta XML Dameng, para que o mecanismo possa atingir o desempenho ideal.
Introdução à tecnologia de índice XML
Atualmente, a pesquisa das pessoas sobre XML está dividida principalmente em dois aspectos. Um é um banco de dados nativo para armazenamento, consulta e gerenciamento de dados semiestruturados, como XML. Os dados e metadados são completamente expressos em estruturas XML e não têm nada a ver com seu formato de armazenamento de dados subjacente (como modelo de objeto, modelo relacional). , etc.). A outra é a conversão mútua entre ele e o banco de dados relacional, utilizando a tecnologia madura do banco de dados relacional para processar dados XML. Como esta última direção tem um significado mais prático, ela se tornou o foco da pesquisa em XML.
Além das soluções de armazenamento, a tecnologia de índice também é um dos fatores mais importantes na determinação de um sistema de banco de dados. Se nenhuma estrutura de índice for construída para documentos XML, então qualquer consulta de dados XML provavelmente resultará na passagem de toda a árvore do documento. À medida que o conjunto de dados XML aumenta, essa sobrecarga é intolerável. Portanto, a pesquisa sobre tecnologia de índice XML tem alto valor teórico e prático.
Embora a tecnologia de indexação tradicional tenha sido relativamente madura após a acumulação de longo prazo, este tipo de tecnologia de indexação concentra-se principalmente na função de localizar registros de dados com base em valores (em vez de padrões com certos relacionamentos), e não presta muita atenção ao relacionamentos lógicos entre registros de dados; O recurso básico da consulta de dados XML é extrair dados que estejam em conformidade com o padrão com base na entrada de recursos do padrão (relacionamentos estruturais descritos na forma de expressões de caminho regulares). índice é projetar tecnologia adequada para correspondência de padrões.
Classificação do índice XML
Índice XML baseado em caminho
O índice baseado em caminho é baseado nas informações de caminho dos nós na estrutura de árvore XML e adota um determinado método de redução para que a estrutura de árvore reduzida apenas mantenha informações de caminho diferentes e não exista Dois nós com o mesmo caminho. Esses índices que foram propostos incluem: índice DataGuides, índice Index Fabric, Adaptive Path Index for XML Data (APEX).
O índice Dataguides é um resumo estrutural do caminho refinado começando no nó raiz. O caminho da string formado pela concatenação de rótulos de arestas é descrito apenas uma vez nos Dataguides. Os guias de dados reduzem o número de nós necessários ao percorrer consultas de caminho e são eficientes ao percorrer documentos XML a partir da raiz. No entanto, consultas de caminho contendo caracteres curinga ou consultas de caminho com o eixo descendente ou próprio definido no padrão XPath exigem múltiplas operações de conexão, resultando em baixa eficiência de consulta e redundância de dados.
Em seguida, escreva o arquivo de objeto Java TestLob.java sobre esses dois campos grandes e defina os tipos como campos de atributos CLOB e BLOB como tipos String e byte[] respectivamente. Como CLOB é um tipo de texto grande, ele corresponde ao tipo String em Java. ., BLOB é para processar alguns arquivos grandes que não são estritamente definidos e são armazenados na forma de fluxos binários, então deixe-o usar o tipo byte[] e, em seguida, defina os métodos Getter e Setter dessas duas propriedades, respectivamente. o código é o seguinte:
O índice do Dataguides vem do nó raiz Um resumo estrutural do caminho inicial de refinamento. O caminho da string formado pela concatenação de rótulos de arestas é descrito apenas uma vez nos Dataguides. Os guias de dados reduzem o número de nós necessários ao percorrer consultas de caminho e são eficientes ao percorrer documentos XML a partir da raiz. No entanto, consultas de caminho contendo caracteres curinga ou consultas de caminho com o eixo descendente ou próprio definido no padrão XPath exigem múltiplas operações de conexão, resultando em baixa eficiência de consulta e redundância de dados.
Index Fabric é uma estrutura de índice desenvolvida na árvore Patricia Trie. Ele codifica cada caminho marcado para cada nó de elemento com uma string e, em seguida, insere esses valores codificados na árvore Patricia Trie, convertendo assim a consulta de dados XML de acordo com o. caminho para a consulta de string. Ao consultar, primeiro codifique o caminho da consulta em um formato de string e, em seguida, pesquise-o na árvore de índice. A vantagem do índice Index Fabric é que ele armazena as informações da estrutura hierárquica dos dados XML, lida uniformemente com a recuperação de dados XML com informações de esquema e sem esquema e economiza o tempo necessário para consultar e atualizar dados XML relacionados à hierarquia, em vez de ao O comprimento da chave do índice está relacionado. A desvantagem do índice Index Fabric é que ele perde o relacionamento estrutural entre os nós dos elementos, pois retém apenas as informações dos nós dos elementos com valores de texto. Portanto, semelhante aos índices DataGuides, os índices Index Fabric não são eficientes no tratamento de expressões de consulta parcialmente correspondidas com eixos descendentes ou próprios definidos no padrão XPath.
Para esse fim, APEX [14] introduziu informações que dependem da distribuição de dados XML. consultas. : Nós de rótulo pré-salvamento correspondentes a instruções de consulta XML que ocorrem com frequência em uma estrutura hash. Sua função é semelhante à função do Cache: quando uma nova consulta requer processamento, ele primeiro pesquisa a tabela hash para ver se há um conjunto de nós satisfatório. Mas é menos eficiente para expressões de consulta com valores de elementos ou valores de atributos.
Índice baseado em nó
O índice baseado em nó decompõe essencialmente os dados XML em um conjunto de registros de unidades de dados e, ao mesmo tempo, salva as informações de localização da unidade nos dados XML do registro. Ao contrário dos índices baseados em caminhos, os índices baseados em nós quebram a restrição de que os nós devem ser encontrados por meio de caminhos de rótulos e decompõem os dados XML em registros de nós em um formato canônico. Por salvar as informações de localização dos nós e poder ser bem integrado em sistemas maduros de gerenciamento de banco de dados relacional, é atualmente o índice mais utilizado.
De acordo com os diferentes métodos de codificação de informações de localização, os índices baseados em nós geralmente podem ser divididos nas seguintes categorias:
1. Índices baseados em prefixo
Os índices baseados em prefixo são principalmente índices gerados com base na codificação Dewey [12] e na codificação ORDPATH. da literatura [13] Um método semelhante é adotado e é fornecido um método de compactação ORDPATH, que foi aplicado à organização de índices do SQL Server 2005.
A idéia básica da codificação de prefixo é usar diretamente a codificação do nó pai de um nó como o prefixo da codificação do nó. Para codificação de prefixo, para determinar se um nó v é descendente de outro nó u, você só precisa determinar. se a codificação de u é o prefixo da codificação de v. Uma propriedade importante dos índices de codificação de prefixo é sua ordenação de dicionário: para qualquer nó u na subárvore enraizada no nó r, sua codificação de prefixo c(u) é maior (menor que) sua subárvore irmã esquerda (subárvore irmã direita). de todos os nós em . Portanto, os índices baseados em prefixos podem não apenas apoiar eficazmente o cálculo das relações de inclusão, mas também apoiar eficazmente o cálculo das relações de posição do documento.
2. Índice baseado na codificação de intervalo
Para o índice de codificação de intervalo, cada nó na árvore T recebe um código de intervalo [início, fim], que satisfaz: o código de intervalo de um nó inclui o código de intervalo de seus nós descendentes. para dizer, o nó u na árvore T é o ancestral do nó v, se e somente se
o primeiro esquema de codificação de intervalo de start(u) for a codificação Dietz, cada nó na árvore T recebe um número de sequência de travessia de pré-ordem e Pós- tupla de número de sequência de travessia de ordem Como um nó ancestral u na árvore T deve aparecer antes (depois) de seu nó descendente v na travessia de pré-ordem (travessia de pós-ordem), portanto, os nós uev são relacionamento ancestral/descendente. , se e somente se pre(u)
Outro exemplo típico de índice de codificação de intervalo é o índice XISS, que atribui um par de números a cada nó, onde ordem é a codificação de pré-ordem estendida e tamanho são os descendentes do escopo do nó. Para qualquer nó X e Y em uma árvore de documentos, se e somente se
o índice XISS order(x) decompõe a instrução de consulta original em subexpressões. Em seguida, implemente a consulta para essas subexpressões respectivamente e, finalmente, junte esses resultados intermediários para obter o conjunto de resultados da consulta. Isso pode oferecer suporte melhor a instruções de consulta contendo caracteres curinga. Porém, obtém o resultado final da consulta após concatenar cada resultado intermediário. Embora tal método possa de fato resolver todos os problemas de caracteres curinga, a concatenação de tais resultados intermediários provavelmente consumirá muito tempo, especialmente para expressões simples com caminhos longos.
Comparação de dois mecanismos de indexação
A indexação baseada em caminho é baseada principalmente na estratégia de fusão de nós. Por meio de técnicas como equivalência de nós e equivalência de caminhos, é obtida uma estrutura de índice muito menor que o documento original. , portanto, ao processar uma consulta, você ainda precisará percorrer toda a árvore de índice para obter o resultado. Índices baseados em caminho podem suportar muito bem consultas de expressão de caminho simples, mas para expressões de caminho regulares, isso não funciona muito bem.
O índice baseado em nó indexa cada nó por meio da tecnologia de codificação. O relacionamento estrutural entre os nós pode ser determinado em tempo constante por meio de codificação. Ele pode suportar bem expressões de caminho regulares, mas para expressões de caminho longo, especialmente quando há muitos resultados intermediários na geração de consultas. a operação de junção do índice do nó é cara.
A indexação baseada em caminho e a indexação baseada em nó têm suas próprias vantagens e desvantagens, mas podem se complementar. Atualmente, em aplicações práticas, a indexação baseada em nós é mais amplamente utilizada e a pesquisa está relativamente madura. Portanto, a pesquisa da Dameng Company sobre a estrutura do índice XML concentra-se principalmente na indexação baseada em nós e faz melhorias apropriadas com referência à indexação baseada em caminhos. .