Technologie d'indexation 'XML' basée sur un moteur de base de données relationnelle

XML (Extensible Markup Language) est devenu la norme pour la représentation et l'échange de données dans les applications Web. Avec le développement rapide d'Internet, en particulier l'utilisation généralisée du commerce électronique, des services Web et d'autres applications, les données de type XML sont devenues la norme. devenir le formulaire de données courant actuel. Par conséquent, la technologie de gestion des données XML, en particulier la technologie de requête de données XML, est devenue un point chaud de recherche actuel.

Par rapport aux données relationnelles, XML présente divers avantages, mais son plus gros inconvénient est son efficacité. Car dans un fichier de données relationnelles, le nom du champ des données ne doit apparaître qu'une seule fois, tandis que dans le fichier de données XML, le nom de l'élément apparaîtra à plusieurs reprises, 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 World Wide Web Consortium a identifié XPath2.0 et XQuery1.0 comme normes recommandées le 23 janvier 2007, mettant ainsi fin à la concurrence précédente entre les différents langages de requête. 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 d'indexation XML

Actuellement, 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, toute requête portant sur des 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 devenue 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 ne prêtez pas beaucoup d'attention aux 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). Le contenu principal de l'index XML est de concevoir le modèle adapté à la technologie Matching.

Classification d'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. La structure arborescente réduite ne conserve que des informations de chemin différentes, et il n'y aura 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 raffinement à partir du nœud racine. Un résumé structurel du chemin. Les chemins de chaîne formés par la concaténation des étiquettes de bord ne sont décrits qu'une seule fois dans 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.

Écrivez ensuite le fichier objet Java TestLob.java sur ces deux grands champs, en définissant 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 à. Le type String en Java est utilisé pour gérer certains fichiers volumineux qui ne sont pas strictement définis et sont stockés sous forme de flux binaires, laissez-le donc utiliser le type byte[], puis définissez les méthodes Getter et Setter de ces deux propriétés. respectivement. Le code pertinent est le suivant :

L'index Dataguides est un résumé structurel du chemin affiné à partir du nœud racine. Les chemins de chaîne formés par la concaténation des étiquettes de bord ne sont décrits qu'une seule fois dans 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 de marque 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 selon le chemin d'accès à 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 dans la gestion des expressions de requête à correspondance partielle avec l’axe descendant ou auto défini dans la norme XPath

Pour cette raison, APEX [14] a introduit le XML de dépendance Informations de distribution des requêtes de données : pré-enregistrez les nœuds d'étiquette 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 pour voir 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 dans le enregistrer. 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. Index basé sur le préfixe

Index basé sur le préfixe. Il s'agit principalement d'un index généré sur la base du codage Dewey[12]. Le codage ORDPATH dans la littérature [13] utilise une méthode similaire et donne une méthode de compression de ORDPATH. Cette méthode 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 de nœud pour le codage de préfixe, afin de déterminer si un nœud v est un descendant de. un autre nœud u, il suffit de déterminer 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 d'intervalle

Pour l'index de codage d'intervalle, chaque nœud de l'arbre T se voit attribuer un codage d'intervalle [début, fin], qui satisfait : l'intervalle d'un nœud Le encoding contient le codage d'intervalle de ses nœuds descendants. Autrement dit, le nœud u dans l'arbre T est l'ancêtre du nœud v si et seulement si start(u)

Le premier schéma de codage d'intervalle est le codage Dietz, chaque nœud dans l'arbre T se voit attribuer un tuple avec un numéro de parcours de pré-ordre et un numéro de parcours de post-ordre Puisqu'un nœud ancêtre u dans l'arbre T doit apparaître dans le parcours de pré-ordre (traversée de post-ordre), son nœud descendant v est. avant (après), donc les nœuds u et v sont des relations 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 à chacun node, où order est le code de précommande étendu et size est la plage des descendants du nœud. Pour tout nœud X et Y dans une arborescence de documents, si et seulement si order(x)

L'index 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 l'originale. document est obtenu. , sa structure est toujours une arborescence, donc lors du traitement d'une requête, vous devez toujours parcourir l'intégralité de l'arborescence d'index pour obtenir les résultats. 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égulier, mais pour les expressions de chemin long, en particulier lorsque la requête génère. 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. .

Ce qui précède est le contenu de la technologie d'indexation « XML » basée sur un moteur de base de données relationnelle. Pour plus de contenu connexe, veuillez faire attention au site Web PHP chinois (www.php.cn) !