Semantic encoding and compression of database tables

• US 6,691,132 B2
• Filed: 12/11/2001
• Issued: 02/10/2004
• Est. Priority Date: 05/16/2001
• Status: Active Grant

• Current Assignee: Reengineering LLC
• Original Assignee: Reengineering LLC
• Inventors: Walker, Adrian D., Benjamin, D. Paul
• Primary Examiner(s): Mizrahi, Diane D.
• Application Number:
  US10/014,970
• Publication Number:
  US 20020178171A1
• Time in Patent Office: 791 Days
• Field of Search: 707/102, 707/10, 707/4, 704/500, 375/261, 380/217.28, 717/141, 711/1, 709/246, 382/253, 708/270, 712/225
• US Class Current: 1/1
• CPC Class Codes: G06F 16/284 Relational databases
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface

Abstract

A method and system are described to allow the encoding and compression of one or more tables of data by splitting each table into two or more sub-tables and allowing the splitting to be followed by permutation of the sub-tables. The method may also include the construction of an interconnection table using a collection of permutations and keys or key numbers, and to optionally allow the permuted tables to be padded with additional data, such that the original tables cannot be queried or reconstructed from the sub-tables without knowledge of the permutations and keys. The method and system also allows efficient querying of the sub-tables to retrieve information that was in the original tables, optionally over a network, and efficient reconstruction of the original tables, given knowledge of the permutations and key numbers. The method and system also supports billing for authorized access to tables of data, management of the permutations via index numbers, and rapid changes in encoding to guard against key theft.

Claims

1. A computer-implemented method for encoding and compressing at least one table of data, comprising the steps of:

splitting each table into two or more subtables; and

permuting the subtables using at least one key; and

selecting one of the splitting of a table into subtables,

the permutations, the key, an equation, a sub-method to combine the permutations and the key, row numbers in the subtables, row numbers in an optional interconnection array and optional padding rows, such that any attempt to obtain information, without knowledge of the permutations, key and equation, and if joining the subtables with an interconnection array, results in one of a table that could be the original table but is not the original table, optionally not including any rows of the original table.

2. The method of claim 1, wherein creating an interconnection table that can also be permuted, such that the at least one table of data cannot be correctly queried or reconstructed from the subtables and the interconnection table without knowledge of the permutation and the key.

3. The method of claim 2, wherein padding the interconnection table with additional data.

4. The method of claim 2, wherein padding the interconnection table with additional data, such that any attempt to query or reconstruct a table from its subtables and padded interconnection table, by joining the subtables and the padded interconnection table, without knowledge of the permutations and keys used to construct the subtables and the unpadded interconnection table, does not reveal any row from the original table.

5. The method of claim 2, wherein padding the interconnection table with additional data, such that the number of rows in the original table is hidden.

6. The method of claim 5, wherein selecting the padding of the interconnection table, such that permuted row numbers which can actually be used, given knowledge of permutations and the key, to query or reconstruct a table from subtables and the interconnection table, are disguised by the padding, such that information in the padded interconnection table appears to be statistically uniform.

7. The method of claim 1, wherein the at least one key comprises a key number.

8. The method of claim 1, wherein a source table is split into subtables, each subtable having a subset of the columns of the source table.

9. The method of claim 1, wherein individual data items in a source column of a source table are each split one or more times, each source column giving rise to two or more columns in at least one subtable.

10. The method of claim 1, wherein splitting the subtables to produce sub-subtables.

11. The method of claim 1, wherein padding the permuted table with additional data.

12. The method of claim 1, wherein padding the permuted table with additional data, such that any attempt to query or reconstruct an original table, by joining the padded subtables, without knowledge of the key used to construct the subtables, does not reveal any row from the original table.

13. The method of claim 1, wherein the source of the data to be encoded is a bulk load destined for a single table in the database.

14. The method of claim 1, wherein the method is used as the only security technique.

15. The method of claim 1, wherein the method is used in combination with at least one of the alternative methods for providing security for a database, the alternative methods including:

(a) access controls;

(b) selectively encrypting the entries in tables of data; and

(c) accessing or transmitting data via a virtual or physical private network.

16. The method of claim 1, wherein the method is used for highly secure distribution of copies of data tables over a network, such that there is no need to encrypt individual names, numbers, or other data items in order to hide the relationships between them.

17. The method of claim 1, wherein:

removing duplicated rows from the subtables; and

creating an interconnection table.

18. The method of claim 1, wherein the method supports authorized access to at least one set of data in a database to at least one authorized user.

19. The method of claim 1, wherein providing one of non-sequential row numbering and labeling for at least one table of data.

20. The method of claim 1, wherein permuting the positions of the rows of the subtables according to one of a permutation, a formula, a key and a formula governed by a key.

21. The method of claim 1, wherein modifying one of the row numbers and labeling of the subtables according to one of a permutation, a formula, a key and a formula governed by a key.

22. The method of claim 1, wherein:

constructing at least one interconnection table, the interconnection table containing one of row numbers and labels of the subtables; and

modifying one of the row numbers and labels of the interconnection table according to one of a permutation, a formula, a key and a formula governed by a key.

23. The method of claim 1, wherein combining one of a permutation and a key using an equation, such that knowledge of the permutation or key and the structure of the equation is necessary in order to correctly reconstruct one or more rows of the original table.

24. The method of claim 1, wherein storing a collection of permutations in the database for use during encoding and decoding.

25. The method of claim 1, wherein managing the collection and generation of permutations for use in encoding and decoding by numbering the permutations using an indexing notation.

26. The method of claim 1, wherein the indexing notation is a base-factorial notation.

27. The method of claim 1, wherein modifying at time intervals one of the permutations, row numbers, equations and interconnection tables used for encoding and decoding in order to defend an encoded database against key theft and other attacks.

28. The method of claim 1, wherein querying the subtables and interconnection tables using a database language, given knowledge of one of the permutations, key, and an equation, to correctly obtain information present in the original tables.

29. The method of claim 1, wherein statically indexing one of the subtables and an interconnection table using a database language.

30. The method of claim 1, wherein dynamically indexing one of the subtables and an interconnection table at one of a query time and an update time using a database language.

31. The method of claim 1, wherein

modifying data in the semantically encoded subtables and an interconnection table;

and

logically updating a non-encoded table that the subtables and the interconnection table represent using a database language and given knowledge of one of the permutations, the key and the equation.

32. The method of claim 1, wherein:

permitting a first computer access to a second computer over a network;

making only the permutations, key and the equation available to authorized computers;

allowing the authorized computer to question the data secured on the second computer;

securely transmitting semantically encoded answers to the questions; and

allowing the authorized computer to decode the answers using one of the permutations, the key and the equation.

33. The method of claim 32, wherein billing users of the authorized computer for usage of the data.

34. The method of claim 33, wherein:

modifying the semantic encoding of the data on the second computer; and

reauthorizing at the authorized computer by transmitting to the authorized computer encrypted versions of one of new permutations, new index numbers of permutations, a new key, and a new equation.

35. The method of claim 1, wherein encrypting one of the permutation, an index number of a permutation, a key, a structure of an equation by one of a private key and a public key, for transmission over a network to an authorized computer.