Par rapport aux données relationnelles, XML présente de nombreux avantages, mais son plus gros inconvénient est son efficacité. Car dans les fichiers de données relationnelles, les noms de champs de données ne doivent apparaître qu'une seule fois, tandis que dans les fichiers de données XML, les noms d'éléments apparaîtront de manière répétée, ce qui affectera certainement l'efficacité de la requête. Afin d'améliorer autant que possible l'efficacité des requêtes XML, il est nécessaire de fournir une fonction d'indexation pour le type XML.
Le 23 janvier 2007, le World Wide Web Consortium a identifié XPath 2.0 et XQuery 1.0 comme normes recommandées, mettant fin à la situation précédente dans laquelle divers langages de requête se disputaient la domination. Sur la base de cette norme, en plus des fabricants traditionnels, diverses institutions de recherche scientifique ont proposé des implémentations de XPath et XQuery (il y en a plus d'une douzaine mentionnées dans la littérature), avec différents modèles de stockage, différents algorithmes de requête et méthodes d'optimisation. Dans ce contexte, Dameng Database Company a également proposé son propre modèle de moteur de requête XML basé sur sa propre stratégie de développement. Actuellement, le moteur de requête XML de Dameng est en cours de développement intense, et l'établissement d'index efficaces pour les données XML est un facteur important affectant XML. performances des requêtes de données. Sur la base d'une analyse approfondie de la technologie d'indexation des produits de base de données existants, une structure d'index plus raisonnable est conçue pour le moteur de requête XML Dameng afin que le moteur puisse atteindre des performances optimales.
Introduction à la technologie des index XML
À l'heure actuelle, les recherches sur XML sont principalement divisées en deux aspects. L'une est une base de données native pour le stockage, l'interrogation et la gestion de données semi-structurées telles que XML. Les données et métadonnées sont entièrement exprimées dans des structures XML et n'ont rien à voir avec le format de stockage de données sous-jacent (tel qu'un modèle objet, un modèle relationnel). , etc.). L'autre est la conversion mutuelle entre celle-ci et la base de données relationnelle, en utilisant la technologie mature de la base de données relationnelle pour traiter les données XML. Cette dernière direction ayant une signification plus pratique, elle est devenue le centre de la recherche XML.
Outre les solutions de stockage, la technologie d'indexation est également l'un des facteurs les plus importants dans la détermination d'un système de base de données. Si aucune structure d'index n'est construite pour les documents XML, alors toute requête de données XML risque de parcourir l'intégralité de l'arborescence du document. À mesure que l'ensemble de données XML augmente, cette surcharge est intolérable. Par conséquent, la recherche sur la technologie des index XML a une grande valeur théorique et pratique.
Bien que la technologie d'indexation traditionnelle soit relativement mature après une accumulation à long terme, ce type de technologie d'indexation se concentre principalement sur la fonction de localisation d'enregistrements de données en fonction de valeurs (plutôt que de modèles avec certaines relations) et ne prête pas beaucoup d'attention à la relations logiques entre les enregistrements de données. ;La fonctionnalité de base de la requête de données XML est d'extraire des données conformes au modèle en fonction de l'entrée des caractéristiques du modèle (relations structurelles décrites sous la forme d'expressions de chemin régulières). index est de concevoir une technologie adaptée à la correspondance de modèles.
Classification de l'index XML
Index XML basé sur le chemin
L'index basé sur le chemin est basé sur les informations de chemin des nœuds dans la structure arborescente XML et adopte une certaine méthode de réduction afin que la structure arborescente réduite ne conserve que des informations de chemin différentes et n'existe pas Deux nœuds avec le même chemin. Les index proposés incluent : l'index DataGuides, l'index Index Fabric, l'index de chemin adaptatif pour les données XML (APEX).
L'index Dataguides est un résumé structurel du chemin affiné à partir du nœud racine. Le chemin de chaîne formé par la concaténation des étiquettes de bord n'est décrit qu'une seule fois dans les Dataguides. Les guides de données réduisent le nombre de nœuds requis lors du parcours des requêtes de chemin et sont efficaces pour parcourir les documents XML à partir de la racine. Cependant, les requêtes de chemin contenant des caractères génériques ou les requêtes de chemin avec l'axe descendant ou auto défini dans la norme XPath nécessitent plusieurs opérations de connexion, ce qui entraîne une faible efficacité des requêtes et une redondance des données.
Ensuite, écrivez le fichier objet Java TestLob.java sur ces deux grands champs et définissez les types comme champs d'attribut CLOB et BLOB comme types String et byte[] respectivement. Puisque CLOB est un type de texte volumineux, il correspond au type String en Java. . , BLOB consiste à traiter certains fichiers volumineux qui ne sont pas strictement définis et qui sont stockés sous forme de flux binaires, laissez-le donc utiliser le type byte[], puis définissez respectivement les méthodes Getter et Setter de ces deux propriétés. Le code est le suivant :
L'index des guides de données provient du nœud racine. Un résumé structurel du chemin de raffinement de départ. Le chemin de chaîne formé par la concaténation des étiquettes de bord n'est décrit qu'une seule fois dans les Dataguides. Les guides de données réduisent le nombre de nœuds requis lors du parcours des requêtes de chemin et sont efficaces pour parcourir les documents XML à partir de la racine. Cependant, les requêtes de chemin contenant des caractères génériques ou les requêtes de chemin avec l'axe descendant ou auto défini dans la norme XPath nécessitent plusieurs opérations de connexion, ce qui entraîne une faible efficacité des requêtes et une redondance des données.
Index Fabric est une structure d'index développée sur l'arbre Patricia Trie. Il encode chaque chemin marqué vers chaque nœud d'élément avec une chaîne, puis insère ces valeurs codées dans l'arbre Patricia Trie, convertissant ainsi la requête de données XML en fonction du chemin dans la requête de chaîne. Lors de l'interrogation, encodez d'abord le chemin de la requête sous forme de chaîne, puis recherchez-le dans l'arborescence d'index. L'avantage de l'index Index Fabric est qu'il stocke les informations de structure hiérarchique des données XML, gère uniformément la récupération des données XML avec des informations de schéma et sans schéma, et réduit le temps requis pour l'interrogation et la mise à jour des données XML liées à la hiérarchie plutôt que à la La longueur de la clé d'index est liée. L'inconvénient de l'index Index Fabric est qu'il perd la relation structurelle entre les nœuds d'éléments, car il ne conserve que les informations des nœuds d'éléments avec des valeurs de texte. Par conséquent, à l’instar des index DataGuides, les index Index Fabric ne sont pas efficaces pour gérer les expressions de requête partiellement appariées avec des axes descendants ou auto définis dans la norme XPath.
À cette fin, APEX [14] a introduit des informations qui s’appuient sur la distribution des données XML
.requêtes. : nœuds d'étiquette pré-enregistrés correspondant aux instructions de requête XML fréquentes dans une structure de hachage. Sa fonction est similaire à celle du Cache : lorsqu'une nouvelle requête nécessite un traitement, il recherche d'abord dans la table de hachage s'il existe un ensemble de nœuds satisfaisant. Mais il est moins efficace pour les expressions de requête avec des valeurs d'éléments ou des valeurs d'attribut.
Index basé sur les nœuds
L'index basé sur les nœuds décompose essentiellement les données XML en un ensemble d'enregistrements d'unités de données et enregistre en même temps les informations d'emplacement de l'unité dans les données XML de l'enregistrement. Contrairement aux index basés sur les chemins, les index basés sur les nœuds brisent la restriction selon laquelle les nœuds doivent être trouvés via des chemins d'étiquette et décomposent les données XML en enregistrements de nœuds sous une forme canonique. Parce qu'il enregistre les informations de localisation des nœuds et peut être bien intégré dans les systèmes de gestion de bases de données relationnelles matures, il s'agit actuellement de l'index le plus largement utilisé.
Selon les différentes méthodes de codage des informations de localisation, les index basés sur les nœuds peuvent généralement être divisés dans les catégories suivantes :
1. Les index basés sur les
préfixes sont principalement des index générés sur la base du codage Dewey [12] et du codage ORDPATH. de la littérature [13] Une méthode similaire est adoptée et une méthode de compression ORDPATH est donnée, qui a été appliquée à l'organisation des index de SQL Server 2005.
L'idée de base du codage de préfixe est d'utiliser directement le codage du nœud parent d'un nœud comme préfixe du codage du nœud. Pour le codage de préfixe, pour déterminer si un nœud v est un descendant d'un autre nœud u, il vous suffit de déterminer. si le codage de u est le préfixe du codage de v. . Une propriété importante des index de codage de préfixe est leur ordre dans le dictionnaire : pour tout nœud u dans le sous-arbre enraciné au nœud r, son codage de préfixe c(u) est supérieur (inférieur à) son sous-arbre frère de gauche (sous-arbre frère de droite). de tous les nœuds dans . Par conséquent, les index basés sur des préfixes peuvent non seulement prendre en charge efficacement le calcul des relations d'inclusion, mais également prendre en charge efficacement le calcul des relations de position du document.
2. Index basé sur le codage par intervalles
Pour l'index de codage par intervalles, chaque nœud de l'arbre T se voit attribuer un code d'intervalle [début, fin], qui satisfait : le code d'intervalle d'un nœud inclut le code d'intervalle de ses nœuds descendants. pour dire, le nœud u dans l'arbre T est l'ancêtre du nœud v, si et seulement si
le premier schéma de codage d'intervalle de start(u) est le codage Dietz, chaque nœud de l'arbre T se voit attribuer un numéro de séquence de parcours de pré-ordre et Post- Tuple de numéro de séquence de parcours d'ordre. Puisqu'un nœud ancêtre u dans l'arbre T doit apparaître avant (après) son nœud descendant v dans le parcours de pré-ordre (parcours post-ordre), par conséquent, les nœuds u et v sont une relation ancêtre/descendant. , si et seulement si pre(u)
Un autre exemple typique d'index de codage d'intervalle est l'index XISS, qui attribue une paire de nombres à chaque nœud, où l'ordre est le codage de pré-ordre étendu et la taille est les descendants de la portée du nœud. Pour tout nœud X et Y dans une arborescence de documents, si et seulement si l'
index order(x) XISS décompose l'instruction de requête d'origine en sous-expressions. Implémentez ensuite la requête pour ces sous-expressions respectivement, et enfin joignez ces résultats intermédiaires pour obtenir l'ensemble de résultats de la requête. Cela permet de mieux prendre en charge les instructions de requête contenant des caractères génériques. Cependant, il obtient le résultat final de la requête après avoir concaténé chaque résultat intermédiaire. Bien qu’une telle méthode puisse effectivement résoudre tous les problèmes de caractères génériques, la concaténation de tels résultats intermédiaires risque de prendre beaucoup de temps, en particulier pour les expressions simples avec des chemins longs.
Comparaison de deux mécanismes d'indexation.
L'indexation basée sur le chemin est principalement basée sur la stratégie de fusion de nœuds. Grâce à des techniques telles que l'équivalence de nœud et l'équivalence de chemin, une structure d'index beaucoup plus petite que le document original est toujours en forme d'arborescence. , donc lors du traitement d'une requête, vous devez toujours parcourir l'intégralité de l'arborescence d'index pour obtenir le résultat. Les index basés sur le chemin peuvent très bien prendre en charge les requêtes d'expression de chemin simple, mais pour les expressions de chemin régulières, cela ne fonctionne pas très bien.
L'index basé sur les nœuds indexe chaque nœud grâce à la technologie d'encodage.La relation structurelle entre les nœuds peut être déterminée en temps constant grâce à l'encodage.Il peut bien prendre en charge les expressions de chemin régulières, mais pour les expressions de chemin long, en particulier lors de la génération de requêtes Lorsqu'il y a de nombreux résultats intermédiaires, l'opération de jointure de l'index de nœud est coûteuse.
L'indexation basée sur le chemin et l'indexation basée sur les nœuds ont chacune leurs propres avantages et inconvénients, mais elles peuvent se compléter. À l'heure actuelle, dans les applications pratiques, l'indexation basée sur les nœuds est plus largement utilisée et la recherche est relativement mature. Par conséquent, les recherches de Dameng Company sur la structure des index XML se concentrent principalement sur l'indexation basée sur les nœuds et apportent des améliorations appropriées en référence à l'indexation basée sur les chemins. .