Method and system for unordered relational database retrieval returning distinct values

• US 20030014390A1
• Filed: 07/02/2002
• Published: 01/16/2003
• Est. Priority Date: 07/12/2001
• Status: Active Grant

• Current Assignee: Twitter Inc (X Holdings Corp.)
• Original Assignee: International Business Machines Corporation
• Inventors: Zuzarte, Calisto Paul, Finlay, Ian R., Lai, Tony Wen Hsun, Zilio, Daniel C.
• Granted Patent: US 7,752,160 B2
• Time in Patent Office: Days
• US Class Current: 707/1
• CPC Class Codes: G06F 16/24554 Unary operations; Data partitioning operations
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching

Abstract

The retrieval of distinct tuples in a relational database management system. In response to a request from a consumer process for distinct tuples in a relational database table matching a defined criteria, a distinct operator component sequentially requests tuples from a source component. The source component access the database table and returns a tuple in the sequence to the distinct operator component. The distinct operator component passes each tuple in the sequence to an auxiliary logger. The auxiliary component receives a tuples from the distinct component and determines if it is distinct from other previously received tuples in the sequence to verify its uniqueness to the distinct operator. Tuples that are verified as unique by the auxiliary logger are returned to the consumer process by the distinct operator upon verification.

Claims

1. A method for providing a consumer process with a set of relational data, the method comprising the steps of:

a) retrieving from a database table a tuple in a sequence of tuples, the tuple satisfying the defined criteria,

b) determining whether the tuple is unique in comparison to previously retrieved tuples in the sequence,

c) providing the consumer process with the tuple where the tuple is unique and discarding the tuple where the tuple is not unique, and

d) repeating the above steps until all tuples matching a defined criteria have been retrieved from the relational table.

2. A relational database management system comprising a source component;

an auxiliary logger component, and a distinct operator, the relational database management system supporting the provision of data from a defined table to a consumer process, the consumer process requesting data from the distinct operator component;

the distinct operator component for sequentially requesting a set of tuples from the source component upon a request from the consumer process, and for accepting tuples returned from the source component, for sequentially passing the tuples in the set of tuples to the auxiliary logger component for uniqueness verification, and for passing only verified unique tuples to the consumer process,

the source component for accessing a tuple in the set of tuples from the defined table upon request from the distinct operator component and providing the tuple to the distinct operator component, and

the auxiliary logger component for sequentially receiving tuples in the set of tuples from the distinct operator component and determining if each sequentially received tuple is distinct from other previously returned tuples in the sequence to verify the uniqueness of each sequentially received tuple to the distinct operator component.

3. The relational database management system of claim 2 in which the auxiliary component includes a hash table to which each unique sequentially received tuple is added.

4. The relational database management system of claim 2 in which the auxiliary component includes a sorted data structure to which each unique sequentially received tuple is added.

5. A computer readable medium containing program instructions for the retrieval of distinct tuples in a relational database management system, the program instructions for providing a distinct operator component,

providing a source component, and

providing an auxiliary logger component, wherein the relational database management system supports the provision of data from a defined table to a consumer process, wherein the consumer process requests data from the distinct operator component, wherein the instruction for the distinct operator component further includes instructions for:

sequentially requesting a set of tuples from the source component upon a request from the consumer process, and for accepting tuples returned from the source component

sequentially passing the tuples in the set of tuples to the auxiliary logger component for uniqueness verification, and

passing only verified unique tuples to the consumer process, the source component comprising code means for accessing a tuple in the set of tuples from the defined table upon request from the distinct operator component and providing the tuple to the distinct operator component, and

wherein the instructions for the auxiliary logger component further includes instructions for sequentially receiving tuples in the set of tuples from the distinct component and for determining if each sequentially received tuple is distinct from other previously returned tuples in the sequence to verify the uniqueness of each sequentially received tuple to the distinct operator component.

6. The computer readable medium of claim 5 in which the instructions for determining if each sequentially received tuple is distinct includes instructions for maintaining a hash table, for verifying uniqueness of tuples using the hash table and for adding each unique sequentially received tuple to the hash table.

7. The computer readable medium of claim 5 in which the instructions for determining if each sequentially received tuple is distinct further includes instructions for maintaining a sorted data structure, for verifying uniqueness of tuples using the sorted data structure and for adding each unique sequentially received tuple to the sorted data structure.

8. A computer readable medium containing program instructions for the retrieval of distinct tuples in a relational database management system, the program instructions for providing a distinct operator component,

providing a source component, and

providing an auxiliary logger component, wherein the relational database management system supports the provision of data from a defined table to a consumer process, wherein the consumer process requests data from the distinct operator component, wherein the instruction for the distinct operator component further includes instructions for:

sequentially requesting a set of tuples from the source component upon a request from the consumer process,

sequentially passing one or more tuples in the set of tuples to the auxiliary logger component for uniqueness verification, and

passing only verified unique tuples to the consumer process, the source component comprising code means for accessing one or more tuples in the set of tuples from the defined table upon request from the distinct operator component and returning a subset of tuples to the distinct operator component, and

wherein the instructions for the auxiliary logger component further including instructions for sequentially receiving a verification set of tuples in the set of tuples from the distinct component and for determining if each tuple in the verification set of tuples is distinct from other previously received tuples in the sequence to verify the uniqueness of each tuple in the verification set of tuples to the distinct operator component.

9. The computer readable medium of claim 8 wherein the instructions for determining if each sequentially received tuple is distinct includes instructions for maintaining a hash table and for verifying uniqueness of tuples using the hash table and for adding each unique sequentially received tuple to the hash table.

10. The computer readable medium of claim 8 in which the instructions for determining if each sequentially received tuple is distinct includes instructions for maintaining a sorted data structure and for verifying uniqueness of tuples using the sorted data structure and for adding each unique sequentially received tuple to the sorted data structure.