System from optimizing query processing of multi-attribute distributed relations using local relation tuple numbers to choose semijoins

• US 5,446,886 A
• Filed: 03/12/1993
• Issued: 08/29/1995
• Est. Priority Date: 03/12/1992
• Status: Expired due to Term

• Current Assignee: Ricoh Company Limited
• Original Assignee: Ricoh Company Limited
• Inventors: Li, Hong
• Primary Examiner(s): Black, Thomas G.
• Assistant Examiner(s): AMSBURY, WAYNE P
• Application Number:
  US08/031,207
• Time in Patent Office: 900 Days
• Field of Search: 395/600
• US Class Current: 707/714
• CPC Class Codes: G06F 16/2456 Join operations
• CPC Class Codes: G06F 16/2471 Distributed queries
• CPC Class Codes: Y10S 707/966 Distributed
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99939 Privileged access

Abstract

A distributed database system includes a communication network having a plurality of nodes each with a distributed database, a local process part for extracting relations from each database by performing local processes at each node when a query including multi-attribute relations thereof is input, a degree setting part for setting a degree number of each of the extracted relations, a relation set part for arranging relation sets each containing relations having the same degree number by grouping the extracted relations according to the degree number, an extraction part for extracting single-attribute relations from each relation set so that the single-attribute relations are added to a first relation set having the lowest degree number, a semijoin operating part for repeatedly semijoining two relations of a only relation set only when the quantity of transfer data resulting from the semijoining is decreased, so that a derived relation is added to a next relation set, and a control part for allowing the semijoin operating part to sequentially perform the semijoining and adding so that each derived relation is added to the transfer data.

Claims

1. A distributed database system for a communication network having a plurality of nodes, each of which nodes includes a distributed database, said distributed database system comprising:

local process means for extracting relations from each database of said communication network by performing local processes at each of said nodes of said communication system when a query including multi-attribute relations is input from one of said nodes;

degree setting means for setting a degree number of each of said extracted relations from said local process means based on (A) tuple numbers of single-attribute relations derived from said multi-attribute relations and (B) a tuple number of each of said multi-attribute relations;

relation set means for arranging a plurality of relation sets, each of which relation sets contains relations having the same degree number in ascending order by grouping said extracted relations from said local process means according to the degree number set by said degree setting means, wherein said relation sets include a first relation set containing relations with the lowest degree number;

extraction means for extracting single-attribute relations from each of said relation sets arranged by said relation set means so that said single-attribute relations are added to said first relation set;

semijoin operating means for repeatedly semijoining two relations of a relation set when a quantity of transfer data after said semijoining is detected to be smaller than a quantity of transfer data before said semijoining, and for adding derived relations resulting from said semijoining to a following relation set among the plurality of relation sets arranged by said relation set means; and

control means or allowing said semijoin operating means to sequentially perform said semijoining and said adding for all of the plurality of relation sets arranged by said relation set means, starting from said first relation set and ending at a relation set having the highest degree number, so that each derived relation resulting from said semijoining is added to the transfer data.

2. A distributed database system according to claim 1, further comprising:

first means for detecting whether or not a derived relation, resulting from said semijoining by said semijoin operating means, is a high-level relation; and

second means for dividing said derived relation into low-level relations when said derived relation is detected to be a high-level relation.

3. A distributed data base system according to claim 2, wherein:

said semijoin operating means semijoins two relations from among said low-level relations from said second means when it is detected that the quantity of transfer data resulting from said semijoining of said two relations is decreased, so that each derived relation resulting from said semijoining is added to a next relation set among the plurality of relation sets arranged by said relation set means.

4. A distributed database system according to claim 1, wherein:

said semijoin operating means includes said degree setting means.

5. A distributed database system according to claim 1, wherein said semijoin operating means includes:

first means for detecting whether or not a derived relation resulting from said semijoining by said semijoin operating means is a high-level relation, the high-level relation having a degree number greater than half of the maximum number of attributes included in the multi-attribute relations of the query.

6. A distributed database system according to claim 1, wherein said semijoin operating means includes:

second means for dividing a derived relation resulting from said semijoining by said semijoin operating means into low-level relations, each of which low-level relations has a degree number smaller than half of the maximum number of attributes included in the multi-attribute relations of the query, when said derived relation is detected to be a high-level relation.

7. A distributed database system according to claim 1, wherein:

said control means obtains the transfer data by adding each derived relation to the transfer data, so that the transfer data is transmitted to said node.

8. A distributed database system according to claim 1, further comprising:

means for sorting relations, included in each relation set of the relation sets arranged by said relation set means, according to the size of each relation in ascending order.

9. A distributed database system according to claim 1, further comprising:

means for detecting whether or not the quantity of the transfer data, after said semijoining is performed by said semijoin operating means, is smaller than the quantity of the transfer data before said semijoining is performed.

10. A distributed database system according to claim 1, wherein:

said degree setting means sets a degree number of a multi-attribute relation to a value "m" in accordance with the following equations and inequalities;

space="preserve" listing-type="equation">K1=min[t1, t2, . . . , tn]

space="preserve" listing-type="equation">K2=min [t1×

t2, t1×

t3, . . . , t.sub.n-1 xt.sub.n ]

space="preserve" listing-type="equation">Kn=t1×

t2×

. . . ×

tn

space="preserve" listing-type="equation">K1≦

K2≦

. . . ≦

Km≦

T<

Km+1≦

. . . ≦

Kn

wherein;

T is a tuple number of said multi-attribute relation,

ti (i=1,2, . . . ,n) are tuple numbers of single-attribute relations derived from said multi-attribute relation, and

Ki are integers derived from the tuple numbers of the single-attribute relations.