Semantic encoding and compression of database tables

• US 20020178171A1
• Filed: 12/11/2001
• Published: 11/28/2002
• Est. Priority Date: 05/16/2001
• Status: Active Grant

• Current Assignee: Reengineering LLC
• Original Assignee: Reengineering LLC
• Inventors: Walker, Adrian D., Benjamin, D. Paul
• Granted Patent: US 6,691,132 B2
• Time in Patent Office: Days
• US Class Current: 707/102
• 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 sub-tables; and

permuting the sub-tables using at least one key.

2. The method of claim 1, further comprising the step of 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 sub-tables and the interconnection table without knowledge of the permutation and the key.

3. The method of claim 2, further comprising the step of padding the interconnection table with additional data.

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

5. The method of claim 2, further comprising the step of 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, further comprising the step of 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 sub-tables 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 sub-tables, 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, further comprising the step of splitting the sub-tables to produce sub-sub-tables.

11. The method of claim 1, further comprising the step of padding the permuted table with additional data.

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

13. The method of claim 1, further comprising the step of selecting one of the splitting of a table into sub-tables, the permutations, the key, an equation, a method to combine the permutations and the key, row numbers in the sub-tables, row numbers in an interconnection array and padding rows, such that any attempt to obtain information, without knowledge of the permutations, key and equation, and if joining the sub-tables with an interconnection array, results in a large amount of plausible, but misleading, information, not including any rows of the original table.

14. 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.

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

16. 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.

17. 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.

18. The method of claim 1, further comprising the steps of:

removing duplicated rows from the sub-tables; and

creating an interconnection table.

19. 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.

20. The method of claim 1, further comprising the step of providing one of non-sequential row numbering and labeling for at least one table of data.

21. The method of claim 1, further comprising the step of permuting the positions of the rows of the sub-tables according to one of a permutation, a formula, a key and a formula governed by a key.

22. The method of claim 1, further comprising the step of modifying one of the row numbers and labeling of the sub-tables according to one of a permutation, a formula, a key and a formula governed by a key.

23. The method of claim 1, further comprising the steps of:

constructing at least one interconnection table, the interconnection table containing one of row numbers and labels of the sub-tables; 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.

24. The method of claim 1, further comprising the step of 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.

25. The method of claim 1, further comprising the step of storing a collection of permutations in the database for use during encoding and decoding.

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

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

28. The method of claim 1, further comprising the step of 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.

29. The method of claim 1, further comprising the step of querying the sub-tables 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.

30. The method of claim 1, further comprising the step of statically indexing one of the sub-tables and an interconnection table using a database language.

31. The method of claim 1, further comprising the step of dynamically indexing one of the sub-tables and an interconnection table at one of a query time and an update time using a database language.

32. The method of claim 1, further comprising the steps of:

modifying data in the semantically encoded sub-tables and an interconnection table; and

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

33. The method of claim 1, further comprising the steps of:

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.

34. The method of claim 33, further comprising the step of billing users of the authorized computer for usage of the data.

35. The method of claim 34, further comprising the steps of:

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.

36. The method of claim 1, further comprising the step of 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.

38. The apparatus of claim 37, further comprising at least one client computer connected over a network, the server or peer computer storing the data, such that the client computer may question the data on the server or peer computer and may securely obtain answers to the questions.

37. An apparatus for encoding and compressing at least one table of data, comprising one of a server, a peer computer, and a computer having data storage devices connected thereto, wherein the data storage device stores a database.