HK71296A - Tree structure database system - Google Patents

Claims (8)

1. Ein Datenverarbeitungssystem bestehend aus einem Datenbanksystem für gemeinsamen Zugriff 12, 14, in dem mehrere Benutzer 10 mittels einer Baumstruktur gleichzeitig auf die Datenbank zugreifen können, wobei der Zugriff erste Operationen umfaßt, bei denen die Baumstruktur unverändert bleibt, sowie zweite Operationen, bei denen die Baumstruktur geändert wird, und wobei das Datenverarbeitungssystem über Mittel zur Ausführung einer aus mehreren Operationen bestehenden Transaktion sowie Mittel zur Speicherung der sequentiellen Positionen von Operationen, anhand derer eine Transaktion im Fall eines Systemausfalls rückgängig gemacht werden kann, verfügt, wobei das System dadurch gekennzeichnet ist, daß das Mittel zur Wiederherstellung über Mittel zur Speicherung einer Angabe der sequentiellen Position einer zweiten Operation aus einer Folge von Operationen, welche die Baumstruktur unmittelbar vor Beginn der Operation verändert haben, verfügt, ferner über Mittel zur Speicherung eines Kompensationsprotokollsatzes, der nach Beendigung der Operationsfolge auf diese Angabe verweist, sowie Mittel zum Rückgängigmachen der Operationen in der Transaktion durch einen Verweis auf die gespeicherte Angabe, falls das System vor Beendigung der Operationsfolge ausfällt, und zum Rückgängigmachen nur der nicht in der Folge enthaltenen Operationen bei einem Systemausfall, sofern die Folge durch einen Verweis auf den Protokollkompensationssatz abgeschlossen wurde.
2. Ein Datenverarbeitungssystem gemäß Anspruch 1, bei dem die Baumstruktur eine Indexbaumstruktur ist mit einem Root-Knoten und Schlüsselsatzverweisen auf Knoten einer nächstniedrigeren Ebene, der wiederum eine nächstniedrigere Knotenebene folgt, auf deren Knoten durch Schlüssel im nächsthöheren Knoten verwiesen wird, bis hin zu Endknoten mit Schlüsseln, die auf die Daten in der Datenbank verweisen, wobei in jeder Operation die Knoten mittels der Schlüsselsatzverweise auf einen vorhandenen Endknoten durchlaufen werden, und das Mittel zur Anforderung bedingter Zugriffsbeschränkungen bei Erreichen eines Schlüsselsatzes im Endknoten, Mittel zum Zugriff auf die im Verweis bezeichneten Daten in der Datenbank nach Gewährung der Zugriffsbeschränkung, Mittel zur Anforderung unbedingter Zugriffsbeschränkungen bei Nichtgewährung der bedingten Zugriffsbeschränkung sowie Mittel zum Durchlaufen der Knoten vom Root-Knoten zu einem neuen Endknoten im Fall einer wesentlichen Änderung des vorhandenen Endknotens enthält.
3. Ein Datenverarbeitungssystem gemäß Anspruch 2, das Mittel enthält, um den Endknoten nach Gewährung der unbedingten Zugriffsbeschränkung daraufhin zu prüfen, ob ein im Endknoten bezeichneter Schlüsselsatz der erste Schlüsselsatz in dem Knoten ist.
4. Ein Datenverarbeitungssystem gemäß Anspruch 3, das Mittel enthält, um den Endknoten daraufhin zu prüfen, ob ein darin enthaltener Schlüsselsatz kleiner ist als ein angeforderter Schlüsselsatz.
5. Ein Verfahren zum Betrieb eines Datenverarbeitungssystems bestehend aus einem Datenbanksystem, das mittels einer Baumstruktur den gleichzeitigen Zugriff mehrerer Benutzer auf Daten in der Datenbank ermöglicht, wobei der Zugriff erste Operationen enthält, bei denen die Baumstruktur unverändert bleibt, sowie zweite Operationen, bei denen die Baumstruktur verändert wird, wobei das Verfahren folgende Schritte umfaßt: Ausführen einer Transaktion bestehend aus mehreren solchen Operationen; Speichern einer Angabe der sequentiellen Position einer zweiten Operation aus einer Folge von Operationen, welche die Baumstruktur verändern, unmittelbar vor Beginn der Operationsfolge; Speichern eines Kompensationsprotokollsatzes, der nach Abschluß der Folge auf diese Angabe verweist; Rückgängigmachen der Operationen einer Transaktion durch Verweis auf die gespeicherte Angabe, falls das System vor Beendigung der Folge ausfällt; sowie Rückgängigmachen nur der nicht in der Folge enthaltenen Operationen bei einem Systemausfall, sofern die Folge abgeschlossen ist, anhand des Kompensationsprotokollsatzes.
6. Ein Verfahren gemäß Anspruch 5, bei dem die Baumstruktur eine Indexbaumstruktur ist mit einem Root-Knoten und Schlüsselsatzverweisen auf Knoten einer nächstniedrigeren Ebene, der wiederum eine nächstniedrigere Knotenebene folgt, auf deren Knoten jeweils durch Schlüssel im nächsthöheren Knoten verwiesen wird, bis hin zu Endknoten mit Schlüsseln, die auf die Daten in der Datenbank verweisen, wobei in jeder Operation die Knoten mittels der Schlüsselsatzverweise bis zu einem vorhandenen Endknoten durchlaufen werden, und das außerdem folgende Schritte enthält: Anforderung bedingter Zugriffsbeschränkungen bei Erreichen eines Schlüsselsatzes im Endknoten; Zugriff auf die im Verweis bezeichneten Daten in der Datenbank nach Gewährung der Zugriffsbeschränkung; Anforderung einer unbedingten Zugriffsbeschränkung, falls die bedingte Zugriffsbeschränkung nicht gewährt wird; Durchlaufen der Knoten vom Root-Knoten bis zu einem neuen Endknoten, wenn der bestehende Endknoten wesentlich verändert wurde.
7. Ein Verfahren gemäß Anspruch 6, bei dem der Endknoten nach Gewährung der unbedingten Zugriffsbeschränkung daraufhin geprüft wird, ob ein im Endknoten bezeichneter Schlüsselsatz der erste Schlüsselsatz des Knotens ist.
8. Ein Verfahren gemäß Anspruch 7, bei dem ferner geprüft wird, ob ein Schlüsselsatz im Endknoten kleiner ist als der angeforderte Schlüsselsatz.