„XML“-Indextechnologie basierend auf einer relationalen Datenbank-Engine

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, haben Daten vom Typ XML stark zugenommen zur aktuellen Mainstream-Datenform werden. Daher ist die XML-Datenverwaltungstechnologie, insbesondere die XML-Datenabfragetechnologie, zu einem aktuellen Forschungsschwerpunkt geworden.

Im Vergleich zu relationalen Daten hat XML verschiedene Vorteile, sein größter 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 hat am 23. Januar 2007 XPath2.0 und XQuery1.0 als empfohlene Standards identifiziert und damit den vorherigen Wettbewerb zwischen verschiedenen Abfragesprachen beendet. 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 bestehender Datenbankprodukte wird eine sinnvollere Indexstruktur für die XML-Abfrage-Engine von Dameng entworfen, damit die Engine eine optimale Leistung erzielen kann.

Einführung in die XML-Indexierungstechnologie

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 Indizierungstechnologie einer der wichtigsten Faktoren bei der Bestimmung eines Datenbanksystems. Wenn für XML-Dokumente keine Indexstruktur 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 langfristiger Akkumulation relativ ausgereift ist, konzentriert sich diese Art der Indizierungstechnologie hauptsächlich auf die Funktion, Datensätze basierend auf Werten (und nicht auf Mustern mit bestimmten Beziehungen) zu lokalisieren Achten Sie nicht besonders auf 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 Hauptinhalt des XML-Index besteht darin, Muster zu entwerfen, die für die Matching-Technologie geeignet sind.

XML-Indexklassifizierung

Pfadbasierter XML-Index

Pfadbasierter Index basiert auf den Pfadinformationen von Knoten in der XML-Baumstruktur und verwendet eine bestimmte Reduktionsmethode. Die reduzierte Baumstruktur verwaltet nur unterschiedliche Pfadinformationen und es gibt keine zwei Knoten mit demselben Pfad. Zu den vorgeschlagenen Indizes gehören: DataGuides-Index, Index Fabric-Index, Adaptive Path Index für XML-Daten (APEX)

Der Dataguides-Index ist eine Verfeinerung ausgehend vom Wurzelknoten. Eine strukturelle Zusammenfassung des Pfads. Die durch die Verkettung von Kantenbeschriftungen gebildeten Zeichenfolgenpfade werden 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 Der String-Typ in Java wird verwendet, um einige große Dateien zu verarbeiten, die nicht streng definiert sind und in Form von Binärstreams gespeichert werden. Lassen Sie ihn daher den Typ byte [] verwenden und definieren Sie dann die Getter- und Setter-Methoden dieser beiden Eigenschaften Der relevante Code lautet wie folgt:

Der Dataguides-Index ist eine strukturelle Zusammenfassung des verfeinerten Pfads ausgehend vom Wurzelknoten. Die durch die Verkettung von Kantenbeschriftungen gebildeten Zeichenfolgenpfade werden 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 Markierungspfad zu jedem Elementknoten und fügt diese codierten Werte dann in den Patricia Trie-Baum ein XML-Daten entsprechend dem Pfad in der Abfrage der Zeichenfolge. 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 der im XPath-Standard definierten Nachkommen-oder-Selbst-Achse nicht effizient.

Aus diesem Grund hat APEX [14] das Abhängigkeits-XML eingeführt Informationen zur Datenabfrageverteilung: Vorab gespeicherte 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 aufzeichnen. 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 gut in ausgereifte relationale Datenbankverwaltungssysteme integriert werden kann, ist er derzeit der am weitesten verbreitete Index.

Je nach verschiedenen Kodierungsmethoden für Standortinformationen können knotenbasierte Indizes im Allgemeinen in die folgenden Kategorien unterteilt werden:

1. Präfixbasierter Index

Präfixbasierter Index Es handelt sich hauptsächlich um einen Index, der auf der Dewey-Codierung [12] basiert. Die ORDPATH-Codierung in der Literatur [13] verwendet eine ähnliche Methode und gibt eine Methode zum Komprimieren des ORDPATH an. Diese Methode wurde auf die Indexorganisation von SQL Server angewendet 2005.

Die Grundidee der Präfixkodierung besteht darin, die Kodierung des übergeordneten Knotens eines Knotens direkt als Präfix der Knotenkodierung zu verwenden, um zu bestimmen, ob ein Knoten v ein Nachkomme von ist Ein weiterer Knoten u, bestimmen Sie einfach Die Kodierung von u ist das Präfix der Kodierung von v. 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 Intervallcodierung

Für den Intervallcodierungsindex wird jedem Knoten im Baum T eine Intervallcodierung [Anfang, Ende] zugewiesen, die Folgendes erfüllt: das Intervall eines Knotens The Die Kodierung enthält die Intervallkodierung seiner Nachkommenknoten. Das heißt, der Knoten u im Baum T ist genau dann der Vorfahre des Knotens v, wenn start(u)

Das erste Intervallkodierungsschema ist die Dietz-Kodierung, jeder Knoten in Dem Baum T wird ein Tupel mit einer Durchlaufnummer vor der Bestellung und einer Durchlaufnummer nach der Bestellung zugewiesen. Da ein Vorfahrenknoten u im Baum T in der Durchquerung vor der Bestellung (Nachbestellungsdurchlauf) erscheinen muss, ist sein Nachkomme Knoten v Vorher (nachher) sind daher die Knoten u und v genau dann Vorfahren/Nachkommen-Beziehungen, wenn PRe(u)

Ein weiteres typisches Beispiel für einen intervallcodierten Index ist der XISS-Index, der jedem ein Zahlenpaar zuweist Knoten, wobei order der erweiterte Vorbestellungscode und size der Bereich der Nachkommen des Knotens ist. Für jeden Knoten X und Y in einem Dokumentbaum gilt genau dann, wenn order(x)

XISS-Index die ursprüngliche Abfrageanweisung in Unterausdrücke zerlegt. Implementieren Sie dann die Abfrage für diese Unterausdrücke und verknüpfen 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.

Vergleich zweier Indexierungsmechanismen

Die pfadbasierte Indizierung basiert hauptsächlich auf der Knotenzusammenführungsstrategie durch Techniken wie Knotenäquivalenz und Pfadäquivalenz, eine Indexstruktur, die viel kleiner als das Original ist Wenn ein Dokument abgerufen wird, ist seine Struktur immer noch ein Baum. Wenn Sie also eine Abfrage verarbeiten, müssen Sie grundsätzlich immer noch den gesamten Indexbaum durchlaufen, um die Ergebnisse zu erhalten. Pfadbasierte Indizes können einfache Pfadausdrucksabfragen sehr gut unterstützen, bei regulären Pfadausdrücken funktioniert dies jedoch nicht sehr gut.

Knotenbasierter Index indiziert jeden Knoten durch Kodierung. Die strukturelle Beziehung zwischen Knoten kann durch Kodierung in konstanter Zeit bestimmt werden. Er kann reguläre Pfadausdrücke gut unterstützen, insbesondere wenn die Abfrage generiert wird Bei vielen Zwischenergebnissen ist die Verknüpfungsoperation des Knotenindex 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 .

Das Obige ist der Inhalt der „XML“-Indizierungstechnologie, die auf einer relationalen Datenbank-Engine basiert. Weitere verwandte Inhalte finden Sie auf der chinesischen PHP-Website (www.php.cn).