DE112012006412T5

DE112012006412T5 - System zur verteilten Datensuche, Verfahren zur verteilten Datensuche und Managementcomputer

Info

Publication number: DE112012006412T5
Application number: DE112012006412.7T
Authority: DE
Inventors: c/o Hitachi Ltd. Miyata Yasushi; c/o Hitachi Ltd. Nishiyama Hiroyasu
Original assignee: Hitachi Ltd
Current assignee: Hitachi Ltd
Priority date: 2012-05-24
Filing date: 2012-05-24
Publication date: 2015-02-12
Also published as: JPWO2013175611A1; JP5844895B2; WO2013175611A1; US9773061B2; US20150120736A1

Abstract

Ein Verwaltungscomputer, der mit mehreren Suchausführungscomputern verbunden ist, umfasst: einen Manger zur verteilten Verwaltung, der Graphen empfängt, die eine Relation halten, die einen Datenewert verbindet, und mit einer Gruppe konfiguriert ist, die durch die Relation verbunden ist, und dieselben unter mehreren Suchausführungscomputern verteilt; und einen Manger zur verteilten Suche, der, wenn eine Suchbedingung empfangen wird, die Suchbedingung zu den mehreren Suchausführungscomputern überträgt und Suchergebnisse empfängt. Der Manager zur verteilten Verwaltung gruppiert die Graphen mit entsprechenden Relationen, segmentiert die Graphen, die der Gruppe zugeordnet sind, und positioniert dieselben in den mehreren Suchausführungscomputern. Der Manager zur verteilten Suche überträgt Suchbedingungen mit Suchbedingungen der Relationen zwischen den Daten und Suchbedingungen des Datenwerts zu jedem der mehreren Suchausführungscomputer und veranlasst, dass sie Suche parallel ausgeführt wird.

Description

HINTERGRUND
Diese Erfindung bezieht sich auf eine Verbesserung in einem Computersystem und ein Verfahren zum Verteilen und Speichern von Graphen auf mehrere Computer und paralleles Suchen der verteilten Graphen.
Graphen werden verwendet, um gegebene Relationen zwischen Datenteilen auszudrücken. Ein Graph ist ein Satz von Daten, in dem ein Datenteil einen Datenwert und mindestens eine Relation mit einem anderen Datenteil hält und mit den anderen Datenteilen durch die Relationen verbunden ist.
Es existieren eine Graphendatenbankvorrichtung zum Speichern und Verwalten von Graphen und eine Graphensuchvorrichtung zum Extrahieren eines gewünschten Graphen aus den in der Graphendatenbank gespeicherten Graphen. Die Graphensuchvorrichtung extrahiert einen Graphen oder Graphen, die den Bedingungen entsprechen, die mit einem Datenwert und einer Relation von Datenteilen definiert sind, aus der Graphendatenbankvorrichtung.
Um das Suchen einer massiven Anzahl von Graphen zu beschleunigen, ist eine Technik bekannt, die Graphen zwischen mehreren Serverknoten verteilt und aufteilt und parallele Suchen an den Serverknoten durchführt.
Das Empfangen und Zusammenführen von Ergebnissen der parallelen Suchen in den mehreren Serverknoten an einem Managementserver führt zum Erhalten eines Ergebnisses mit denselben Graphen, die durch Suchen aller Graphen erhalten werden. Es sollte jedoch beachtet werden, dass, wenn zusammengehörende Daten unter mehreren Serverknoten verteilt sind, die mehreren Serverknoten bestimmen müssen, ob die zusammengehörenden Daten Bedingungen zueinander erfüllen, da beim Suchen von Graphen die Suchbedingungen aus einem Datenwert und einer Datenrelation bestehen. Die Bestimmung der Bedingungen in den mehreren Serverknoten könnte Kommunikationen zwischen Serverknoten erfordern, was eine Verzögerung in der Verarbeitung verursacht. Um diese Verzögerung zu verhindern, offenbart die Nicht-Patentliteratur 1 eine Technik, die durch Relationen verbundene Daten im gleichen Serverknoten speichert.
Die in der Nicht-Patentliteratur 1 offenbarte Technik beseitigt Kommunikationen zwischen den Serverknoten beim Suchen; die für jeden Serverknoten erforderliche Suchzeit ist die Zeit, die durch Suchen der Graphen benötigt wird, die in jedem Serverknoten gehalten werden, um Graphen zu extrahieren, die den Bedingungen entsprechen, die mit einem Datenwert und einer Datenrelation festgelegt sind. Da jeder Serverknoten eine Suche parallel durchführt, hängt die Zeit zum Erhalten aller Suchergebnisse vom Serverknoten ab, der die längste Zeit beim Suchen braucht. Die Details der Suche sind allen Servern gemeinsam; folglich hängt die Zeit zum Erhalten aller Suchergebnisse von der Anzahl von durch jeden Serverknoten zu suchenden Graphen ab.
Nun werden zu suchende Graphen erläutert. Im Allgemeinen verwendet das Suchen von Daten Markierungen, die Index genannt werden, um ein oder mehrere Datenteile zu extrahieren, die einem Teil der oder allen Suchbedingungen entsprechen. Der Index für die Graphen sind Verzeichnisdaten, in denen Datenwerte und Datenrelationen in einer spezifischen Reihenfolge, sortiert sind. Das Extrahieren eines Datenbereichs, der einem Teil oder allen Suchbedingungen entspricht, aus diesen Verzeichnisdaten führt zur Erfassung von gewollten Graphen ohne Prüfen der Vollständigkeit der Graphen. Wenn an dieser Stelle ein Datenbereich extrahiert wird, der einem Teil der Suchbedingungen entspricht, ist es erforderlich, unter der Annahme, dass der extrahierte Datenbereich mögliche Lösungen bereitstellt, zu bestimmen, ob jede mögliche Lösung den restlichen Suchbedingungen entspricht. Die Anzahl von möglichen Lösungen entspricht der Anzahl von zu suchenden Graphen. Wenn kein Index vorgesehen ist, sind alle Graphen mögliche Lösungen.
Die Anzahl von zu suchenden Graphen hängt von den Details der Suche und der Zuweisung der Graphen zu den Serverknoten ab. Wenn ein spezifischer Server mehr Graphen aufweist als die anderen Server, nimmt folglich die Last für den spezifischen Server zu, was eine Verzögerung beim Suchen verursacht. Um dieses Problem zu lösen, offenbart die Patentliteratur 1 eine Technik, die die Datensätze der Details von vergangenen Suchen und das Volumen von gesuchten Daten hält und Daten von einem Serverknoten mit einem großen Volumen von gesuchten Daten einem Serverknoten mit einem kleinen Volumen neu zuweist, um einen Lastausgleich zu erreichen.
Entgegenhaltungsliste

Patentliteratur 1: JP H06-259478 A
Nicht-Patentliteratur 1: Huang, J. Abadi, D. und Ren, K., ”Scalable SPARQL Querying of Large RDF Graphs”, VLDB Endowment Inc., Band 4 (VLDB 2011)

ZUSAMMENFASSUNG
Bei der Anwendung der in der Patentliteratur 1 offenbarten Technik auf ein System, das Suchgraphen hält, könnte, wenn das Übertragen zur Neuzuweisung von Graphen von einem Serverknoten zu einem anderen die Last erhöht, das Suchen verzögert werden. Ferner führt die in der Patentliteratur 1 offenbarte Technik diese Bestimmung unter Verwendung der Details von vergangenen Suchen durch. Folglich existiert ein Problem, dass beim Hinzufügen eines neuen Graphen, ob der neue Graph häufig abzurufende Daten umfasst, nicht bestimmt werden kann, so dass der Serverknoten, dem der Graph zuzuweisen ist, nicht bestimmt werden kann, um den Lastausgleich zu erreichen.
Diese Erfindung zielt darauf ab, die Suchleistung in einem System zu verbessern, das Graphen verwaltet, die unteren mehreren Serverknoten verteilt sind. Das System verteilt Daten zu mehreren Serverknoten und führt das Ergebnis zusammen, dass die Suchverarbeitung desselben Inhalts durch jeden Serverknoten durchgeführt wurde.
Ein repräsentativer Aspekt der vorliegenden Offenbarung ist wie folgt. Ein System zur verteilten Datensuche, das umfasst: einen Managementcomputer mit einem Prozessor und einem Speicher; mehrere Suchausführungscomputer, die jeweils einen Prozessor und einen Speicher umfassen; und ein Netz, das den Managementcomputer und die mehreren Suchausführungscomputer verbindet, wobei der Managementcomputer umfasst: einen Manager zur verteilten Verwaltung zum Empfangen von Graphen, wobei jeder der Graphen mindestens eine Relation hält, die einen Datenwert mit einem anderen Datenwert verbindet, und aus Datenteilen besteht, die durch die mindestens eine Relation verbunden sind, und Verteilen der Graphen zu den mehreren Suchausführungscomputern; und einen Manager zur verteilten Suche zum Senden von Suchbedingungen zu den mehreren Suchausführungscomputern beim Empfang der Suchbedingungen und Empfangen von Suchergebnissen von den mehreren Suchausführungscomputern, wobei jeder der Suchausführungscomputer umfasst: ein Graphenspeichermodul zum Speichern von Graphen, die vom Managementcomputer empfangen werden; und ein Suchausführungsmodul zum Suchen der Graphen mit den Suchbedingungen, die vom Managementcomputer empfangen werden, und Zurückgeben eines Suchergebnisses zum Managementcomputer, wobei der Manager zur verteilten Verwaltung des Managementcomputers Graphen mit mindestens einer gemeinsamen Relation als Gruppe klassifiziert und die Graphen, die zur Gruppe gehören, zu den mehreren Suchausführungscomputern verteilt und zuweist, wobei der Manager zur verteilten Suche des Managementcomputers Suchbedingungen, einschließlich einer Suchbedingung für eine Datenrelation und einer Suchbedingung für einen Datenwert, zu jedem der mehreren Suchausführungscomputer sendet, um die Durchführung einer parallelen Suche anzufordern, wobei das Suchausführungsmodul in jedem der mehreren Suchausführungscomputer Graphen, die der Suchbedingung für die Datenrelation entsprechen, als mögliche Lösungen extrahiert und einen Bedingungsvergleich an Datenwerten, die in den Graphen enthalten sind, die als mögliche Lösungen extrahiert werden, mit der Suchbedingung für den Datenwert durchführt, um einen Datenteil, dessen Datenwert der Suchbedingung für den Datenwert entspricht, als Suchergebnis zu erfassen.
Ein Aspekt dieser Erfindung kann die Suchleistung eines Systems verbessern, das Graphen verwaltet, die unter mehreren Serverknoten verteilt sind. Probleme, Konfigurationen und andere Effekte als die vorstehend beschriebenen werden in der folgenden Beschreibung der Ausführungsformen verdeutlicht.
KURZBESCHREIBUNG DER ZEICHNUNGEN
1 ist ein Blockdiagramm, das ein Konfigurationsbeispiel eines Computersystems zum Implementieren der verteilten Verwaltung und Suche von Graphen gemäß einer ersten Ausführungsform dieser Erfindung darstellt.
2 ist ein Blockdiagramm, das Funktionsmodule, die im Manager zur verteilten Graphendatenverwaltung enthalten sind, gemäß der ersten Ausführungsform dieser Erfindung darstellt.
3 ist ein Blockdiagramm, das Beispiele von Funktionsmodulen im Manager zur verteilten Graphendatensuche darstellt.
4 ist ein Ablaufplan, der ein Beispiel des Klassifizierens eines Graphen in eine Gruppe darstellt, das im Manager zur verteilten Graphendatenverwaltung gemäß der ersten Ausführungsform dieser Erfindung durchgeführt wird.
5 ist ein Ablaufplan, der ein Beispiel der Zuweisung eines Graphen darstellt, die im Manager zur verteilten Graphendatenverwaltung durchgeführt wird.
6 ist eine Ansicht, die ein Beispiel der Gruppenmanagementtabelle gemäß der ersten Ausführungsform dieser Erfindung darstellt.
7 ist eine Ansicht, die ein Beispiel der Gruppenzuweisungs-Managementtabelle gemäß der ersten Ausführungsform dieser Erfindung darstellt.
8 ist eine Ansicht, die ein Beispiel der Zuweisungsmanagementtabelle gemäß der ersten Ausführungsform dieser Erfindung darstellt.
9 ist ein Ablaufplan, der ein Beispiel der Verarbeitung für den Managementcomputer gemäß einer zweiten Ausführungsform dieser Erfindung darstellt.
10 ist ein Ablaufplan, der ein Beispiel der Verarbeitung des Abfrageausführungsmoduls gemäß einer dritten Ausführungsform dieser Erfindung darstellt.
11 ist eine Ansicht, die ein Beispiel einer Relationsabrufzählwert-Managementtabelle gemäß einer dritten Ausführungsform dieser Erfindung darstellt.
12 ist ein Ablaufplan, der ein Beispiel der Verarbeitung des Managers zur verteilten Graphendatenverwaltung, um Relationen, die verwendet werden sollen, um eine Gruppe zu erzeugen, aus statistischen Informationen zu extrahieren, gemäß der dritten Ausführungsform dieser Erfindung darstellt.
13 ist ein Blockdiagramm, das ein Beispiel von Daten, die in der Speichervorrichtung jedes Suchausführungscomputers gespeichert sind, gemäß der dritten Ausführungsform dieser Erfindung darstellt.
14 ist ein Ablaufplan, der ein Beispiel des Managers zur verteilten Graphendatenverwaltung, um das Erscheinen von Relationen zu zählen, gemäß einer vierten Ausführungsform dieser Erfindung darstellt.
15 ist eine Ansicht, die ein Beispiel der Relationserscheinungszählwert-Managementtabelle gemäß der vierten Ausführungsform dieser Erfindung darstellt.
16 ist ein Ablaufplan, der ein Beispiel der Verarbeitung des Managers zur verteilten Graphendatenverwaltung, um einen Graphen in eine Gruppe zu klassifizieren, ausschließlich Relationen, die in niedriger Häufigkeit vorkommen, gemäß der vierten Ausführungsform dieser Erfindung darstellt.
17 ist ein Blockdiagramm, das eine Konfiguration des Managers zur verteilten Graphendatenverwaltung gemäß der vierten Ausführungsform dieser Erfindung darstellt.
18 ist ein Ablaufplan, der die Verarbeitung für den Manager zur verteilten Graphendatenverwaltung, um Graphen zu Suchausführungscomputern zu verteilen und zuzuweisen, gemäß einer fünften Ausführungsform dieser Erfindung darstellt.
19 ist ein Blockdiagramm, das ein Beispiel einer Konfiguration des Managementcomputers gemäß einer sechsten Ausführungsform dieser Erfindung darstellt.
20 ist ein Ablaufplan, der ein Beispiel der Verarbeitung des Managementcomputers, um die Kapazität für Graphendaten zu managen, gemäß der sechsten Ausführungsform dieser Erfindung darstellt.
21 ist ein Blockdiagramm, das ein Beispiel eines Computersystems für die verteilte Graphendatenverwaltung und Graphendatensuche gemäß einer achten Ausführungsform dieser Erfindung darstellt.
22 ist ein Diagramm, das ein Beispiel von Graphen darstellt, um diese Erfindung anzuwenden.
23 ist ein Diagramm, das ein Beispiel einer Suchabfrage darstellt, um diese Erfindung anzuwenden.
AUSFÜHRLICHE BESCHREIBUNG DER AUSFÜHRUNGSFORMEN
Nachstehend werden Ausführungsformen dieser Erfindung im Einzelnen mit Zeichnungen beschrieben.
Ausführungsform 1
Die Ausführungsform 1 beschreibt ein Beispiel eines Systems zur verteilten Graphendatenverwaltung und Graphendatensuche. Um Graphen mit Bedingungen für einen Datenwert und eine Datenrelation zu suchen, klassifiziert das System Graphen, die den Suchbedingungen entsprechen (Bedingungen für den Datenwert und die Datenrelation), als Gruppe von zu suchenden Graphen. Ferner verteilt und weist das System die Gruppe von Graphen zu mehreren Suchausführungscomputern oder Suchausführungsknoten zu und sucht die verteilten Graphen. 1 stellt ein Konfigurationsbeispiel eines Computersystems zum Implementieren der verteilten Verwaltung und Suche von Graphen in der Ausführungsform 1 dar. 1 ist ein Blockdiagramm, das ein Beispiel eines Computersystems für die verteilte Verwaltung und Suche von Graphen darstellt.
Das Computersystem zum Implementieren der verteilten Verwaltung und Suche von Graphen, das in 1 dargestellt ist, umfasst einen Managementcomputer 101 zum Managen der Verwaltung und Suche von Graphen, mehrere Suchausführungscomputer 102-1 bis 102-n (n ist irgendeine natürliche Zahl) zum Halten und Suchen von Graphen, einen Client 80 zum Ausgeben einer Anforderung für die Suche und ein Netz 140, das diese Computer verbindet.
Der Managementcomputer 101 kann mit einem Computer mit einem Speicher 111, einer CPU 112, einer Kommunikationsvorrichtung 113, einer Speichervorrichtung 114 mit einer Hilfsspeichervorrichtung wie z. B. einer Festplatte, einer Eingabevorrichtung 115 und einer Anzeigevorrichtung 116 implementiert werden.
Jeder der mehreren Suchausführungscomputer 102-1 bis 102-n kann auch mit einem Computer implementiert werden, der derselbe wie der Managementcomputer 101 ist. Die Suchausführungscomputer 102-1 bis 102-n sind allgemein mit einem Bezugszeichen, 102 bezeichnet.
Die Eingabevorrichtung 115 des Managementcomputers 101 umfasst eine Tastatur, eine Maus und/oder ein Berührungsfeld und ist eine Vorrichtung zum Eingeben der Befehle des Benutzers wie z. B. eines Befehls, um ein Programm zu starten. Die Anzeigevorrichtung 116 kann ein Monitor sein und zeigt Zustande und Ergebnisse der Verarbeitung im Managementcomputer 101 an. Die CPU 112 führt Programme aus, die im Speicher 111 gespeichert sind. Die Kommunikationsvorrichtung 113 tauscht Daten und Befehle mit anderen Vorrichtungen unter Verwendung einer Kommunikationsleitung wie z. B. eines LAN aus. die Speichervorrichtung 114 speichert Programme 121 und Daten 122 für den Managementcomputer 101, um die Verarbeitung durchzuführen. Der Speicher 111 speichert Programme 121, die vom Managementcomputer 101 abgearbeitet werden, und vorübergehende Daten 122.
Diese Ausführungsform schafft eine Beschreibung unter Verwendung eines Konfigurationsbeispiels, in dem der Managementcomputer 101 und die Suchausführungscomputer 102 physikalisch unabhängig sind; diese Erfindung ist jedoch nicht auf eine solche Konfiguration begrenzt und alle oder ein Teil der Computer können logisch konfiguriert sein.
Um die verteilte Zuweisung von Graphen unter mehreren Suchausführungscomputern 102 zu erreichen, klassifiziert der Managementcomputer 101 einen zu speichernden empfangenen Graphen als Gruppe mit denselben Datenrelationen beim Empfang derselben. Der Managementcomputer 101 wählt einen Suchausführungscomputer 102 aus, der die wenigsten Graphen derselben Gruppe hält, und sendet den Graphen 70 zum Suchausführungscomputer 102 mit der Kommunikationsvorrichtung 113. Der Suchausführungscomputer 102 speichert den mit der Kommunikationsvorrichtung 53 empfangenen Graphen in der Speichervorrichtung 54 als Graphen 70.
Auf dem Managementcomputer 101 zu laufende Programme, um die verteilte Verwaltung und Suche von Graphen zu implementieren, werden beschrieben. Die CPU 112 des Managementcomputers 101 lädt ein Programm 121 und Daten 112, die in der Speichervorrichtung 114 gespeichert sind, in den Speicher 111 und führt das Programm 121 aus. Das Programm 121 schafft einen Manager 131 zur verteilten Graphendatenverwaltung und einen Manager 132 zur verteilten Graphendatensuche. Unter Verwendung dieser Programme sendet und empfängt der Managementcomputer 101 Daten zu und von mehreren Suchausführungscomputern durch die Kommunikationsvorrichtungen, um die verteilte Suche und Verwaltung von Graphen zu implementieren.
Die CPU 112 arbeitet gemäß Programmen für Funktionsmodule, um als Funktionsmodule zum Implementieren von vorbestimmten Funktionen zu arbeiten. Die CPU 112 arbeitet beispielsweise gemäß einem Managementprogramm zur verteilten Graphendatenverwaltung, um als Manager 131 zur verteilten Graphendatenverwaltung zu funktionieren. Dasselbe gilt für die anderen Programme. Ferner arbeitet die CPU 112 als Funktionsmodule zum Durchführen von mehreren Prozessen, die von jedem Programm ausgeführt werden. Die Computer und das Computersystem sind Vorrichtungen und ein System mit diesen Funktionsmodulen.
Die Informationen wie z. B. Programme und Tabellen zum Implementieren der Funktionen des Managers 131 zur verteilten Graphendatenverwaltung und des Managers 132 zur verteilten Graphendatensuche können in einer Speichervorrichtung wie z. B. im Speicherbereich 114, einem nichtflüchtigen Halbleiterspeicher, einem Festplattenlaufwerk oder einem SSD (Festkörperlaufwerk) oder einem computerlesbaren nichtflüchtigen Datenspeichermedium wie z. B. einer IC-Karte, einer SD-Karte oder einer DVD gespeichert werden.
Auf jedem Suchausführungscomputer 102 zu laufende Programme zum Schaffen der verteilten Verwaltung und Suche von Graphen werden beschrieben. Die CPU 52 des Suchausführungscomputers 102 lädt ein Programm 71 und Daten 72, die in der Speichervorrichtung 54 gespeichert sind, in den Speicher 51 und führt das Programm 71 aus. Das Programm 71 umfasst ein Abfrageausführungsmodul 60. Das Abfrageausführungsmodul 60 führt eine Suche der Graphen 70 mit Suchbedingungen aus, die vom Managementcomputer 101 empfangen werden, und gibt ein Suchergebnis an den Managementcomputer 101 zurück. Die Speichervorrichtung 54 speichert das Programm 71 und fungiert außerdem als Speichermodul zum Speichern von Graphen und speichert ferner einen Index der Graphen 70 als Daten 72.
Der Client 80 ist ein Computer mit einer CPU, einem Speicher, einer Kommunikationsvorrichtung, einer Eingabevorrichtung und einer Anzeigevorrichtung, die nicht gezeigt sind, und sendet Suchbedingungen (oder eine Suchabfrage) als Anforderung für die Suche zum Managementcomputer 101.
2 ist ein Blockdiagramm, das Funktionsmodule darstellt, die im Manager 131 zur verteilten Graphendatenverwaltung enthalten sind, der ein in den Speicher 111 des Managementcomputers 101 zu ladendes und auszuführendes Programm ist, um die verteilte Verwaltung von Graphen zu implementieren.
Das für den Managementcomputer 101 auszuführende Programm, um als Manager zur verteilten Graphendatenverwaltung zu fungieren, umfasst ein Graphendatenempfangsmodul 201, eine Relationsextraktionseinrichtung 202, eine Gruppenerzeugungseinrichtung 203, eine Gruppeninformationshalteeinrichtung 204, einen Datenklassifizierer 205, ein Datenzuweisungsbestimmungsmodul 206, eine Halteeinrichtung 207 für verteilte Knoteninformationen, ein Graphendatenliefermodul 208 und später beschriebene Tabellen.
Das Graphendatenempfangsmodul 201 empfängt Graphen, die gemanagt werden soll, durch die Eingabevorrichtung 115 und die Kommunikationsvorrichtung 113. Die Relationsextraktionseinrichtung 202 extrahiert Datenrelationen, die in jedem der empfangenen Graphen enthalten sind. In dieser Beschreibung ist ein Graph ein Satz von Daten oder Datenteilen, die durch Relationen verbunden sind; wie in 22 gezeigt, weist beispielsweise ein Datenteil eines Stadtnamens Relationen wie z. B. Ortsinformationen (Breitengrad und Längengrad) und Zugehörigkeit (Land) auf und ist durch die Relationen verbunden, um einen Satz von Daten zu bilden. Der Graph in 22 gibt an, dass ein Datenwert eines Stadtnamens ”YOKOHAMA” mit einem Datenwert eines Ländernamens ”JAPAN” durch eine Relation von ”GEHÖRT_ZU” verbunden ist. Der Datenwert des Stadtnamens ”YOKOHAMA” ist auch mit dem Datenwert ”35,47, 139,63” durch eine Relation von ”BREITENGRAD, LÄNGENGRAD” verbunden. Die Relationsextraktionsvorrichtung 202 extrahiert diese Relationen, die Datenteile verbinden.
Die Gruppenerzeugungseinrichtung 203 erzeugt Graphengruppen mit jeweils extrahierten Datenrelationen als Elemente und managt die IDs der erzeugten Gruppen mit den Relationen der Elemente nach Gruppe in einer Gruppenmanagementtabelle 600. Das heißt, die Gruppenerzeugungseinrichtung 203 behandelt eine oder mehrere Relationen, die in Elementen unterschiedlich sind, als unterschiedliche Gruppe und fügt einen neuen Eintrag zur Gruppenmanagementtabelle 600 hinzu, wenn eine neue Gruppe erzeugt wird. Die Gruppenmanagementtabelle 600 wird im Speicher 111 durch die Gruppeninformationshalteeinrichtung 204 gehalten. 6 ist eine Ansicht, die ein Beispiel der Gruppenmanagementtabelle 600 darstellt. In der Gruppenmanagementtabelle 600 umfasst ein Eintrag (oder ein Datensatz) eine Gruppen-ID 601 zum Speichern des Identifizierers einer Graphengruppe und eine Relationsliste 602 zum Speichern von Elementen, die Datenrelationen angeben.
Der Datenklassifizierer 205 identifiziert mit Bezug auf die Gruppeninformationen (Gruppenmanagementtabelle 600), die durch die Gruppeninformationshalteeinrichtung 204 gehalten werden, eine Gruppe (Gruppen-ID 601) mit Elementen, die zu den Datenrelationen identisch sind, die im empfangenen Graphen enthalten sind, als Gruppe, um den Graphen aufzunehmen, und managt sie in einer Gruppenzuweisungsmanagementtabelle 700.
7 ist eine Ansicht, die ein Beispiel der Gruppenzuweisungsmanagementtabelle 700 darstellt. In der Gruppenzuweisungsmanagementtabelle 700 umfasst ein Eintrag (oder ein Datensatz) eine Graphen-ID 701 zum Speichern des Identifizierers eines Graphen und eine Gruppen-ID 702 zum Speichern einer Gruppen-ID 601 in der Gruppenmanagementtabelle 600.
Das Datenzuweisungsbestimmungsmodul 206 wählt einen Suchausführungscomputer 102 mit den wenigsten Graphen aus, die der Gruppen-ID 801 zugewiesen sind, die zur Gruppen-ID identisch ist, die für den Graphen identifiziert ist.
Das heißt, das Datenzuweisungsbestimmungsmodul 206 wählt mit Bezug auf die in 8 dargestellte Zuweisungsmanagementtabelle 800 einen Suchausführungscomputer, der die geringste (oder geringere) Anzahl in den Anzahlen von zugewiesenen Graphen 802-1 bis 802-n angibt, unter den Suchausführungscomputern 102-1 bis 102-n für die Gruppen-ID 801 aus, die zur Gruppen-ID 601 identisch ist, die mit 6 identifiziert ist.
Das Datenzuweisungsbestimmungsmodul 206 bestimmt die Zuweisung des mit einer Graphen-ID 701 versehenen Graphen zum ausgewählten Ausführungscomputer 102.
Die Halteeinrichtung 207 für verteilte Knoteninformationen hält Informationen über zugewiesene Gruppen für das Datenzuweisungsbestimmungsmodul 206, um festzustellen, wo ein Graph zugewiesen werden soll. 8 ist eine Ansicht, die ein Beispiel der Zuweisungsmanagementtabelle 800 zum Halten von Informationen über zugewiesene Gruppen darstellt. Die Zuweisungsmanagementtabelle 800 hält die Anzahlen von Graphen, die in individuellen Suchausführungscomputern 102 nach Gruppe gespeichert sind, als Informationen über zugewiesene Gruppen.
Die Zuweisungsmanagementtabelle 800 umfasst Gruppen-IDs 801 zum Speichern der Identifizierer von Graphengruppen und der Anzahlen von Graphen-IDs, die in 7 zugewiesen sind, als die Anzahlen von Graphen 802-1 bis 802-n, die Suchausführungscomputern 102-1 bis 102-n zugewiesen sind.
Das Graphendatenliefermodul 208 liefert einen Graphen 70 zum bestimmten Suchausführungscomputer 102 unter Verwendung der Kommunikationsvorrichtung 53. Der Suchausführungscomputer 102 speichert den empfangenen Graphen 70 in der Speichervorrichtung 54.
4 ist ein Ablaufplan, der ein Beispiel der Klassifikation eines Graphen in eine Gruppe darstellt, die im Manager 131 zur verteilten Graphendatenverwaltung durchgeführt wird. Die Verarbeitung, um einen empfangenen Graphen in eine Gruppe zu klassifizieren, wird gemäß dem in 4 dargestellten Ablaufplan beschrieben. Die Verarbeitung in 4 wird unter Verwendung des Graphendatenempfangsmoduls 201, der Relationsextraktionseinrichtung 202, der Gruppenerzeugungseinrichtung 203, der Gruppeninformationshalteeinrichtung 204 und des Datenklassifizierers 205 unter den Funktionsmodulen, die im Manager 131 zur verteilten Graphendatenverwaltung enthalten sind, durchgeführt.
Zuerst empfängt das Graphendatenempfangsmodul 201 einen Graphen durch die Kommunikationsvorrichtung 113 des Managementcomputers 101 (Schritt 401) und sendet ihn zur Relationsextraktionseinrichtung 202. Die Relationsextraktionseinrichtung 202 extrahiert alle Datenrelationen, die im empfangenen Graphen enthalten sind, und sendet sie zur Gruppenerzeugungseinrichtung 203 (Schritt 402).
Die Gruppenerzeugungseinrichtung 203 erfasst die Gruppenmanagementtabelle 600 von der Gruppeninformationshalteeinrichtung 204 und bestimmt, ob irgendeine Gruppen-ID 601 existiert, bei der Elemente von Relationen, die in der erfassten Relationsliste 602 enthalten sind, vollständig gleich sind wie alle Relationen, die durch die Relationsextraktionseinrichtung 202 extrahiert werden.
Wenn eine entsprechende Gruppen-ID 601 existiert, erzeugt die Gruppenerzeugungseinrichtung 203 eine Graphen-ID 701 zum eindeutigen Identifizieren des empfangenen Graphen und fügt einen neuen Eintrag zur Gruppenzuweisungsmanagementtabelle 700 hinzu, um die Graphen-ID 701 der Gruppen-ID 702 in einer Eins-zu-Eins-Entsprechung zuzuordnen (Schritt 406).
Wenn keine entsprechende Gruppen-ID 601 bei der Bestimmung im vorangehenden Schritt 404 existiert, geht die Gruppenerzeugungseinrichtung 203 zu Schritt 405 weiter. Die Gruppenerzeugungseinrichtung 203 erzeugt eine Gruppe mit allen durch die Relationsextraktionseinrichtung 202 extrahierten Relationen in einer Relationsliste 602 und eine Gruppen-ID 601 zum eindeutigen Identifizieren dieser Gruppe und fügt einen neuen Eintrag zur Gruppenmanagementtabelle 600 hinzu (Schritt 405).
Anschließend erzeugt wie in dem Fall, in dem eine entsprechende Gruppen-ID 601 existiert, die Gruppenerzeugungseinrichtung 203 eine Graphen-ID 701 zum eindeutigen Identifizierten des empfangenen Graphen und fügt einen neuen Eintrag zur Gruppenzuweisungsmanagementtabelle 700 hinzu, um die Graphen-ID 701 der Gruppen-ID 702 in einer Eins-zu-Eins-Entsprechung zuzuordnen.
Durch die vorstehend beschriebene Verarbeitung wird einem Graphen, der durch den Managementcomputer 101 empfangen wird, eine Gruppen-ID 702 der Graphengruppe mit der identischen Relationsliste 602 zugewiesen, wenn eine solche Gruppe existiert, und wird in der Gruppenmanagementtabelle 600 und der Gruppenzuweisungsmanagementtabelle 700 gemanagt.
5 ist ein Ablaufplan, der ein Beispiel der Zuweisung eines Graphen darstellt, die im Manager 131 zur verteilten Graphendatenverwaltung durchgeführt wird. Die Verarbeitung wird unter Verwendung des Graphendatenempfangsmoduls 201, der Gruppeninformationshalteeinrichtung 204, des Datenklassifizierers 205, des Datenzuweisungsbestimmungsmoduls 206, der Halteeinrichtung 207 für verteilte Knoteninformationen und des Graphendatenliefermoduls 208 des Managers 131 zur verteilten Graphendatenverwaltung durchgeführt. Diese Verarbeitung soll einen Graphen zu einem Suchausführungscomputer 102 liefern, so dass die Graphen, die derselben Gruppe zugewiesen sind, unter den Suchausführungscomputern 102 gleich verteilt sind.
Zuerst empfängt das Graphendatenempfangsmodul 201 einen Graphen und sendet ihn zum Datenklassifizierer 205 (Schritt 501). Es sollte beachtet werden, dass der zum Datenklassifizierer 205 gesendete Graph in dieser Phase derjenige sein kann, der durch die Gruppenerzeugungseinrichtung 203 nach dem Erzeugen einer Graphengruppe gemäß dem vorangehenden Ablaufplan von 4 gesendet wird. Wenn die vorangehende Verarbeitung in 4 eine Graphengruppe erzeugen muss, kann der empfangene Graph vorübergehend im Speicher, in der Speichervorrichtung oder in einer externen Speichervorrichtung zur erneuten Verwendung gespeichert werden.
Der Datenklassifizierer 205 bezieht sich auf die Gruppenzuweisungsmanagementtabelle 700 von der Gruppeninformationshalteeinrichtung 204, erfasst die Gruppen-ID 702 der Gruppe, zu der der empfangene Graph gehört, und sendet den Graphen zum Datenzuweisungsbestimmungsmodul 206 zusammen mit der Gruppen-ID 702 (Schritt 502).
Das Datenzuweisungsbestimmungsmodul 206 erfasst die Zuweisungsmanagementtabelle 800 von der Halteeinrichtung 207 für verteilte Knoteninformationen und bestimmt, ob irgendeine Gruppen-ID 801, die zur empfangenen Gruppen-ID 702 identisch ist, existiert. Wenn eine Gruppen-ID 801, die zur Gruppen-ID 702 identisch ist, existiert, extrahiert das Datenzuweisungsbestimmungsmodul 206 den Suchausführungscomputer, der die wenigsten zugewiesenen Graphen unter den Anzahlen von zugewiesenen Graphen 802-1 bis 802-n im Suchausführungscomputer 102-1, Suchausführungscomputer 102-2... und Suchausführungscomputer 102-n angibt. Das Datenzuweisungsbestimmungsmodul 206 sendet den empfangenen Graphen zum Graphendatenliefermodul zusammen mit den Ortsinformationen über den extrahierten Suchausführungscomputer und addiert 1 zur Anzahl von zugewiesenen Graphen im Suchausführungscomputer 102 des Ziels (Schritt 503).
Wenn mehrere Suchausführungscomputer 102 die wenigsten zugewiesenen Graphen angeben, kann das Datenzuweisungsbestimmungsmodul 206 einen Suchausführungscomputer 102 willkürlich auswählen oder kann den Suchausführungscomputer 102 mit den wenigsten zugewiesenen Graphen, der zuerst oder zuletzt gefunden wird, auswählen. Als Ortsinformationen über den Suchausführungscomputer 102 kann eine IP-Adresse, die Ortsinformationen im Netz angibt, oder eine ID, die einen Suchausführungscomputer eindeutig identifiziert, verwendet werden.
Am Ende sendet das Graphendatenliefermodul 208 den empfangenen Graphen zum Suchausführungscomputer 102 bei den Ortsinformationen, die durch das Datenzuweisungsbestimmungsmodul 206 festgelegt werden (Schritt 504).
Durch die vorstehend beschriebene Verarbeitung extrahiert der Managementcomputer 101 eine Gruppen-ID 801 des empfangenen Graphen, wählt einen Suchausführungscomputer 102 aus, der die wenigsten zugewiesenen Graphen derselben Gruppen-ID 801 in der Zuweisungsmanagementtabelle 800 angibt, und liefert den Graphen 70 zum ausgewählten Suchausführungscomputer 102.
Der Managementcomputer 101 fungiert als vorstehend erwähnter Manager zur verteilten Graphendatenverwaltung, um Graphen zu Suchausführungscomputern 102 zu verteilen und dort zu speichern. Der Managementcomputer 101 fungiert auch als Manger zur verteilten Graphendatensuche, der durch den Manager 132 zur verteilten Graphendatensuche implementiert wird, der auf dem Speicher des Managementcomputers 101 läuft, beim Durchsuchen der Graphen, die in den Suchausführungscomputern 102 gespeichert sind, nach einem gewünschten Graphen.
3 ist ein Blockdiagramm, das Beispiele von Funktionsmodulen im Manager 132 zur verteilten Graphendatensuche darstellt.
Der Managementcomputer 101, der als Manger zur verteilten Graphendatensuche fungiert, überträgt Suchbedingungen, die vom Client 80 gesendet werden, der eine Suche anfordert, und an einem Suchabfrageempfangs- und Suchabfrageliefermodul 301 durch die Kommunikationsvorrichtung 113 empfangen werden, zu jedem Suchausführungscomputer 102 durch die Kommunikationsvorrichtung 113. Gleichzeitig zeichnet der Managementcomputer 101 die Suchausführungscomputer 102 der Ziele auf, um die Suchbedingungen in einer Suchknoteninformationshalteeinrichtung 302 zu liefern. Der Client 80 gibt eine Suchabfrage (nachstehend Suchbedingungen) als Anforderung für die Suche aus.
Jeder der Suchausführungscomputer 102, die die Suchbedingungen empfangen haben, interpretiert die Suchbedingungen am Abfrageausführungsmodul 60, extrahiert mögliche Lösungen unter Verwendung von Indexdaten, die in seiner Speichervorrichtung 54 gehalten werden, als Art von Daten und hält die extrahierten möglichen Lösungen in einer Halteeinrichtung 61 für mögliche Lösungen. Danach extrahiert das Abfrageausführungsmodul 60 des Suchausführungscomputers 102 einen Graphen 70, der den Suchbedingungen entspricht, von den möglichen Lösungen und sendet den extrahierten Graphen zum Managementcomputer 101. Wenn kein Graph, der den Suchbedingungen entspricht, existiert, sendet der Suchausführungscomputer 102 Informationen, die angeben, dass keine entsprechenden Daten existieren, zum Managementcomputer 101.
Die Suchbedingungen umfassen Datenbedingungen und Relationsbedingungen, wie in 23 dargestellt. 23 ist ein Diagramm, das ein Beispiel einer Suchabfrage darstellt, um diese Erfindung anzuwenden. Das Beispiel in 23 gibt Suchbedingungen an, einschließlich Datenbedingungen einer Relationsbedingung ”GEHÖRT_ZU” und einer Datenbedingung ”JAPAN” und einer Relationsbedingung ”BREITENGRAD, LÄNGENGRAD” und einer Datenbedingung ”30 Grad oder mehr nördlicher Breite”. In diesem Beispiel können Lösungen für die Datenbedingungen ”GEHÖRT_ZU” und ”JAPAN” durch Indexsuche erhalten werden; Lösungen für die Datenbedingung ”30 Grad oder mehr nördlicher Breite” werden jedoch von den möglichen Lösungen, die durch die Indexsuche erhalten werden, durch Bedingungsvergleich extrahiert.
Ein Suchergebnisempfangsmodul 303 des Managementcomputers 101 empfängt Suchergebnisse, die von den Suchausführungscomputern 102 zurückgesendet werden, und überträgt sie zu einer Suchergebniszusammenfügungseinrichtung 304. Die Suchergebniszusammenfügungseinrichtung 304 wartet auf die Suchergebnisse, die von allen Suchausführungscomputern 102 zurückgesendet werden, zu denen die Suchbedingungen gesendet wurden und in der Suchknoteninformationshalteeinrichtung 302 aufgezeichnet wurden. Die Suchergebniszusammenfügungseinrichtung 304 verbindet die von allen Suchausführungscomputern 102 zurückgesendeten Graphen zu einem Satz von Daten und sendet ihn zum Client 80, der die Suchbedingungen ausgegeben hat, unter Verwendung des Suchergebnisrückgabemoduls 305.
Die vorstehend beschriebene verteilte Verwaltung und verteilte Suche von Graphen schaffen ein Verfahren für die verteilte Verwaltung von Graphen, die Sätze von Daten sind, in denen ein Datenteil einen Datenwert und Relationen mit anderen Datenteilen hält und durch die Relationen verbunden ist. Das Verfahren erzeugt Graphengruppen mit denselben Datenrelationen und weist die Graphen derselben Gruppe mehreren Suchausführungscomputeren 102 gleich zu. Eine solche verteilte Verwaltung von Graphen unter mehreren Suchausführungscomputeren 102 ermöglicht beim Suchen der Graphen mit identischen Datenrelationen, dass die Suchausführungscomputer 102 gleiche Anzahlen von zu suchenden Graphen aufweisen, was einen Lastausgleich zwischen den Suchausführungscomputern 102 erreicht.
Die vorangehende Ausführungsform 1 hat ein Beispiel bereitgestellt, in dem das Computersystem zum Schaffen der verteilten Verwaltung und verteilten Suche von Graphen aus einem Managementcomputer 101 und mehreren Suchausführungscomputern 102 besteht; die Konfiguration ist jedoch nicht darauf begrenzt. Ein physikalischer Computer mit mehreren Prozessoren kann beispielsweise mehrere virtuelle Maschinen mit einem Hypervisor oder einem VMM (virtuellen Maschinenmonitor) konfigurieren, so dass eine der virtuellen Maschinen als Managementcomputer 101 arbeitet und die anderen virtuellen Maschinen als Suchausführungscomputer 102 arbeiten.
Ausführungsform 2
Beim Suchen von Graphen 70, die unter Suchausführungscomputern 102 verteilt sind, extrahiert das Abfrageausführungsmodul 60 in jedem Suchausführungscomputer 102 mögliche Lösungen unter Verwendung von Verzeichnisdaten, die in einem Index enthalten sind, der in der Speichervorrichtung 54 gehalten wird. Das Abfrageausführungsmodul 60 bestimmt dann, ob jeder Datenwert und jede Datenrelation, die in allen Graphen der möglichen Lösungen enthalten sind, Suchbedingungen entspricht. Die Ausführungsform 2 verwendet ein Computersystem mit derselben Konfiguration wie jener der Ausführungsform 1, um eine verteilte Verwaltung und verteilte Suche von Graphen durchzuführen. Es wird auch angenommen, dass der Index und später beschriebene Verzeichnisdaten in der Speichervorrichtung 54 beispielsweise in Daten 72 enthalten sind.
Jeder Datensatz der Verzeichnisdaten, die beim Suchen am Suchausführungscomputer 102 verwendet werden, umfasst einen Datenwert oder eine Datenrelation, die in den Graphen 70 enthalten sind, in Form einer Zeichenfolge, einer Zahlenreihe oder einer Symbolfolge. Das Sortieren dieser Datensätze nach dem Wert wie ein Verzeichnis hilft dem Abfrageausführungsmodul 60, den Bereich des Datenwerts in den Graphen zu verschmälern, die Suchbedingungen entsprechen, um mögliche Lösungen zu extrahieren.
Die in einem Datensatz von Daten enthaltenen Informationen können als einer der folgenden zwei Typen klassifiziert werden. Einer sind Klasseninformationen, die den Typ oder die Kategorie eines Datenteils angeben, der als URI (einheitlicher Quellenidentifizierer) oder Wort ausgedrückt werden kann. Der andere sind Informationen, die die Bedeutung eines Datenteils selbst angeben (nachstehend Instanzinformationen), die als Satz, eines von einer Symbolfolge, einer Zahlenreihe und eines Zahlenwerts gemäß einem gewissen Schema oder einer Kombination von diesen ausgedrückt werden kann.
Die ersteren Klasseninformationen werden häufig verwendet, um die abzurufenden Daten mit einem Typ oder einer Kategorie zu verschmälern. Die letzteren Instanzinformationen werden bei einem (möglichen) Bedingungsvergleich verwendet, der nach der Extraktion von möglichen Lösungen durchgeführt wird, um festzustellen, ob die extrahierten Daten gewünschte Informationen umfassen oder ob die extrahierten Daten in einem festgelegten Bereich enthalten sind. Insbesondere soll der Bedingungsvergleich in dieser Beschreibung feststellen, ob eine teilweise Zeichenfolge, die in einem Datenwert enthalten ist, oder eine Zahlenreihe, die in einem Datenwert enthalten ist, größer oder kleiner als ein festgelegter Wert ist (Datenbedingung) oder ob das Datum und die Zeit, die in einem Datenwert enthalten sind, vor oder nach einem festgelegten Datum und einer festgelegten Zeit liegen (Datenbedingung).
Die Datenrelationen, die in einem Graphen enthalten sind, sind eine Art von Typ oder Kategorie eines Datenteils; folglich gehören sie zu den ersteren Klasseninformationen. Hinsichtlich der Datenwerte, wenn der Datenwert Informationen eines Typs oder einer Kategorie aufweist, gehört er zu den ersteren Klasseninformationen; in den anderen Fällen gehört er zu den letzteren Instanzinformationen.
Wenn der Graph, der in 22 dargestellt ist, als Beispiel herangezogen wird, ist ein Datenwert eines Stadtnamens ”YOKOHAMA” und ein Datenwert eines Landesnamens ”JAPAN” durch eine Kategorie ”GEHÖRT_ZU” verbunden, um eine Relation zu konstruieren. Beim Durchführen einer Suche kann die Relation ”GEHÖRT_ZU” mit einem Index zu suchende Datenwerte klassifizieren. Das heißt, Datenwerte, mit denen eine Kategorie ”GEHÖRT_ZU” verbindet, sind Klasseninformationen.
Im Gegensatz dazu ist der Datenwert einer Zahlenreihe ”35,47, 139,63” Instanzinformationen, die die Koordinaten eines Stadtnamens ”YOKOHAMA” angeben. Der Datenwert der Zahlenreihe ”35,47, 139,63” wird wahrscheinlicher mit einer Datenbedingung eines Bereichs in Breitengrad oder Längengrad abgerufen. Die Ausführungsform 2 erzeugt eine Graphengruppe mit einer Relation ”BREITENGRAD, LÄNGENGRAD”, die einen Stadtnamen ”YOKOHAMA” mit einer Zahlenreihe ”35,47, 139,63” verbindet, und verteilt die Graphen der Gruppe gleich zu mehreren Suchausführungscomputern 102, um einen Lastausgleich beim Suchen des Bedingungsvergleichs zu erreichen. Die Ausführungsform 2 erzeugt jedoch keine Gruppe mit einer Relation ”GEHÖRT_ZU”, da ein Landesname, der mit einem Stadtnamen durch die Relation ”GEHÖRT_ZU” verbunden ist, Klasseninformationen sind. Dies liegt daran, dass, da ein Datenwert, der durch eine Relation ”GEHÖRT_ZU” verbunden ist, Klasseninformationen sind, die Indexsuche eine Lösung extrahieren kann, so dass die Suchausführungscomputer 102 hinsichtlich der Last weniger beeinflusst sind.
Beim Suchen von Graphen extrahiert das Abfrageausführungsmodul 60 eines Suchausführungscomputers 102 Datenwerte, die einer Datenbedingung von vorstehend erwähnten Klasseninformationen entsprechen, unter Verwendung eines Index, der im Voraus erzeugt wird. Anschließend bestimmt das Abfrageausführungsmodul 60, ob jeder der Datenwerte eine Datenbedingung (und eine Relationsbedingung) für Instanzinformationen erfüllt, um einen Datenwert zu finden, der die Relationsbedingung erfüllt.
Wie in 23 dargestellt, führt das Abfrageausführungsmodul 60 beispielsweise eine Suche unter Verwendung eines Index mit einem Datenwert durch, der eine Kategorie ”JAPAN” als Datenbedingung der Suchbedingungen (eine Datenbedingung und eine Relationsbedingung) angibt, um mögliche Lösungen von Stadtnamen zu extrahieren. Anschließend extrahiert das Abfrageausführungsmodul 60 Zahlenreihen, die eine Relationsbedingung ”nördliche Breite”, und eine Datenbedingung ”30 Grad oder mehr” erfüllen, durch Bedingungsvergleich, um Suchergebnisse zu erhalten.
Das Computersystem, um die verteilte Suche durchzuführen, verteilt die Anzahl von Malen der Durchführung des Bedingungsvergleichs gleich auf die mehreren Suchausführungscomputer 102, um einen wesentlichen Lastausgleich zwischen den Suchausführungscomputern 102 beim Suchen zu erreichen.
Um die Anzahl von Malen der Durchführung des Bedingungsvergleichs auf mehrere Suchausführungscomputer 102 gleich zu verteilen, klassifiziert die Ausführungsform 2 Graphen mit gemeinsamen Datenrelationen, die mit Werten von Instanzinformationen verbinden, an denen der vorstehend erwähnte Bedingungsvergleich durchgeführt werden soll, in dieselbe Gruppe beim Klassifizieren von als mögliche Lösungen zu extrahierenden Graphen in Suchen in dieselbe Gruppe. Die Ausführungsform 2 schafft ferner ein Verfahren zur verteilten Verwaltung von Graphen, das Graphen, die in derselben Gruppe enthalten sind, gleich auf die Suchausführungscomputer 102 verteilt und diesen zuweist. Das heißt, wenn der Graph in 22 als Beispiel herangezogen wird, erzeugt die Ausführungsform 2 eine Gruppe von Graphen mit der Relation ”BREITENGRAD, LÄNGENGRAD”, die den Datenwert einer Zahlenreihe ”35,47, 139,63” mit einem Stadtnamen verbindet.
Die Ausführungsform 2 führt die vorstehend beschriebene Verarbeitung unter Verwendung des Graphendatenempfangsmoduls 201, der Relationsextraktionseinrichtung 202, der Gruppenerzeugungseinrichtung 203, der Gruppeninformationshalteeinrichtung 204 und des Datenklassifizierers 205, die im Manager 131 zur verteilten Graphendatenverwaltung enthalten sind, der in 2 der vorangehenden Ausführungsform 1 dargestellt ist, durch.
9 ist ein Ablaufplan, der ein Beispiel der Verarbeitung für den Managementcomputer 101 darstellt, um einen Graphen in eine Gruppe mit identischen Relationen zu klassifizieren, die mit Datenwerten verbinden, an denen ein Bedingungsvergleich wahrscheinlicher durchgeführt wird, nachdem einige Graphen als mögliche Lösungen extrahiert sind.
Zuerst empfängt das Graphendatenempfangsmodul 201 einen Graphen durch die Kommunikationsvorrichtung 113 des Managementcomputers 101 (Schritt 901) und sendet ihn zur Relationsextraktionseinrichtung 202. Die Relationsextraktionseinrichtung extrahiert Datenrelationen, die im empfangenen Graphen enthalten sind, und sendet sie zur Gruppenerzeugungseinrichtung (Schritt 902).
Die Gruppenerzeugungseinrichtung 203 bestimmt an jeder der empfangenen Relationen, ob der Datenwert, mit dem die empfangene Relation verbindet, Klasseninformationen sind, die den Typ oder die Kategorie eines Datenteils angeben, wie z. B. Informationen, die durch einen URI angegeben werden (Schritt 903). Wenn Klasseninformationen enthalten sind, geht die Gruppenerzeugungseinrichtung 203 zu Schritt 904 weiter; wenn keine Klasseninformationen enthalten sind, geht sie zu Schritt 905 weiter.
In Schritt 904 entfernt die Gruppenerzeugungseinrichtung 203 die Relationen, die mit Datenwerten von Klasseninformationen verbinden, die in Schritt 902 extrahiert werden, aus den extrahierten Relationen. Das heißt, sie extrahiert erneut Relationen, die mit Datenwerten von Instanzinformationen verbinden.
In Schritt 905 erfasst die Gruppenerzeugungseinrichtung 203 die Gruppenmanagementtabelle 600 von der Gruppeninformationshalteeinrichtung 204 und bestimmt, ob irgendeine Graphengruppen-ID existiert, bei der alle Relationen, die in einer Relationsliste 602 enthalten sind, vollständig den extrahierten Relationen entsprechen.
Wenn eine Graphengruppen-ID mit einer vollständigen Übereinstimmung existiert, geht die Gruppenerzeugungseinrichtung 203 zu Schritt 907 weiter. Sie erzeugt eine Graphen-ID 701 zum eindeutigen Identifizieren des empfangenen Graphen und fügt einen neuen Eintrag zur Gruppenzuweisungsmanagementtabelle 700 hinzu, um die Graphen-ID 701 der Gruppen-ID 702 in einer Eins-zu-Eins-Entsprechung zuzuordnen.
Wenn keine Graphengruppen-ID mit einer vollständigen Übereinstimmung existiert, geht die Gruppenerzeugungseinrichtung 203 zu Schritt 906 weiter. Sie erzeugt eine Gruppe mit allen extrahierten Relationen in einer Relationsliste 602 und eine Gruppen-ID 601 zum eindeutigen Identifizieren dieser Gruppe und fügt einen neuen Eintrag zur Gruppenmanagementtabelle 600 hinzu.
Nach dem Hinzufügen eines neuen Eintrags zur Gruppenmanagementtabelle 600 in Schritt 906 geht die Gruppenerzeugungseinrichtung 203 zum vorstehend beschriebenen Schritt 907 weiter. Die Gruppenerzeugungseinrichtung 203 erzeugt eine Graphen-ID 701 zum eindeutigen Identifizieren des empfangenen Graphen und fügt einen neuen Eintrag zur Gruppenzuweisungsmanagementtabelle 700 hinzu, um die Graphen-ID 701 der Gruppen-ID 702 in einer Eins-Zu-Eins-Entsprechung zuzuordnen.
Durch die vorstehend beschriebene Verarbeitung kann der Managementcomputer 101 ein Verfahren zur verteilten Graphendatenverwaltung bereitstellen, das eine Gruppe von Graphen erzeugt, an denen ein Bedingungsvergleich mit Datenbedingungen von Suchbedingungen für einen Datenwert durchgeführt werden soll, nach der Extraktion von möglichen Lösungen mit denselben Suchbedingungen, und Graphen, die in derselben Gruppe enthalten sind, den Suchausführungscomputern 102 gleich zuweist.
Eine solche verteilte Verwaltung von Graphen zwischen mehreren Suchausführungscomputern 102 erreicht eine gleiche Anzahl von Malen der Durchführung eines Bedingungsvergleichs unter den Suchausführungscomputern 102.
Ausführungsform 3
Die Ausführungsform 2 erzeugt eine Gruppe von Graphen, an denen ein Bedingungsvergleich durchgeführt werden soll, und verteilt die in derselben Gruppe enthaltenen Graphen gleich zu mehreren Suchausführungscomputern 102.
Beim Durchführen einer tatsächlichen Suche sind, selbst wenn Datenwerte keine Klasseninformationen sind, die die Typen oder Kategorien von Datenteilen angeben, sondern sie Instanzinformationen sind, die die Bedeutungen der Datenteile angeben, einige Datenwerte wahrscheinlicher Objekte eines Bedingungsvergleichs und einige Datenwerte sind weniger wahrscheinlich Objekte eines Bedingungsvergleichs. Angesichts dieses Umstandes speichert die Ausführungsform 3 Suchbedingungen (Suchabfrage) der Suchen, die von den Suchausführungscomputern 102 durchgeführt werden, und erzeugt in Anbetracht der vergangenen Suchbedingungen eine Gruppe von Graphen mit gemeinsamen Relationen, die mit Datenwerten verbinden, an denen ein Bedingungsvergleich häufiger durchgeführt wird. Dann verteilt die Ausführungsform 3 die Graphen derselben Gruppe gleich zu mehreren Suchausführungscomputern 102, um mögliche Lösungen, die durch verteiltes Suchen extrahiert werden sollen, zu den mehreren Suchausführungscomputern 102 zu verteilen, was die Möglichkeit zum Erreichen eines Lastausgleichs beim Suchen erhöht.
Um einen Lastausgleich beim Suchen zu erreichen, klassifiziert die Ausführungsform 3 Graphen mit gemeinsamen Datenrelationen, die mit Datenwerten verbinden, die häufig Objekt eines Bedingungsvergleichs in den vergangenen Suchen waren, in dieselbe Gruppe beim Klassifizieren von Graphen, die in Suchen als mögliche Lösungen extrahiert werden sollen, in dieselbe Gruppe. Dann verteilt und weist die Ausführungsform 3 Graphen derselben Gruppe gleich den Suchausführungscomputern 102 zu, um einen Lastausgleich beim Suchen zu erreichen.
Die Systemkonfiguration der Ausführungsform 3 wird durch Hinzufügen einer Relationsabrufzählwert-Managementtabelle 721 zu den Daten 72 in jedem Suchausführungscomputer 102, der in 1 der Ausführungsform 1 dargestellt ist, geschaffen; der Rest der Konfiguration ist dieselbe wie jene der Ausführungsform 1. Die gemeinsamen Elemente sind mit denselben Bezugszeichen bezeichnet und auf deren Erläuterung wird verzichtet.
13 ist ein Blockdiagramm, das ein Beispiel von Daten 72 darstellt, die in der Speichervorrichtung 51 von jedem Suchausführungscomputer 102 gespeichert sind. Die Daten 72 umfassen einen Index 722 und eine Relationsabrufzählwert-Managementtabelle 721 zum Aufzeichnen der Anzahl von Suchen nach der Art der Relation.
11 ist eine Ansicht, die ein Beispiel der Relationsabrufzählwert-Managementtabelle 721 darstellt. In der Relationsabrufzählwert-Managementtabelle 721 umfasst jeder Eintrag eine abgerufene Relation 7211 zum Speichern einer abgerufenen Relation und einen Relationsabrufzählwert 7212 zum Speichern des Zählwerts des Abrufs der Relation.
10 ist ein Ablaufplan, der ein Beispiel der Verarbeitung des Abrufausführungsmoduls 60 in jedem Suchausführungscomputer 102, der in 1 der Ausführungsform 1 gezeigt ist, darstellt, um eine Relation, die mit einem Datenwert verbindet, als Objekt des Bedingungsvergleichs zu speichern.
Beim Empfang einer Suchabfrage vom Managementcomputer 101 extrahiert das Abfrageausführungsmodul 60 zuerst Graphen 70 als mögliche Lösungen mit einem Index (Schritt 1801). Es wird angenommen, dass der Index derselbe wie derjenige in der Ausführungsform 2 ist und in den Daten 72 in der Speichervorrichtung 54 enthalten ist.
Dann bestimmt das Abfrageausführungsmodul 60, ob der Bedingungsvergleich an den extrahierten möglichen Lösungen durchgeführt werden muss (Schritt 1802). Wenn der Bedingungsvergleich erforderlich ist, erfasst das Abfrageausführungsmodul 60 eine Relation, die mit dem Datenwert verbindet, als Objekt des Bedingungsvergleichs vom Managementcomputer 101 (Schritt 1803).
Anschließend bestimmt das Abfrageausführungsmodul 60, ob die in Schritt 1803 erfasste Relation in den abgerufenen Relationen 7211 in der in 11 gezeigten Relationsabrufzählwert-Managementtabelle 721 enthalten ist, die in den Daten 72 der Speichervorrichtung 54 gehalten wird (Schritt 1804). Wenn die erfasste Relation in den abgerufenen Relationen 7211 enthalten ist, geht das Abfrageausführungsmodul 60 zu Schritt 1806 weiter. Wenn die erfasste Relation nicht in den abgerufenen Relationen 7211 enthalten ist, nimmt das Abfrageausführungsmodul 60 die erfasste Relation in einen neuen Eintrag der abgerufenen Relation 7211 der Relationssuchzählwert-Managementtabelle 720 auf, setzt einen anfänglichen Wert 0 auf den Abrufsuchzählwert 7012 und geht zu Schritt 1806 weiter (Schritt 1805).
In Schritt 1806 inkrementiert das Abfrageausführungsmodul 60 den Relationssuchzählwert 7212 für die erfasste Relation um eins. Danach geht sie zum Bedingungsvergleich weiter.
Obwohl diese Beschreibung ein Beispiel bereitgestellt hat, dass die Relationsabrufzählwert-Managementtabelle 721 in 11 als Daten in der Speichervorrichtung 54 von jedem Suchausführungscomputer 102 gehalten wird, kann diese Tabelle zum Managementcomputer 101 mit einem vorbestimmten Zeitablauf geschickt werden, damit sie in der Speichervorrichtung 114 des Managementcomputers 101 gehalten wird.
12 ist ein Ablaufplan, der ein Beispiel der Verarbeitung des Managers zur verteilten Graphendatenverwaltung darstellt, um Relationen, die zum Erzeugen einer Gruppe verwendet werden sollen, aus statistischen Informationen zu extrahieren. Die Verarbeitung des Ablaufplans von 12 wird im Managementcomputer 101 unter Verwendung der Relationsabrufzählwert-Managementtabelle 721, die gemäß dem Ablaufplan in 10 durch das Abfrageausführungsmodul 60 erzeugt wird, und des Graphendatenempfangsmoduls 201, der Relationsextraktionseinrichtung 202, der Gruppenerzeugungseinrichtung 203, der Gruppeninformationshalteeinrichtung 204 und des Datenklassifizierers 205, die im Manager 131 zur verteilten Graphendatenverwaltung, der in 2 gezeigt ist, und im Manager 132 zur verteilten Graphendatensuche, der in 1 gezeigt ist, enthalten sind, durchgeführt.
Zuerst empfängt im Managementcomputer 101 das Graphendatenempfangsmodul 201 einen Graphen durch die Kommunikationsvorrichtung 113 und sendet ihm zur Relationsextraktionseinrichtung 202 (Schritt 1001). Die Relationsextraktionseinrichtung 202 extrahiert Datenrelationen, die im empfangenen Graphen enthalten sind, und sendet sie zur Gruppenerzeugungseinrichtung 203 (Schritt 1002). Die Gruppenerzeugungseinrichtung 203 erfasst die Relationsabrufzählwert-Managementtabelle 721, die in 11 dargestellt ist, aus der Speichervorrichtung 54 von jedem Suchausführungscomputer 102 (oder der Speichervorrichtung 114 des Managementcomputers 101).
Dann extrahiert die Gruppenerzeugungseinrichtung 203 erneut Relationen, die in der erfassten Relationsabrufzählwert-Managementtabelle 721 enthalten sind und Anzahlen, die größer sind als ein vorbestimmter Schwellenwert, in den Relationsabrufzählwerten in der Tabelle angeben, von den vom Graphen extrahierten Relationen und geht zu Schritt 1004 weiter. Der vorbestimmte Schwellenwert kann ein fester Wert wie z. B. 1, ein durch die Eingabevorrichtung 115 des Managementcomputers 101 eingegebener Wert oder eine Anzahl sein, die in einer spezifischen Zeile angegeben ist, wenn die Relationsabrufzählwerte in der Relationsabrufzählwert-Managementtabelle 721 in der Reihenfolge des Relationsabrufzählwerts sortiert werden.
In Schritt 1004 erfasst die Gruppenerzeugungseinrichtung 203 die Gruppenmanagementtabelle 600 aus der Gruppeninformationshalteeinrichtung 204 und bestimmt, ob die Gruppenmanagementtabelle 600 irgendeine Graphengruppen-ID umfasst, bei der die Relationen, die in einer Relationsliste 602 enthalten sind, vollständig den extrahierten Relationen entsprechen.
Wenn die Gruppenmanagementtabelle 600 eine Graphengruppen-ID umfasst, bei der die Relationen, die in einer Relationsliste 602 enthalten sind, den extrahierten Relationen vollständig entsprechen, geht die Gruppenerzeugungseinrichtung 203 zu Schritt 1006 weiter.
Wenn keine Relationsliste 602, die den extrahierten Relationen vollständig entspricht, gefunden wird, geht die Gruppenerzeugungseinrichtung 203 zu Schritt 1005 weiter, erzeugt eine Gruppe mit allen extrahierten Relationen in einer Relationsliste 602 und eine Gruppen-ID 601 zum eindeutigen Identifizieren der Gruppe und fügt sie zur Gruppenmanagementtabelle 600 als neuen Eintrag hinzu (Schritt 1005).
Als nächstes erzeugt die Gruppenerzeugungseinrichtung 203 eine Graphen-ID 701 zum eindeutigen Identifizieren des empfangenen Graphen und fügt sie zur Gruppenzuweisungsmanagementtabelle 700 als neuen Eintrag hinzu, so dass sie der Gruppen-ID 702 eins zu eins entspricht (Schritt 1006).
Durch die vorstehend beschriebene Verarbeitung kann ein Verfahren zur verteilten Graphendatenverwaltung bereitgestellt werden, das eine Gruppe von Graphen erzeugt, die gemeinsame Relationen umfassen, die mit Datenwerten verbinden, die als mögliche Lösungen für eine Schwellenanzahl von Malen oder mehr in den vergangenen Suchen extrahiert wurden, und die Graphen der Gruppe gleich zu mehreren Suchausführungscomputern 102 verteilt und diesen zuweist.
Eine solche verteilte Verwaltung von Graphen kann ein Verfahren zur verteilten Graphendatensuche schaffen, das, wenn die vorangehenden Relationen als Suchbedingungen mit derselben Häufigkeit wie die vergangenen Suchen festgelegt werden, Datenwerte, die durch Relationen verbunden sind, als mögliche Lösungen unter den Suchausführungscomputeren 102 gleich extrahiert.
Ausführungsform 4
Wenn eine Datenrelation, die mit niedriger Häufigkeit erscheint, als Suchbedingung festgelegt wird, ist die Anzahl von möglichen Lösungen klein. Wenn dagegen eine Relation, die mit höherer Häufigkeit erscheint, als Suchbedingung festgelegt wird, ist die Anzahl von möglichen Lösungen größer. Folglich führt das gleiche Verteilen von Graphen mit Relationen, die mit hoher Häufigkeit erscheinen, zu mehreren Suchausführungscomputern 102 zur Verteilung eines großen Teils der Last beim Suchen, was mehr Verringerung der Suchzeit erreicht. Mit dem Ziel einer Suche mit höherer Geschwindigkeit schafft die Ausführungsform 4 ein Verfahren zur verteilten Graphendatenverwaltung, das Graphen mit gemeinsamen Relationen, die mit hoher Häufigkeit erscheinen, als gleiche Gruppe beim Klassifizieren von Graphen, die in Suchen als mögliche Lösungen extrahiert werden, in dieselbe Gruppe klassifiziert und Graphen, die in derselben Gruppe enthalten sind, zu den Suchausführungscomputern 102 gleich verteilt und zuweist.
Die Systemkonfiguration der Ausführungsform 4 wird durch Hinzufügen einer Relationserscheinungszählwert-Managementtabelle 900, die in 15 dargestellt ist, zum Manager 131 zur verteilten Graphendatenverwaltung im Managementcomputer 101, der in 2 der Ausführungsform 1 dargestellt ist, bereitgestellt; der Rest der Konfiguration ist dieselbe wie jene der Ausführungsform 1. Die gemeinsamen Elemente sind mit denselben Bezugszeichen bezeichnet und auf deren Erläuterung wird verzichtet.
17 ist ein Blockdiagramm, das eine Konfiguration des Managers 131 zur verteilten Graphendatenverwaltung im Managementcomputer 101 in der Ausführungsform 4 darstellt. Der Manager 131 zur verteilten Graphendatenverwaltung in der Ausführungsform 4 umfasst zusätzlich eine Relationserscheinungszählwert-Managementtabelle 900, die von der Relationsextraktionseinrichtung 202 gemanagt wird. Der Rest der Konfiguration ist dieselbe wie die Konfiguration in der Ausführungsform 1.
15 ist eine Ansicht, die ein Beispiel der Relationserscheinungszählwert-Managementtabelle 900 in der Ausführungsform 4 dieser Erfindung darstellt. In der Relationserscheinungs-Managementtabelle 900 umfasst ein Eintrag eine Relation 901 zum Speichern einer abgerufenen Relation und einen Erscheinungszählwert 902 zum Speichern der Anzahl von Malen, die die Relation erschienen ist.
14 ist ein Ablaufplan, der ein Beispiel des Managers 131 zur verteilten Graphendatenverwaltung darstellt, um das Erscheinen von Relationen zu zählen. Diese Verarbeitung extrahiert Relationen, die mit hoher Häufigkeit erscheinen, unter Verwendung des Graphendatenempfangsmoduls 201 und der Relationsextraktionseinrichtung 202, die im Manager 131 zur verteilten Graphendatenverwaltung enthalten sind.
Zuerst empfängt im Managementcomputer 101 das Graphendatenempfangsmodul 201 einen Graphen durch die Kommunikationsvorrichtung 113 und sendet ihn zur Relationsextraktionseinrichtung 202 (Schritt 1101). Die Relationsextraktionseinrichtung 202 extrahiert Datenrelationen, die im empfangenen Graphen enthalten sind, und erfasst dann die in 15 gezeigte Relationserscheinungszählwert-Managementtabelle 900 aus der Speichervorrichtung 114 (Schritt 1102). Anschließend bestimmt die Relationsextraktionseinrichtung 202, ob alle extrahierten Relationen in der Relationserscheinungszählwert-Managementtabelle 900 enthalten sind (Schritt 1103).
Wenn alle extrahierten Relationen in der Relationserscheinungszählwert-Managementtabelle 900 enthalten sind, geht die Relationsextraktionseinrichtung 202 zu Schritt 1005 weiter; wenn eine oder mehrere extrahierte Relationen nicht in der Relationserscheinungszählwert-Managementtabelle 900 enthalten sind, geht sie zu Schritt 1104 weiter.
In Schritt 1104 fügt die Relationsextraktionseinrichtung 202 die Relationen, die nicht in der Relationserscheinungszählwert-Managementtabelle 900 enthalten sind, zur Relationserscheinungszählwert-Managementtabelle 900 hinzu, setzt den anfänglichen Wert 0 auf die Erscheinungszählwerte und geht zu Schritt 1105 weiter. In Schritt 1105 inkrementiert die Relationsextraktionseinrichtung 202 alle Erscheinungszählwerte für die extrahierten Relationen um eins in der Relationserscheinungszählwert-Managementtabelle 900.
Unter Verwendung der in 15 gezeigten Relationserscheinungszählwert-Managementtabelle 900, die durch die vorstehend beschriebene Verarbeitung erzeugt wird, und des Graphendatenempfangsmoduls 201, der Relationsextraktionseinrichtung 202, der Gruppenerzeugungseinrichtung 203, der Gruppeninformationshalteeinrichtung 204 und des Datenklassifizierers 205, die im Manager 131 zur verteilten Graphendatenverwaltung enthalten sind, der in 17 gezeigt ist, klassifiziert der Managementcomputer 101 Graphen in Gruppen ohne Relationen, die mit niedriger Häufigkeit erscheinen.
16 ist ein Ablaufplan, der ein Beispiel der Verarbeitung des Managers 131 zur verteilten Graphendatenverwaltung darstellt, um einen Graphen in eine Gruppe ohne Relationen, die mit niedriger Häufigkeit erscheinen, zu klassifizieren.
Zuerst empfängt das Graphendatenempfangsmodul 201 einen Graphen durch die Kommunikationsvorrichtung 113 des Managementcomputers 101 und sendet ihn zur Relationsextraktionseinrichtung 202 (Schritt 1301). Die Relationsextraktionseinrichtung 202 extrahiert Datenrelationen, die im empfangenen Graphen enthalten sind, und sendet sie zur Gruppenerzeugungseinrichtung (Schritt 1302).
Die Gruppenerzeugungseinrichtung 203 ruft die Relationserscheinungszählwert-Managementtabelle 900, die in 14 gezeigt ist, aus der Speichervorrichtung 114 ab, extrahiert erneut Relationen, für die die Erscheinungszählwerte in der erfassten Relationserscheinungszählwert-Managementtabelle 900 Zahlen angeben, die gleich oder größer als ein vorbestimmter Schwellenwert sind, aus den Relationen, die von der Relationsextraktionseinrichtung 202 empfangen werden, und geht zu Schritt 1304 weiter (Schritt 1303). Der Schwellenwert kann ein Wert sein, der durch die Eingabevorrichtung 115 des Managementcomputers 101 eingegeben wird, oder eine Anzahl, die in einer spezifischen Zeile angegeben wird, wenn die Erscheinungszählwerte in der Relationserscheinungszählwert-Managementtabelle 900 in der Reihenfolge des Erscheinungszählwerts sortiert werden.
In Schritt 1304 erfasst die Gruppenerzeugungseinrichtung 203 die Gruppenmanagementtabelle 600 von der Gruppeninformationshalteeinrichtung 204 und bestimmt, ob irgendeine Graphengruppen-ID existiert, bei der die Elemente von Relationen, die in der Relationsliste 602 enthalten sind, vollständig allen Elementen von Relationen entsprechen, die durch die Relationsextraktionseinrichtung 202 erneut extrahiert werden.
Wenn eine solche Graphengruppen-ID existiert, geht die Gruppenerzeugungseinrichtung 203 zu Schritt 1304 weiter; wenn keine solche Graphengruppen-ID existiert, geht die Gruppenerzeugungseinrichtung 203 zu Schritt 1305 weiter.
Wenn keine Graphengruppen-ID existiert, geht die Gruppenerzeugungseinrichtung 203 zu Schritt 1305 weiter, erzeugt eine Gruppe mit allen Relationen, die von der Relationsextraktionseinrichtung 202 erneut extrahiert werden, in einer Relationsliste 602 und eine Gruppen-ID 601 zum eindeutigen Identifizieren der Gruppe und fügt einen neuen Eintrag zur Gruppenmanagementtabelle 600 hinzu.
Anschließend erzeugt die Gruppenerzeugungseinrichtung 203 eine Graphen-ID 701 zum eindeutigen Identifizieren des empfangenen Graphen und fügt einen neuen Eintrag zur Gruppenzuweisungsmanagementtabelle 700 hinzu, um die Graphen-ID 701 der Gruppen-ID 601 (702) in einer Eins-zu-Eins-Entsprechung zuzuordnen (Schritt 1306).
Durch die vorstehend beschriebene Verarbeitung kann der Managementcomputer 101 eine Graphengruppe mit Relationen erzeugen, die mit hoher Häufigkeit erscheinen, und weist Graphen gleich zu mehreren Suchausführungscomputern 102 zu. Eine solche verteilte Verwaltung von Graphen kann die Suche beschleunigen, da mögliche Lösungen gleich unter den Suchausführungscomputern 102 verteilt werden, wenn mehrere mögliche Lösungen mit einer Suchbedingung mit einer Relation, die mit hoher Häufigkeit erscheint, extrahiert werden.
Ausführungsform 5
Wenn jede Gruppe mit Datenrelationen erzeugt wird, die in einem Graphen enthalten sind, kann irgendeine Relation teilweise mehreren Gruppen gemeinsam sein. Selbst in dem Fall, in dem mögliche Lösungen mit dieser teilweise gemeinsamen Relation erfasst werden, sollten die Graphen, die zu den Gruppen gehören, so zugewiesen werden, dass mögliche Lösungen unter den mehreren Suchausführungscomputern 102 gleich verteilt werden, um einen Lastausgleich beim Bedingungsvergleich zu erreichen.
Die Konfiguration der Ausführungsform 5 ist dieselbe wie diejenige der Ausführungsform 1; die gemeinsamen Elemente sind mit denselben Bezugszeichen bezeichnet und auf deren Erläuterung wird verzichtet.
Um einen Lastausgleich beim Bedingungsvergleich selbst in dem Fall zu erreichen, in dem Relationen Gruppen teilweise gemeinsam sind, verteilt und weist die Ausführungsform 5 Graphen 70, die von den Suchausführungscomputern 10 gehalten werden, Suchausführungscomputern 102 in Anbetracht der Relationen zu, die teilweise Gruppen gemeinsam sind. In dieser Verarbeitung verwendet die Ausführungsform 5 das Graphendatenempfangsmodul 201, den Datenklassifizierer 205, die Gruppeninformationshalteeinrichtung 204, das Datenzuweisungsbestimmungsmodul 206, die Halteeinrichtung 207 für verteilte Knoteninformationen, das Graphendatenliefermodul 208, die im Manager 131 zur verteilten Graphendatenverwaltung enthalten sind, der in 2 gezeigt ist.
18 ist ein Ablaufplan, der die Verarbeitung für den Manager 131 zur verteilten Graphendatenverwaltung darstellt, um Graphen zu Suchausführungscomputern 102 zu verteilen und zuzuweisen.
Zuerst empfängt das Graphendatenempfangsmodul 201 einen Graphen durch die Kommunikationsvorrichtung 113 des Managementcomputers 101 und sendet ihn zum Datenklassifizierer 205 (Schritt 1401).
Der Datenklassifizierer 205 erfasst die Gruppenzuweisungsmanagementtabelle 700 von der Gruppeninformationshalteeinrichtung 204 und erfasst die Gruppen-ID 702 der Gruppe, zu der der empfangene Graph gehört. Anschließend ruft der Datenklassifizierer 205 die Gruppen-ID 601, die der erfassten Gruppen-ID 702 entspricht, aus der Gruppenmanagementtabelle 600 ab. Der Datenklassifizierer 205 extrahiert eine Relationsliste 602 für die abgerufene Gruppen-ID 601 (Schritt 1402). Ferner erfasst der Datenklassifizierer 205 Gruppen-IDs der Gruppen mit jeder der Relationen, die in der extrahierten Relationsliste 602 enthalten sind, als zugehörige Gruppen-IDs.
Anschließend sendet der Datenklassifizierer 205 den Graphen, die Gruppen-ID 601 der Gruppe, zu der der Graph gehört, und die zugehörigen Gruppen-IDs zum Datenzuweisungsbestimmungsmodul 206 (Schritt 1403).
In Schritt 1404 erfasst das Datenzuweisungsbestimmungsmodul 206 die Zuweisungsmanagementtabelle 800 von der Halteeinrichtung 207 für verteilte Knoteninformationen. Anschließend summiert das Datenzuweisungsbestimmungsmodul 206 die Anzahlen von Graphen, denen die Gruppen-ID zugewiesen ist, und die Relationsgruppen-IDs in jedem Suchausführungscomputer 102, um die Anzahl von zusammengehörenden Graphen in jedem Suchausführungscomputer 102 zu erhalten. Das Datenzuweisungsbestimmungsmodul 206 extrahiert den Suchausführungscomputer 102, der die geringste Anzahl von zusammengehörenden Graphen angibt, sendet den empfangenen Graphen zusammen mit den Ortsinformationen über diesen Suchausführungscomputer 102 zum Graphendatenliefermodul 208 und geht zu Schritt 1405 weiter.
Wenn mehrere Suchausführungscomputer 102 die wenigsten zugewiesenen Graphen angeben, kann das Datenzuweisungsbestimmungsmodul 206 einen Suchausführungscomputer 102 willkürlich auswählen oder kann den Suchausführungscomputer 102 mit den wenigsten zugewiesenen Graphen, der zuerst oder zuletzt gefunden wird, auswählen. Für die Ortsinformationen über den Suchausführungscomputer 102 kann eine IP-Adresse, die Ortsinformationen im Netz angibt, oder eine ID, die einen Suchausführungscomputer eindeutig identifiziert, verwendet werden.
Als nächstes sendet in Schritt 1405 das Graphendatenliefermodul 208 den empfangenen Graphen 70 zum in Schritt 1404 ausgewählten Suchausführungscomputer 102 bei den Ortsinformationen.
Durch die vorstehend beschriebene Verarbeitung schafft die Ausführungsform 5 ein Verfahren zur verteilten Graphendatenverwaltung, das verschiedene Relationen gleich zu mehreren Suchausführungscomputern 102 verteilt. Eine solche verteilte Graphendatenverwaltung kann ein Verfahren zur verteilten Graphendatensuche zum Suchen von gleichen Graphen unter den mehreren Suchausführungscomputern beim Suchen von Graphen mit gemeinsamen Datenrelationen schaffen, das zum Abrufen von Datenteilen führt, die in mehreren Gruppen enthalten sind.
Ausführungsform 6
Beim Suchen der Graphen 70, die unter den Suchausführungscomputern 102 verteilt sind, wenn die Relation, die am meisten in den Graphen 70 enthalten ist, die in den Suchausführungscomputern 102 gehalten werden, als Suchbedingung festgelegt wird, wird die größte Anzahl von möglichen Lösungen extrahiert. Da der Bedingungsvergleich an allen möglichen Lösungen durchgeführt wird, nimmt die Zeit zum Vollenden der Suche mit der Anzahl von möglichen Lösungen zu. Folglich kann die für die verteilte Suche erforderliche Zeit durch Erfassen der Anzahl von Datenrelationen, die in jedem Suchausführungscomputer 102 enthalten sind, und Multiplizieren der Anzahl mit einer Zeit, die für den Bedingungsvergleich pro möglicher Lösung erforderlich ist, abgeschätzt werden, was die Bestimmung, ob eine Suche innerhalb einer festgelegten Zeit vollendet werden kann, unter Verwendung des Ergebnisses der Abschätzung ermöglicht.
In der Ausführungsform 6 schätzt der Managementcomputer 101 eine Zeit ab, die zum verteilten Suchen erforderlich ist, und falls er feststellt, dass die Suche nicht innerhalb einer festgelegten Zeit vollendet wird, fügt er einen Suchausführungscomputer 102 hinzu und weist die Graphen neu zu, um die möglichen Lösungen zu verringern, die an jedem Suchausführungscomputer 102 extrahiert werden.
Die Systemkonfiguration der Ausführungsform 6 wird durch Hinzufügen eines Relationszählwertrechners 1501 und eines Kapazitätsplanungsindikators 1502, wie in 19 dargestellt, zum Managementcomputer 101 der Ausführungsform 1 geschaffen; der Rest der Konfiguration ist dieselbe wie jene der Ausführungsform 1. Die gemeinsamen Elemente sind mit denselben Bezugszeichen bezeichnet und auf deren Erläuterung wird verzichtet.
19 ist ein Blockdiagramm, das ein Beispiel einer Konfiguration des Managementcomputers darstellt. Um eine Graphenzuweisung anzugeben, die erforderlich ist, um die Verarbeitungsfähigkeiten der Suchausführungscomputer 102 festzustellen, stellt der Managementcomputer 101 eine Graphendaten-Kapazitätsmanagementfunktion, die in 19 dargestellt ist, bereit. Der Managementcomputer 101 verknüpft die Halteeinrichtung 204 für verteilte Knoteninformationen und die Gruppeninformationshalteeinrichtung 207, die Funktionsmodule sind, die im Manager 131 zur verteilten Graphendatenverwaltung enthalten sind, mit dem Relationszählwertrechner 1501 und umfasst ferner einen Kapazitätsplanungsindikator 1502. Der Kapazitätsplanungsindikator 1502 zeigt Informationen zum Abschätzen der Zeit, die für jeden Suchausführungscomputer 102 erforderlich ist, um die verteilten Graphen zu suchen, und gibt einen Überschuss oder einen Mangel in jedem Suchausführungscomputer 102 an.
20 ist ein Ablaufplan, der ein Beispiel der Verarbeitung des Managementcomputers 101 darstellt, um die Kapazität für Graphendaten zu managen.
Zuerst erfasst der Relationszählwertrechner 1501 die Gruppenmanagementtabelle 600 von der Gruppeninformationshalteeinrichtung 207 und erfasst die Zuweisungsmanagementtabelle 800 von der Halteeinrichtung 204 für verteilte Knoteninformationen (Schritt 1601).
Als nächstes wählt der Relationszählwertrechner 1501 eine Relation (beispielsweise NAME) aus, die in einer Relationsliste 602 in der Gruppenmanagementtabelle 600 enthalten ist, und erfasst die Gruppen-IDs der Gruppen mit der ausgewählten Relation in den Relationslisten. Anschließend summiert der Relationszählwertrechner 1501 mit Bezug auf die Zuweisungsmanagementtabelle 800 die Anzahlen auf, die den erfassten Gruppen-IDs 601 zugeordnet sind, in der Spalte eines gegebenen Suchausführungscomputers 102 (Schritt 1602). Folglich kann die Anzahl von Relationen (in einem Beispiel die Anzahl von NAMEN), die im gegebenen Suchausführungscomputer 102 enthalten sind, erhalten werden. Der Relationszählwertrechner 1501 führt diese Verarbeitung an allen Suchausführungscomputeren 102 und allen Relationen durch.
Als nächstes bestimmt der Relationszählwertrechner 1501 in Schritt 1603, ob irgendein Suchausführungscomputer 102 existiert, der eine Anzahl von Relationen gleich einem oder mehr als ein Schwellenwert umfasst. Wenn irgendein Suchausführungscomputer 102 mit Relationen gleich oder mehr als der Schwellenwert existiert, geht der Relationszählwertrechner 1501 zu Schritt 1604 weiter, und wenn kein solcher Suchausführungscomputer 102 existiert, verlässt er die Verarbeitung. Der Schwellenwert kann ein vorbestimmter fester Wert sein oder ein Wert, der durch die Eingabevorrichtung 115 des Managementcomputers 101 empfangen wird. Mit Bezug auf die im Voraus gespeicherten vorherigen Suchzeiten kann alternativ die Anzahl von möglichen Lösungen, die zum Abrufen langer gedauert haben als eine spezifische Zeit, als Schwellenwert verwendet werden oder die Relation, die in den Suchausführungscomputern 102 am meisten erscheint, kann als Schwellenwert verwendet werden.
In Schritt 1604 gibt der Kapazitätsplanungsindikator 1502 die Relation in einer Anzahl gleich oder mehr als der Schwellenwert, die Anzahl von Relationen, die in jedem Suchausführungscomputer 102 enthalten sind, und Gruppeninformationen über die Gruppen mit der Relation an die Anzeigevorrichtung 116 aus.
Durch die vorstehend beschriebene Verarbeitung kann die Anzahl von möglichen Lösungen, die einen Bedingungsvergleich beim Suchen der Graphen erfordern, die unter mehreren Suchausführungscomputern 102 verteilt sind, mit Suchbedingungen mit der Relation, die zum Abrufen der größten Anzahl von möglichen Lösungen führt, erfasst werden. Aus dieser Anzahl von möglichen Lösungen kann die Suchzeit mit dem Bedingungsvergleich abgeschätzt werden. Um die Suchzeit zu verringern, können Informationen, die empfehlen, einen Suchausführungscomputer 102 hinzuzufügen oder die Graphen in den Suchausführungscomputeren 102 neu zuzuweisen, dargestellt werden.
Ausführungsform 7
Ein Schema zum Ausdrücken von Daten, das RDF (Ressourcenbeschreibungsrahmen) genannt wird, das durch das W3C (World Wide Web Consortium) standardisiert ist, war bekannt. Der RDF definiert das Ausdrücken von Daten, die Relationen von Ressourcen angeben, mit drei Elementen von Subjekt, Prädikat und Objekt. Ein Satz von diesen drei Elementen wird Tripel genannt. Im Tripel stellen das Subjekt und das Objekt Datenwerte dar und das Prädikat stellt eine Relation zwischen dem Subjekt und dem Objekt dar. Das in einem Tripel enthaltene Subjekt kann das Objekt eines anderen Tripels sein; mehrere Tripel können einen Satz von Daten ausdrücken. Der durch Verbinden von mehreren Tripeln gebildete Satz von Daten weist dieselbe Struktur wie der von dieser Erfindung behandelte Graph auf.
Als Abfragesprache zum Suchen von Graphen, die im RDF ausgedrückt sind, hat das W3C SPARQL (SPARQL-Abfragesprache) empfohlen. Beim Suchen von Graphen in SPARQL kann nach dem Extrahieren von möglichen Lösungen, die einem Datenwert, der durch ein Subjekt oder Objekt dargestellt wird, das durch das RDF-Schema definiert ist, oder einer Relation, die durch ein Prädikat dargestellt wird, entsprechen, ein Bedingungsvergleich an den möglichen Lösungen durchgeführt werden.
Hinsichtlich dieser im RDF-Schema ausgedrückten Graphen können wie in der vorstehend beschriebenen Ausführungsform 1 bis Ausführungsform 6 Graphen mit gemeinsamen Prädikaten oder Relationen als dieselbe Gruppe klassifiziert werden und zu mehreren Suchausführungscomputern 102 verteilt und zugewiesen werden, um einen Lastausgleich und eine Verarbeitung mit höherer Geschwindigkeit beim Suchen durch Durchführen von parallelen Suchen zu erreichen.
Ausführungsform 8
Um eine Vielfalt von Daten im Querschnitt zu verwalten und zu suchen, wie z. B. Text-, Audio-, Bild- und Videodaten, sollten die in jedem Typ von Daten enthaltenen Informationen im gleichen Format verwaltet und im gleichen Schema gesucht werden. In einer Inhalts-Cloud-Architektur zum automatischen Vereinigen von Daten, die in mehreren Speichern gespeichert sind, in einem Datenzentrum über ein Netz, sind beispielsweise dasselbe Format der Informationen und dasselbe Suchschema erforderlich.
Um Informationen im gleichen Format zu verwalten und die Informationen im gleichen Schema zu suchen, können Metadaten verwendet werden. Die Metadaten sind Daten über Daten, die von einer Vielfalt von computerisierten Inhaltsdaten, wie z. B. Text-, Audio- und Bilddaten, durch eine Vielfalt von Erkennungsverarbeitung extrahiert werden. Für die Erkennungsverarbeitung können öffentlich oder allgemein bekannte Techniken verwendet werden; beispielsweise kann eine Technik, die zukünftige Werte von Audio, Bild oder Video erhält und Metadaten aus den Merkmalswerten erzeugt, gegebenenfalls verwendet werden.
Da Metadaten Informationen über eine Vielfalt von Daten umfassen, ist es bevorzugt, die Graphenstruktur zu verwenden, die Metadaten mit Datenwerten und Relationen ausdrücken kann. Wenn Bilddaten eines blauen Autos als Beispiel herangezogen werden, besteht der Graph, der ihre Metadaten darstellt, aus einem Datenteil mit einem Datenwert von ”Auto”, der durch eine Relation von ”Farbe” mit einem Datenteil mit einem Datenwert von ”blau” verbunden ist.
Um eine Vielfalt von Daten wie z. B. Text-, Audio-, Bild- und Videodaten unter Verwendung von Metadaten zu suchen, die in dieser Weise extrahiert werden, ist eine Speichervorrichtung zum integralen Managen der tatsächlichen Daten in Zusammenhang mit dem Graphen von Metadaten erforderlich. Es sollte beachtet werden, dass, da die Daten wie z. B. Text-, Audio-, Bild- und Videodaten im Volumen im Vergleich zu Metadaten größer sind, die Speichervorrichtung eine große Kapazität aufweisen muss, nämlich eine Speichervorrichtung mit mehreren Plattenvorrichtungen.
In einer Umgebung zur Querschnittsverwaltung einer Vielfalt von Daten wie z. B. Text-, Audio-, Bild- und Videodaten kann ein schneller Datenabruf durch eine verteilte Suche der Metadaten in der Graphenstruktur unter Verwendung von mehreren Suchausführungscomputern 102 erreicht werden.
Um die vorstehend erwähnten Metadaten einer Vielfalt von Daten wie z. B. Text-, Audio-, Bild- und Videodaten auf diese Erfindung anzuwenden, kann ein in 21 dargestelltes Computersystem die verteilte Verwaltung und das parallele Suchen von Metadaten implementieren.
21 ist ein Blockdiagramm, das ein Beispiel eines Computersystems für eine verteilte Graphendatenverwaltung und Graphendatensuche darstellt. Die Systemkonfiguration der Ausführungsform 8 wird durch Hinzufügen einer Speichervorrichtung 150 und als Funktionsmodule im Managementcomputer 101 eines Graphenstruktur-Abfrageumsetzers 1701 und eines Datenausgleichszuweisungsmoduls 1702 zur in 1 der Ausführungsform 1 dargestellten Konfiguration bereitgestellt. Der Rest der Konfiguration ist dieselbe wie jene der Ausführungsform 1. Die gemeinsamen Elemente sind durch dieselben Bezugszeichen bezeichnet und auf deren Erläuterung wird verzichtet.
Die Speichervorrichtung 150 umfasst eine CPU 151, einen Speicher 152 und eine Kommunikationsvorrichtung 153 und ist mit einem Managementcomputer 101, Suchausführungscomputern 102 und einem Client 80 über ein Netz 140 verbunden. Die Speichervorrichtung 150 umfasst mehrere Plattenvorrichtungen 160-1 bis 160-n und speichert Metadaten 1610 und Daten 16020 wie z. B. Text-, Audio-, Bild- und Videodaten, die den Metadaten entsprechen. Die CPU 151 führt ein Steuerprogramm aus, das in den Speicher 152 geladen wird, um die Kommunikationsvorrichtung 153 und die Plattenvorrichtungen 160-1 bis 160-n zu steuern. Nachstehend werden die Plattenvorrichtungen 160-1 bis 160-n allgemein mit einem Bezugszeichen 160 bezeichnet.
Der Graphenstruktur-Abfrageumsetzer 1701 setzt eine Suchanforderung, die vom Client 80 empfangen wird, der eine Suche anfordert, in eine Suchabfrage für Graphen um. Das Datenausgleichszuweisungsmodul 1702 steuert die Datenzuweisung, um die E/A-Last auszugleichen, zu den mehreren Plattenvorrichtungen 160, die in der Speichervorrichtung 150 enthalten sind.
Der Graphenstruktur-Abfrageumsetzer 1701 hält Relationen, die in Graphen enthalten sind, die Metadaten 1610 ausdrücken, und klassifiziert Bedingungen über den Typ oder die Kategorie der Daten 1620 in den vom Client 80 empfangenen Suchbedingungen als Relationen und die anderen Bedingungen als Datenwerte, um eine Abfrage für Graphen zu erzeugen. Der Graphenstruktur-Abfrageumsetzer 1701 sendet die erzeugte Abfrage zum Manager 132 für die verteilte Graphendatensuche, um eine verteilte Suche von Graphen durchzuführen. Die als Relationen zu klassifizierenden Suchbedingungen sind beispielsweise Klasseninformationen, die Kategorien wie z. B. ”Fahrzeug”, ”Frucht”, Name” und ”Alter” angeben; die als Datenwerte zu klassifizierenden Suchbedingungen sind Instanzinformationen, die die Substanz der Klasseninformationen angeben, wie z. B. eine mit einem anfänglichen Buchstaben ”A” buchstabierte Frucht, ein Name mit einer Zeichenfolge ”Taro” und ein Alter ”über zwanzig”. Der Graphenstruktur-Abfrageumsetzer 1701 kann eine Abfrage mit Instanzinformationen erzeugen, die durch Klasseninformationen verbunden sind.
Das Datenausgleichszuweisungsmodul 1702 bestimmt die Datenzuweisung zu mehreren Plattenvorrichtungen 160, so dass mehrere Suchausführungscomputer 102 nicht auf dieselbe Plattenvorrichtung 160 zugreifen, um eine E/A-Lastkonzentration zu verhindern.
Insbesondere weist das Datenausgleichszuweisungsmodul 1702 eine zweckgebundene Plattenvorrichtung 160 jedem Suchausführungscomputer 102 zu und weist Metadaten 1620 in der Graphenstruktur und Daten 1620 wie z. B. Text-, Audio-, Bild- oder Videodaten, die den Metadaten entsprechen, die durch den Manager 131 zur verteilten Graphendatenverwaltung verteilt werden, den Plattenvorrichtungen 160 zu, die entsprechend für die Suchausführungscomputer 102 zweckgebunden sind. Die Plattenvorrichtungen 160 werden beispielsweise den Suchausführungscomputern 102 in einer Eins-zu-Eins-Entsprechung zugewiesen.
Beim Verwalten einer Vielfalt von Daten wie z. B. Text-, Audio-, Bild- und Videodaten unter Verwendung von Metadaten in der Graphenstruktur, die durch Erkennungsverarbeitung extrahiert wird, kann die vorstehend beschriebene Verarbeitung die Last, die durch Abrufen von gewünschten Daten verursacht wird, unter mehreren Suchausführungscomputern 102 ausgleichen.
Diese Erfindung ist nicht auf die vorstehend beschriebenen Ausführungsformen begrenzt, sondern umfasst verschiedene Modifikationen. Die vorstehend beschriebenen Ausführungsformen sind in Details zum besseren Verständnis dieser Erfindung erläutert und sind nicht auf jene begrenzt, die alle vorstehend beschriebenen Konfigurationen umfassen. Ein Teil der Konfiguration von einer Ausführungsform kann durch jene einer anderen Ausführungsform ersetzt werden; die Konfiguration einer Ausführungsform kann in die Konfiguration einer anderen Ausführungsform integriert werden. Ein Teil der Konfiguration jeder Ausführungsform kann hinzugefügt, gelöscht oder durch jene einer anderen Konfiguration ersetzt werden. Die vorstehend beschriebenen Konfigurationen, Funktionen und Prozessoren können für alle oder einen Teil von ihnen durch Hardware implementiert werden: beispielsweise durch Entwerfen einer integrierten Schaltung. Die vorstehend beschriebenen Konfigurationen und Funktionen können durch Software implementiert werden, was bedeutet, dass ein Prozessor Programme interpretiert und ausführt, die die Funktionen bereitstellen. Die Informationen von Programmen, Tabellen und Dateien, um die Funktionen zu implementieren, können in einer Speichervorrichtung wie z. B. einem Speicher, einem Festplattenlaufwerk oder einem SSD (Festkörperlaufwerk) oder einem Speichermedium wie z. B. einer IC-Karte oder einer SD-Karte gespeichert werden.
Die Zeichnungen zeigen Steuerleitungen und Informationsleitungen, wie für die Erläuterungen erforderlich betrachtet, zeigen jedoch nicht alle Steuerleitungen oder Informationsleitungen in den Produkten. Tatsächlich kann in Betracht gezogen werden, dass fast alle Komponenten miteinander verbunden sind.

Claims

System zur verteilten Datensuche, das umfasst: einen Managementcomputer mit einem Prozessor und einem Speicher; mehrere Suchausführungscomputer jeweils mit einem Prozessor und einem Speicher; ein Netz, das den Managementcomputer und die mehreren Suchausführungscomputer verbindet, wobei der Managementcomputer umfasst: einen Manager zur verteilten Verwaltung zum Empfangen von Graphen, wobei jeder der Graphen mindestens eine Relation hält, die einen Datenwert mit einem anderen Datenwert verbindet und aus Datenteilen besteht, die durch die mindestens eine Relation verbunden sind, und Verteilen der Graphen zu den mehreren Suchausführungscomputern; und einen Manager zur verteilten Suche zum Senden von Suchbedingungen zu den mehreren Suchausführungscomputern beim Empfang der Suchbedingungen und Empfangen von Suchergebnissen von den mehreren Suchausführungscomputern, wobei jeder der Suchausführungscomputer umfasst: ein Graphenspeichermodul zum Speichern von Graphen, die vom Managementcomputer empfangen werden; und ein Suchausführungsmodul zum Suchen der Graphen mit den vom Managementcomputer empfangenen Suchbedingungen und Zurückgeben eines Suchergebnisses zum Managementcomputer, wobei der Manager zur verteilten Verwaltung des Managementcomputers Graphen mit mindestens einer gemeinsamen Relation als Gruppe klassifiziert und die Graphen, die zur Gruppe gehören, zu den mehreren Suchausführungscomputern verteilt und zuweist, wobei der Manager zur verteilten Suche des Managementcomputers Suchbedingungen mit einer Suchbedingung für die Datenrelation und einer Suchbedingung für den Datenwert zu jedem der mehreren Suchausführungscomputer sendet, um die Durchführung einer parallelen Suche anzufordern, wobei das Suchausführungsmodul in jedem der mehreren Suchausführungscomputer Graphen, die der Suchbedingung für die Datenrelation entsprechen, als mögliche Lösungen extrahiert und einen Bedingungsvergleich an Datenwerten, die in den Graphen enthalten sind, die als möglichen Lösungen extrahiert werden, mit der Suchbedingung für den Datenwert durchführt, um einen Datenteil, dessen Datenwert der Suchbedingung für den Datenwert entspricht, als Suchergebnis zu erfassen.
System zur verteilten Datensuche nach Anspruch 1, wobei, wenn der Manager zur verteilten Verwaltung des Managementcomputers Graphen mit mindestens einer gemeinsamen Relation als Gruppe klassifiziert, der andere Datenwert, der durch die mindestens eine gemeinsame Relation verbunden ist, ein Datenwert ist, an dem der Bedingungsvergleich mit einer Suchbedingung für den Datenwert durchgeführt werden soll.
System zur verteilten Datensuche nach Anspruch 1, wobei beim Klassifizieren von Graphen mit mindestens einer gemeinsamen Relation als Gruppe der Manager zur verteilten Verwaltung des Managementcomputers Anzahlen von Malen eines vergangenen Abrufs von Datenwerten von Datenteilen erfasst, mit denen Relationen verbinden, und Graphen mit mindestens einer gemeinsamen Relation, die mit einem Datenteil verbindet, dessen Datenwert für eine Anzahl von Malen eines ersten Schwellenwerts oder mehr abgerufen wurde, klassifiziert.
System zur verteilten Datensuche nach Anspruch 1, wobei beim Klassifizieren von Graphen mit mindestens einer gemeinsamen Relation als Gruppe der Manager zur verteilten Verwaltung des Managementcomputers Anzahlen von Relationen erfasst, die in allen Graphen enthalten sind, die in jedem der mehreren Suchausführungscomputer gespeichert sind, und Graphen mit mindestens einer gemeinsamen Relation, wobei eine Anzahl von Relationen ein zweiter Schwellenwert oder mehr ist, klassifiziert.
System zur verteilten Datensuche nach Anspruch 1, wobei beim Verteilen und Zuweisen der Graphen zu den mehreren Suchausführungscomputern der Manager zur verteilten Verwaltung des Managementcomputers einen Suchausführungscomputer auswählt, dem die geringsten Anzahlen von Graphen der Gruppe zugewiesen sind, die mit Elementen von mindestens einer Relation erzeugt wird, die mindestens einer Relation gemeinsam ist, die in einem zuzuweisenden Graphen enthalten ist, und den zum ausgewählten Suchausführungscomputer zuzuweisenden Graphen speichert.
System zur verteilten Datensuche nach Anspruch 1, wobei der Managementcomputer ferner ein Planungsmodul zum Erfassen von Anzahlen von Relationen, die in den Graphen in jedem der mehreren Suchausführungscomputer enthalten sind, und in einem Fall, in dem der Suchausführungscomputer mit den Relationen gleich oder mehr als ein dritter Schwellenwert existiert, Ausgeben von Informationen, die das Hinzufügen eines Suchausführungscomputers und eine erneute Zuweisung der Graphen empfehlen, umfasst.
System zur verteilten Datensuche nach Anspruch 1, wobei die Graphen Daten sind, die im RDF-Format ausgedrückt sind, und wobei die Suchbedingungen in SPARQL vorliegen.
System zur verteilten Datensuche nach Anspruch 1, wobei in jedem der Graphen der Datenwert computerisierte Inhaltsdaten umfasst, und wobei die mindestens eine Relation und der andere Datenwert, der durch die mindestens eine Relation mit den computerisierten Inhaltsdaten verbunden ist, Metadaten umfassen, die aus den computerisierten Inhaltsdaten erzeugt sind.
System zur verteilten Datensuche nach Anspruch 1, wobei die mehreren Suchausführungscomputer mit mehreren Speichervorrichtungen mit jeweils dem Graphenspeichermodul verbunden sind und jedem der mehreren Suchausführungscomputer eine zweckgebundene Speichervorrichtung aus den mehreren Speichervorrichtungen zugewiesen ist.
Verfahren zur verteilten Datensuche zum Suchen von Graphen auf mehreren Suchausführungscomputern unter Verwendung eines Managementcomputers mit einem Prozessor und einem Speicher, und wobei die mehreren Suchausführungscomputer jeweils einen Prozessor und einen Speicher umfassen, wobei das Verfahren umfasst: einen ersten Schritt zum Empfangen von Graphen, die jeweils mindestens eine Relation halten, die einen Datenwert mit einem anderen Datenwert verbindet, und aus Datenteilen besteht, die durch die mindestens eine Relation verbunden sind, durch den Managementcomputer; einen zweiten Schritt zum Verteilen der Graphen zu den mehreren Suchausführungscomputern durch den Managementcomputer; einen dritten Schritt zum Speichern der vom Managementcomputer empfangenen Graphen durch die mehreren Suchausführungscomputer; einen vierten Schritt zum Senden von Suchbedingungen zu den mehreren Suchausführungscomputern beim Empfang der Suchbedingungen durch den Managementcomputer; einen fünften Schritt zum Suchen der Graphen mit den Suchbedingungen, die vom Managementcomputer empfangen werden, und Zurückgeben von Suchergebnissen an den Managementcomputer durch die mehreren Suchausführungscomputer; und einen sechsten Schritt zum Empfangen der Suchergebnisse von den mehreren Suchausführungscomputern durch den Managementcomputer, wobei der zweite Schritt Graphen mit mindestens einer gemeinsamen Relation als Gruppe klassifiziert und die Graphen, die zur Gruppe gehören, zu den mehreren Suchausführungscomputern verteilt und zuweist, wobei der vierte Schritt Suchbedingungen mit einer Suchbedingung für die Datenrelation und einer Suchbedingung für den Datenwert zu jedem der mehreren Suchausführungscomputer sendet, um die Durchführung einer parallelen Suche anzufordern, und wobei der fünfte Schritt Graphen, die der Suchbedingung für die Datenrelation entsprechen, als mögliche Lösungen extrahiert und einen Bedingungsvergleich an Datenwerten, die in den Graphen enthalten sind, die als mögliche Lösungen extrahiert werden, mit der Suchbedingung für den Datenwert durchführt, um einen Datenteil, dessen Datenwert der Suchbedingung für den Datenwert entspricht, als Suchergebnis zu erfassen.
Verfahren zur verteilten Datensuche nach Anspruch 10, wobei beim Klassifizieren von Graphen mit mindestens einer gemeinsamen Relation als Gruppe in der zweiten Gruppe der andere Datenwert, der durch die mindestens eine gemeinsame Relation verbunden ist, ein Datenwert ist, an dem der Bedingungsvergleich mit einer Suchbedingung für den Datenwert durchgeführt werden soll.
Verfahren zur verteilten Datensuche nach Anspruch 10, wobei beim Klassifizieren von Graphen mit mindestens einer gemeinsamen Relation als Gruppe im zweiten Schritt der Managementcomputer Anzahlen von Malen eines vergangenen Abrufs von Datenwerten von Datenteilen erfasst, mit denen Relationen verbinden, und Graphen mit mindestens einer gemeinsamen Relation, die mit einem Datenteil verbindet, dessen Datenwert für eine Anzahl von Malen eines ersten Schwellenwerts oder mehr abgerufen wurde, klassifiziert.
Verfahren zur verteilten Datensuche nach Anspruch 10, wobei im zweiten Schritt zum Klassifizieren von Graphen mit mindestens einer gemeinsamen Relation als Gruppe der Managementcomputer Anzahlen von Relationen erfasst, die in allen Graphen enthalten sind, die in jedem der mehreren Suchausführungscomputer gespeichert sind, und Graphen mit mindestens einer gemeinsamen Relation, wobei eine Anzahl von Relationen ein zweiter Schwellenwert oder mehr ist, klassifiziert.
Verfahren zur verteilten Datensuche nach Anspruch 10, wobei beim Verteilen und Zuweisen von Graphen zu den mehreren Suchausführungscomputern im zweiten Schritt der Managementcomputer einen Suchausführungscomputer auswählt, dem die wenigsten Anzahlen der Graphen der Gruppe zugewiesen sind, die mit Elementen von mindestens einer Relation erzeugt sind, die mit mindestens einer Relation gemeinsam ist, die in einem zuzuweisenden Graphen enthalten ist, und den zuzuweisenden Graphen im ausgewählten Suchausführungscomputer speichert.
Verfahren zur verteilten Datensuche nach Anspruch 10, das ferner umfasst: einen sechsten Schritt zum Erfassen von Anzahlen von Relationen, die in den Graphen in jedem der mehreren Suchausführungscomputer enthalten sind, durch den Managementcomputer und in einem Fall, in dem ein Suchausführungscomputer mit den Relationen gleich oder mehr als ein dritter Schwellenwert existiert, Ausgeben von Informationen, die das Hinzufügen eines Suchausführungscomputers und die erneute Zuweisung der Graphen empfehlen.
Verfahren zur verteilten Datensuche nach Anspruch 10, wobei die Graphen Daten sind, die im RDF-Format ausgedrückt sind, und wobei die Suchbedingungen in SPARQL vorliegen.
Verfahren zur verteilten Datensuche nach Anspruch 10, wobei in jedem der Graphen der Datenwert computerisierte Inhaltsdaten umfasst, und wobei die mindestens eine Relation und der andere Datenwert, der mit den computerisierten Inhaltsdaten durch die mindestens eine Relation verbunden ist, Metadaten umfassen, die aus den computerisierten Inhaltsdaten erzeugt sind.
Verfahren zur verteilten Datensuche nach Anspruch 10, wobei die mehreren Suchausführungscomputer mit mehreren Speichervorrichtungen mit jeweils dem Graphenspeichermodul verbunden sind und jedem der mehreren Suchausführungscomputer eine zweckgebundene Speichervorrichtung aus den mehreren Speichervorrichtungen zugewiesen ist.
Managementcomputer, der mit mehreren Suchausführungscomputern verbunden ist, wobei der Managementcomputer umfasst: einen Prozessor; und einen Speicher, wobei der Managementcomputer umfasst: einen Manger zur verteilten Verwaltung, der dazu konfiguriert ist, Graphen zu empfangen, die jeweils mindestens eine Relation halten, die einen Datenwert mit einem anderen Datenwert verbindet, und aus Datenteilen besteht, die durch die mindestens eine Relation verbunden sind, und die Graphen zu den mehreren Suchausführungscomputern zu verteilen; und einen Manager zur verteilten Suche, der dazu konfiguriert ist, Suchbedingungen zu den mehreren Suchausführungscomputern beim Empfang der Suchbedingungen zu senden und Suchergebnisse von den mehreren Suchausführungscomputern zu empfangen, wobei der Manager zur verteilten Verwaltung dazu konfiguriert ist, Graphen mit mindestens einer gemeinsamen Relation als Gruppe zu klassifizieren und die Graphen, die zur Gruppe gehören, zu den mehreren Suchausführungscomputern zu verteilen und zuzuweisen, und wobei der Manager zur verteilten Suche dazu konfiguriert ist, Suchbedingungen mit einer Suchbedingung für die Datenrelation und einer Suchbedingung für den Datenwert zu jedem der mehreren Suchausführungscomputer zu senden, um die Durchführung einer parallelen Suche anzufordern.