XML (Extensible Markup Language) ist zum Standard für die Datendarstellung und den Datenaustausch in Webanwendungen geworden. Mit der rasanten Entwicklung des Internets, insbesondere der weit verbreiteten Nutzung von E-Commerce, Webdiensten und anderen Anwendungen, sind Daten vom Typ XML zum aktuellen Standard geworden Mainstream-Datenformular. Daher ist die XML-Datenverwaltungstechnologie, insbesondere die XML-Datenabfragetechnologie, zu einem aktuellen Forschungsschwerpunkt geworden.
Im Vergleich zu relationalen Daten hat XML verschiedene Vorteile, der größte Nachteil ist jedoch seine Effizienz. Denn in relationalen Datendateien müssen Datenfeldnamen nur einmal vorkommen, während in XML-Datendateien Elementnamen wiederholt vorkommen, was sich sicherlich auf die Effizienz der Abfrage auswirkt. Um die Abfrageeffizienz von XML so weit wie möglich zu verbessern, ist es notwendig, eine Indexierungsfunktion für den XML-Typ bereitzustellen.
Das World Wide Web Consortium identifizierte am 23. Januar 2007 XPath 2.0 und XQuery 1.0 als empfohlene Standards und beendete damit die bisherige Situation, in der verschiedene Abfragesprachen um die Vorherrschaft konkurrierten. Basierend auf diesem Standard haben neben traditionellen Herstellern auch verschiedene wissenschaftliche Forschungseinrichtungen Implementierungen von XPath und XQuery (in der Literatur werden mehr als ein Dutzend erwähnt) mit unterschiedlichen Speichermodellen, unterschiedlichen Abfragealgorithmen und Optimierungsmethoden vorgeschlagen In diesem Zusammenhang hat die Dameng Database Company auch ein eigenes XML-Abfrage-Engine-Modell vorgeschlagen, das auf ihrer eigenen Entwicklungsstrategie basiert. Derzeit befindet sich die XML-Abfrage-Engine von Dameng in intensiver Entwicklung, und die Einrichtung effektiver Indizes für XML-Daten ist ein wichtiger Faktor Datenabfrageleistung. Basierend auf einer eingehenden Analyse der Indexierungstechnologie vorhandener Datenbankprodukte wird eine sinnvollere Indexstruktur für die XML-Abfrage-Engine von Dameng entwickelt, damit die Engine eine optimale Leistung erzielen kann.
Einführung in die XML-Indextechnologie.
Derzeit gliedert sich die Forschung zu XML hauptsächlich in zwei Aspekte. Eine davon ist eine native Datenbank für die Speicherung, Abfrage und Verwaltung halbstrukturierter Daten wie XML. Die Daten und Metadaten werden vollständig in XML-Strukturen ausgedrückt und haben nichts mit dem zugrunde liegenden Datenspeicherformat (wie Objektmodell, relationales Modell) zu tun , usw.). Das andere ist die gegenseitige Konvertierung zwischen ihr und der relationalen Datenbank, wobei die ausgereifte Technologie der relationalen Datenbank zur Verarbeitung von XML-Daten verwendet wird. Da die letztere Richtung eine größere praktische Bedeutung hat, ist sie zum Schwerpunkt der XML-Forschung geworden.
Neben Speicherlösungen ist auch die Indextechnologie einer der wichtigsten Faktoren bei der Bestimmung eines Datenbanksystems. Wenn keine Indexstruktur für XML-Dokumente erstellt wird, führt jede Abfrage nach XML-Daten wahrscheinlich dazu, dass der gesamte Dokumentbaum durchlaufen wird. Mit zunehmendem XML-Datensatz ist dieser Mehraufwand nicht tolerierbar. Daher ist die Forschung zur XML-Indextechnologie von hohem theoretischen und praktischen Wert.
Obwohl die traditionelle Indizierungstechnologie nach längerer Akkumulation relativ ausgereift ist, konzentriert sich diese Art der Indizierungstechnologie hauptsächlich auf die Funktion, Datensätze anhand von Werten (anstelle von Mustern mit bestimmten Beziehungen) zu lokalisieren, und schenkt dieser nicht viel Aufmerksamkeit Logische Beziehungen zwischen Datensätzen. Die grundlegende Funktion der XML-Datenabfrage besteht darin, Daten zu extrahieren, die dem Muster entsprechen, basierend auf der Eingabe von Mustermerkmalen (strukturelle Beziehungen, die in Form von regulären Pfadausdrücken beschrieben werden). Der Index besteht darin, eine für den Mustervergleich geeignete Technologie zu entwerfen.
XML-Indexklassifizierung
Pfadbasierter XML-Index
Der pfadbasierte Index basiert auf den Pfadinformationen von Knoten in der XML-Baumstruktur und verwendet eine bestimmte Reduktionsmethode, sodass die reduzierte Baumstruktur nur unterschiedliche Pfadinformationen beibehält und nicht vorhanden ist Zwei Knoten mit der gleiche Weg. Zu den vorgeschlagenen Indizes gehören: DataGuides-Index, Index Fabric-Index, Adaptive Path Index für XML-Daten (APEX).
Der Dataguides-Index ist eine strukturelle Zusammenfassung des verfeinerten Pfads, beginnend mit dem Wurzelknoten. Der durch die Verkettung von Kantenbeschriftungen gebildete Zeichenfolgenpfad wird in den Datenleitfäden nur einmal beschrieben. Datenführer reduzieren die Anzahl der erforderlichen Knoten beim Durchlaufen von Pfadabfragen und sind beim Durchlaufen von XML-Dokumenten vom Stamm aus effizient. Allerdings erfordern Pfadabfragen, die Platzhalterzeichen enthalten, oder Pfadabfragen mit der im XPath-Standard definierten Nachkommen-oder-Selbst-Achse mehrere Verbindungsvorgänge, was zu einer geringen Abfrageeffizienz und Datenredundanz führt.
Schreiben Sie dann die Java-Objektdatei TestLob.java über diese beiden großen Felder und definieren Sie die Typen als CLOB- und BLOB-Attributfelder als String- bzw. Byte[]-Typen. Da CLOB ein großer Texttyp ist, entspricht er dem String-Typ in Java . BLOB dient dazu, einige große Dateien zu verarbeiten, die nicht streng definiert sind und in Form von Binärströmen gespeichert werden. Lassen Sie es daher den Typ byte [] verwenden und definieren Sie dann die entsprechenden Getter- und Setter-Methoden Der Code lautet wie folgt:
Der Dataguides-Index stammt vom Stammknoten. Eine strukturelle Zusammenfassung des anfänglichen Verfeinerungspfads. Der durch die Verkettung von Kantenbeschriftungen gebildete Zeichenfolgenpfad wird in den Datenleitfäden nur einmal beschrieben. Datenführer reduzieren die Anzahl der erforderlichen Knoten beim Durchlaufen von Pfadabfragen und sind beim Durchlaufen von XML-Dokumenten vom Stamm aus effizient. Allerdings erfordern Pfadabfragen, die Platzhalterzeichen enthalten, oder Pfadabfragen mit der im XPath-Standard definierten Nachkommen-oder-Selbst-Achse mehrere Verbindungsvorgänge, was zu einer geringen Abfrageeffizienz und Datenredundanz führt.
Index Fabric ist eine auf dem Patricia Trie-Baum entwickelte Indexstruktur. Sie codiert jeden markierten Pfad zu jedem Elementknoten mit einer Zeichenfolge und fügt diese codierten Werte dann in den Patricia Trie-Baum ein. Konvertiert somit die Abfrage von XML-Daten entsprechend Pfad in die Abfrage von string. Codieren Sie bei der Abfrage zunächst den Abfragepfad in eine Zeichenfolgenform und durchsuchen Sie ihn dann im Indexbaum. Der Vorteil des Index Fabric-Index besteht darin, dass er die hierarchischen Strukturinformationen von XML-Daten speichert, den Abruf von XML-Daten mit Schema- und schemalosen Informationen einheitlich handhabt und den Zeitaufwand für die Abfrage und Aktualisierung von XML-Daten im Zusammenhang mit der Hierarchie verringert Die Länge des Indexschlüssels hängt damit zusammen. Der Nachteil des Index Fabric-Index besteht darin, dass die strukturelle Beziehung zwischen Elementknoten verloren geht, da nur die Informationen von Elementknoten mit Textwerten gespeichert werden. Daher sind Index Fabric-Indizes ähnlich wie DataGuides-Indizes bei der Verarbeitung teilweise übereinstimmender Abfrageausdrücke mit im XPath-Standard definierten Nachkommen- oder Selbstachsen nicht effizient.
Zu diesem Zweck führte APEX [14] Informationen ein, die auf der Verteilung von XML-Daten basieren Abfragen: Vorabspeicherung von Label-Knoten, die häufig vorkommenden XML-Abfrageanweisungen in einer Hash-Struktur entsprechen. Seine Funktion ähnelt der Funktion von Cache: Wenn eine neue Abfrage verarbeitet werden muss, durchsucht es zunächst die Hash-Tabelle, um festzustellen, ob ein zufriedenstellender Knotensatz vorhanden ist. Für Abfrageausdrücke mit Elementwerten oder Attributwerten ist es jedoch weniger effizient.
Knotenbasierter Index
Der knotenbasierte Index zerlegt XML-Daten im Wesentlichen in einen Datensatz von Dateneinheiten und speichert gleichzeitig die Standortinformationen der Einheit in den XML-Daten im Datensatz. Im Gegensatz zu pfadbasierten Indizes durchbrechen knotenbasierte Indizes die Einschränkung, dass Knoten über Etikettenpfade gefunden werden müssen, und zerlegen XML-Daten in kanonischer Form in Knotendatensätze. Da er die Standortinformationen von Knoten speichert und sich gut in ausgereifte relationale Datenbankverwaltungssysteme integrieren lässt, ist er derzeit der am weitesten verbreitete Index.
Entsprechend den verschiedenen Kodierungsmethoden für Standortinformationen können knotenbasierte Indizes im Allgemeinen in die folgenden Kategorien unterteilt werden:
1. Präfixbasierte Indizes
sind hauptsächlich Indizes, die auf der Dewey-Kodierung [12] und der ORDPATH-Kodierung basieren der Literatur [13] Eine ähnliche Methode wird übernommen und eine Methode zur Komprimierung von ORDPATH angegeben, die auf die Indexorganisation von SQL Server 2005 angewendet wurde.
Die Grundidee der Präfixcodierung besteht darin, die Codierung des übergeordneten Knotens eines Knotens direkt als Präfix für die Codierung des Knotens zu verwenden. Um zu bestimmen, ob ein Knoten v ein Nachkomme eines anderen Knotens u ist, müssen Sie nur bestimmen ob die Kodierung von u das Präfix der Kodierung von v ist. . Eine wichtige Eigenschaft von Präfix-Kodierungsindizes ist ihre Wörterbuchreihenfolge: Für jeden Knoten u im Teilbaum mit Wurzel am Knoten r ist seine Präfix-Kodierung c(u) größer (kleiner als) sein linker Geschwister-Teilbaum (rechter Geschwister-Teilbaum). Die Präfix-Kodierung aller Knoten in . Daher können präfixbasierte Indizes nicht nur die Berechnung von Einschlussbeziehungen, sondern auch die Berechnung von Dokumentpositionsbeziehungen effektiv unterstützen.
2. Index basierend auf der Intervallcodierung
Für den Intervallcodierungsindex wird jedem Knoten im Baum T ein Intervallcode [Anfang, Ende] zugewiesen, der Folgendes erfüllt: Der Intervallcode eines Knotens enthält auch den Intervallcode seiner Nachkommenknoten Das heißt, der Knoten u im Baum T ist der Vorfahre des Knotens v. Genau dann, wenn
das erste Intervallkodierungsschema von start(u) die Dietz-Kodierung ist, wird jedem Knoten im Baum T eine Durchlaufsequenznummer vor der Bestellung zugewiesen und Post- Reihenfolgendurchlauf-Sequenznummerntupel. Da ein Vorfahrenknoten u im Baum T vor (nach) seinem Nachkommenknoten v in der Vorbestellungsdurchquerung (Nachbestellungsdurchquerung) erscheinen muss, sind die Knoten u und v eine Vorfahren-/Nachkommenbeziehung , genau dann, wenn pre(u)
Ein weiteres typisches Beispiel für einen Intervallkodierungsindex ist der XISS-Index, der jedem Knoten ein Zahlenpaar zuweist, wobei die Reihenfolge die erweiterte Vorordnungskodierung und die Größe die Nachkommen des Knotens sind. Für jeden Knoten X und Y in einem Dokumentbaum, genau dann, wenn order(x)
der XISS-Index die ursprüngliche Abfrageanweisung in Unterausdrücke zerlegt. Implementieren Sie dann die Abfrage für diese Unterausdrücke und verbinden Sie schließlich diese Zwischenergebnisse, um den Abfrageergebnissatz zu erhalten. Dadurch können Abfrageanweisungen mit Platzhalterzeichen besser unterstützt werden. Das endgültige Abfrageergebnis wird jedoch nach der Verkettung der einzelnen Zwischenergebnisse erhalten. Obwohl eine solche Methode tatsächlich alle Wildcard-Probleme lösen kann, dürfte die Verkettung solcher Zwischenergebnisse insbesondere bei einfachen Ausdrücken mit langen Pfaden sehr zeitaufwändig sein.
Der Vergleich zweier Indizierungsmechanismen
basiert hauptsächlich auf der Knotenverschmelzungsstrategie. Durch Techniken wie Knotenäquivalenz und Pfadäquivalenz wird eine Indexstruktur erhalten, die immer noch baumförmig ist Wenn Sie also eine Abfrage verarbeiten, müssen Sie im Wesentlichen immer noch den gesamten Indexbaum durchlaufen, um das Ergebnis zu erhalten. Pfadbasierte Indizes können einfache Pfadausdrucksabfragen sehr gut unterstützen, bei regulären Pfadausdrücken funktioniert dies jedoch nicht sehr gut.
Der knotenbasierte Index indiziert jeden Knoten durch Codierung. Die strukturelle Beziehung zwischen Knoten kann durch Codierung in konstanter Zeit bestimmt werden. Er kann reguläre Pfadausdrücke gut unterstützen, insbesondere bei der Abfragegenerierung, wenn es viele Zwischenergebnisse gibt. Der Join-Vorgang des Knotenindex ist teuer.
Pfadbasierte Indizierung und knotenbasierte Indizierung haben jeweils ihre eigenen Vor- und Nachteile, können sich jedoch gegenseitig ergänzen. Derzeit wird die knotenbasierte Indizierung in praktischen Anwendungen häufiger verwendet und die Forschung ist relativ ausgereift. Daher konzentriert sich die Forschung der Dameng Company zur XML-Indexstruktur hauptsächlich auf die knotenbasierte Indizierung und führt entsprechende Verbesserungen in Bezug auf die pfadbasierte Indizierung durch .