In-database connectivity components analysis of data

Patent metadata

Field	Value
Publication number	US-9465854-B2
Application number	US-201514802934-A
Country	US
Kind code	B2
Filing date	Jul 17, 2015
Priority date	Mar 14, 2013
Publication date	Oct 11, 2016
Grant date	Oct 11, 2016

Abstract

A method determines the connectivity components defined by a set of relations over a set of data elements. For each first data element of a selected subset of data elements, a second data element that is linked to the first data element by a path of relations is selected as its representative, using a randomization process. A new set of relations is created by replacing each first data element of the subset by its representative in at least part of the set of relations.

First claim

What is claimed is:

1. A method for determining connectivity components defined by a set of relations over a set of data elements, wherein the relations and the data elements are stored in a database, the method comprising:
selecting, for each first data element in the set of data elements, a respective second representative data element from among a group of data elements that includes the first data element and those data elements linked to the first data element by a path of relations, including assigning, to each of the data elements in the set of data elements, a random value and basing the selecting on the respective random values assigned to the data elements in the group;
for each first data element, identifying a respective data element assigned to be a leader of each first element and replacing the assigned data element with the representative data element of the first element as the leader of the first element;
iteratively creating a new set of relations by replacing each first data element of the set of data elements by its representative in the set of relations; and
outputting the leader of each data element as an identifier of the connectivity component of which the data element is a member;
wherein the selecting and creating are performed within the database.

2. The method of claim 1 , further comprising: performing the method recursively or iteratively on the new set of relations.

3. The method of claim 2 , further comprising: repeating the method until all relations within the new set of relations are between a data element and the data element itself.

4. The method of claim 3 , further comprising:
removing relations between a data element and said data element itself from the new set of relations, and determining said connectivity components as a result of said removing said relations and determining that the new set of relations is an empty set.

5. The method of claim 1 , wherein the selecting and the creating are performed using database queries.

6. The method of claim 1 , further comprising:
receiving a user request to identify one or more connectivity components within the set of data elements; and
performing the method of claim 1 in response to the user request.

7. The method of claim 1 , wherein a data element represents an individual and a representative data element represents a representative of the individual.

8. The method of claim 1 , wherein a data element represents a voting person and a representative data element represents a representative of the voting person.

9. A computing system for determining connectivity components defined by a set of relations over a set of data elements, wherein the relations and the data elements are stored in a database and the system comprises:
one or more computers; and
one or more storage units storing instructions that when executed by the one or more computers cause the computing system to perform operations comprising:
selecting, for each first data element in the set of data elements, a respective second representative data element from among a group of data elements that includes the first data element and those data elements linked to the first data element by a path of relations, including assigning, to each of the data elements in the set of data elements, a random value and basing the selecting on the respective random values assigned to the data elements in the group;
for each first data element, identifying a respective data element assigned to be a leader of each first element and replacing the assigned data element with the representative data element of the first element as the leader of the first element;
iteratively creating a new set of relations by replacing each first data element of the set of data elements by its representative in the set of relations; and
outputting the leader of each data element as an identifier of the connectivity component of which the data element is a member;
wherein the selecting and creating are performed within the database.

10. The system of claim 9 , the operations further comprising: performing the operations recursively or iteratively on the new set of relations.

11. The system of claim 10 , the operations further comprising: repeating the operations until all relations within the new set of relations are between a data element and the data element itself.

12. The system of claim 11 , the operations further comprising:
removing relations between a data element and said data element itself from the new set of relations, and determining said connectivity components as a result of said removing said relations and determining that the new set of relations is an empty set.

13. The system of claim 9 , wherein the selecting and the creating are performed using database queries.

14. The system of claim 9 , the operations further comprising:
receiving a user request to identify one or more connectivity components within the set of data elements; and
performing the operations of claim 9 in response to the user request.

15. The system of claim 9 , wherein a data element represents an individual and a representative data element represents a representative of the individual.

16. The system of claim 9 , wherein a data element represents a voting person and a representative data element represents a representative of the voting person.

17. A non-transitory computer storage medium encoded with a computer program for determining connectivity components defined by a set of relations over a set of data elements, wherein the relations and the data elements are stored in a database, the computer program comprising instructions that when executed by a system cause the system to perform operations comprising:
selecting, for each first data element in the set of data elements, a respective second representative data element from among a group of data elements that includes the first data element and those data elements linked to the first data element by a path of relations, including assigning, to each of the data elements in the set of data elements, a random value and basing the selecting on the respective random values assigned to the data elements in the group;
for each first data element, identifying a respective data element assigned to be a leader of each first element and replacing the assigned data element with the representative data element of the first element as the leader of the first element;
iteratively creating a new set of relations by replacing each first data element of the set of data elements by its representative in the set of relations; and
outputting the leader of each data element as an identifier of the connectivity component of which the data element is a member;
wherein the selecting and creating are performed within the database.

18. The non-transitory computer storage medium of claim 17 , the operations further comprising: performing the operations recursively or iteratively on the new set of relations.

19. The non-transitory computer storage medium of claim 18 , the operations further comprising: repeating the operations until all relations within the new set of relations are between a data element and the data element itself.

20. The non-transitory computer storage medium of claim 19 , the operations further comprising:
removing relations between a data element and said data element itself from the new set of relations, and determining said connectivity components as a result of said removing said relations and determining that the new set of relations is an em

Assignees

• Pivotal Software Inc

Inventors

• Brand Michael
• Schoppmann Florian
• Fang Chunsheng
• Vawdrey Jarrod James
• Kawaler Emily

Classifications

• G06F17/30569 Primary

  Physics · mapped topic

• G06F17/30958

  Physics · mapped topic

• G06F16/258 Primary

  Data format conversion from or to a database · CPC title

• G06F16/9024 Primary

  Graphs; Linked lists (G06F16/9027 takes precedence) · CPC title

• G06F16/24578

  using ranking · CPC title