System and method to join and cut two-way rest overlay trees for distributed knowledge bases

Patent metadata

Field	Value
Publication number	US-9092497-B2
Application number	US-201213371828-A
Country	US
Kind code	B2
Filing date	Feb 13, 2012
Priority date	Sep 29, 2011
Publication date	Jul 28, 2015
Grant date	Jul 28, 2015

Abstract

System and method of event-driven synchronization of a database distributed among servers connected in a tree topology, including: transmitting, from a root server, a composition request to a first level of child servers of the root server; recursively transmitting, from each child server of a first level, a composition request to child servers at a second level, wherein the second level is lower than the first level; recursively transmitting, from each child server of the second level, a notification message to child servers at the first level, wherein the notification message comprises an identification of database fragments accessible to the child server; transmitting, from child servers at the first level, respective notification messages to the root server, wherein the root server synchronizes an availability of database fragments from the respective notification messages transmitted to the root server. Subtrees may be cut from or joined to the tree topology.

First claim

What is claimed is:

1. A system to provide event-driven synchronization of a database distributed among a plurality of servers connected in a tree topology, comprising:
a root server further comprising a transceiver coupled to a processor, where the transceiver is configured to transmit, from the root server of the tree topology, a composition request to child servers at a first predetermined level;
the child servers at the first predetermined level of the tree topology, wherein each of the child servers at the first predetermined level further comprises a transceiver coupled to a processor, the transceiver configured to recursively transmit a composition request to child servers at a second predetermined level of the tree topology, wherein the second predetermined level is lower than the first predetermined level;
the child servers at the second predetermined level of the tree topology, wherein each of the child servers at the second predetermined level further comprises a transceiver coupled to a processor, the transceiver configured to recursively transmit a notification message to child servers at the first predetermined level of the tree topology, wherein the notification message comprises an identification of database fragments accessible to the child server;
at child servers at the first predetermined level of the tree topology, the transceiver transmits respective notification messages to the root server in the response to receiving the notification messages, wherein each of the child servers at the first predetermined level combines results received in the notification messages from their respective child servers at the second predetermined level with results associated with database fragments accessible to the child server itself;
wherein the root server merges the respective notification messages and synchronizes an availability of database fragments from the respective notification messages transmitted to the root server to form a virtual knowledge database,
wherein the step of recursively transmitting, from each child server of a first predetermined level of the tree topology, a composition request to child servers at a second predetermined level of the tree topology, comprises evaluating the following relationship:

V
⁡

(

P
,

S
i

)

=

K
⁡

(

P
,

S
i

)

⋃

⋃

C
∈

c
⁡

(
P
)

⁢

V
⁡

(

C
,

S
i

)

wherein:
P comprises a parent node;
C comprises a child node;
S i comprises a knowledge service on node i;
i comprises an index variable;
V( ) comprises a view of virtual knowledge base for service S i at node P;
K( ) comprises a knowledge base for service S i at node P; and
c(P) comprises a set of child nodes of node P.

2. The system of claim 1 , wherein the root server and child servers provide RESTful web services.

3. The system of claim 1 , wherein the tree topology comprises an overlay network of REST servers connected by a composition links and a notification links.

4. The system of claim 3 , further comprising the steps of:
pausing a processing of update events;
retrieving a reference count from a root node of a subtree to add to the tree topology;
updating a database mapping in the root server; and
resuming the processing of update events.

5. The system of claim 4 , wherein the reference count is determined in accordance with the following relationship:

rc
⁡

(

P
,

S
i

,

K
j

)

=



f
⁡

(

P
,

S
i

,

K
j

)



+

∑

C
∈

c
⁡

(
P
)

⁢

rc
⁡

(

C
,

S
i

,

K
j

)

wherein:
rc( ) comprises a reference count function;
ƒ( ) comprises a set of fragments of knowledge base Kj;
P comprises a parent node;
C comprises a child node;
c(P) comprises a set of child nodes of node P;
Si comprises a service;
Kj comprises a fragment of a knowledge base; and
i, j comprise index variables.

6. The system of claim 4 , further comprising: exchanging corrective messages between a node of the overlay tree and the root node of the subtree in order to add to the tree topology.

7. The system of claim 4 , further comprising:
providing a delete command

Assignees

• Li Li
• Chou Wu
• Avaya Inc

Inventors

• Li Li
• Chou Wu

Classifications

• G06F17/30575 Primary

  Physics · mapped topic

• G06F16/27 Primary

  Replication, distribution or synchronisation of data between databases or within a distributed database system; Distributed database system architectures therefor · CPC title