In-database connectivity components analysis of data

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 empty set.

21. The non-transitory computer storage medium of claim 17 , wherein the selecting and the creating are performed using database queries.

22. The non-transitory computer storage medium of claim 17 , 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 17 in response to the user request.