Decentralized database optimizations

Patent metadata

Field	Value
Publication number	US-11212107-B2
Application number	US-202017098151-A
Country	US
Kind code	B2
Filing date	Nov 13, 2020
Priority date	Aug 12, 2016
Publication date	Dec 28, 2021
Grant date	Dec 28, 2021

Abstract

Techniques for managing data stored within a database, such as a decentralized database are provided. Some techniques involve managing some data within a lower-trust database and some other data within a higher-trust database. A higher-trust database may be a decentralize database including a blockchain. A lower-trust database may store references to data within the blockchain, and optionally other data in association with those references. Disclosed techniques include WHERE clause query handling in databases with reference values, replacement of distinct data in a relational database with a distinct reference to that data, number line storing for secure indexing, APIs for databases, and consensus operations for private blockchain networks.

First claim

What is claimed is:

1. A tangible, non-transitory, machine-readable medium storing instructions that when executed by one or more processors effectuate operations comprising:
obtaining access to a first database having a first trust level and second database having a second, higher trust level, the second database storing at least some information designated as sensitive and not stored in the first database, wherein:
the first database stores relationships between values of a plurality of fields, values of a first subset of the fields, and references to locations of values of a second subset of the fields stored in the second database, and
the references do not reveal the values stored in the second database at the locations indicated by the references;

for a given field in the second subset, forming a mapping of each reference stored in the first database under the given field to a sort key, wherein:
the sort keys are in a namespace that indicates order of the sort keys, such that some sort keys are greater than other sort keys in the namespace,
the sort key namespace is larger than a cardinality of the given field,
at least some sort keys are selected to be ordered in the namespace between:
sort keys mapped to references that correspond to values in the second database that are larger than a value in the second database corresponding to a reference to be mapped to the respective sort key, and
sort keys mapped to references that correspond to values in the second database that are smaller than the value in the second database corresponding to the reference to be mapped to the respective sort key;

receiving a query configured to be applied to the first database; and
determining that the query includes an operator that specifies a sort operation based on the given field in the second subset and, in response to the determination, reforming the query to specify a sort operation based on the sort keys and not based on the references stored in the first database under the given field.

2. The tangible, non-transitory, machine-readable medium of claim 1 , wherein:
the first database comprises a first data structure storing values of records in relation to respective fields, and
the values of the records comprise plain text values in the first subset of the fields, and the references in the second subset of the fields.

3. The medium of claim 2 , wherein:
plain text values for the second subset of the fields are accessed from the second database based on the respective references in the second subset of fields, and
the references do not reveal the plain text values.

4. The tangible, non-transitory, machine-readable medium of claim 1 , wherein selecting at least some sort keys to be ordered in the namespace between sort keys mapped to references that correspond to values in the second database that are larger than a value in the second database corresponding to a reference to be mapped to the respective sort key, and sort keys mapped to references that correspond to values in the second database that are smaller than the value in the second database corresponding to the reference to be mapped to the respective sort key comprises:
selecting a first sort key to be mapped to a first reference that corresponds to a first plain text value in the second database that occurs in a sort order before a plain text value in the second database of a next reference to map to a selected sort key, and
selecting a second sort key to be mapped to a second reference that corresponds to a second plain text value in the second database that occurs in the sort order after the plain text value in the second database of the next reference to map to the selected sort key.

5. The tangible, non-transitory, machine-readable medium of claim 4 , wherein determining that the query includes an operator that specifies a sort operation based on the given field in the second subset comprises:
determining that the query includes an operational clause for which a result is based in part on the sort order of the references within the given field in the second subset of fields.

6. The tangible, non-transitory, machine-readable medium of claim 1 , wherein:
the namespace indicates order among the sort keys based on their values within the namespace, each sort key having a value different than other sort keys in the namespace.

7. The tangible, non-transitory, machine-readable medium of claim 1 , wherein:
the first database is a relational database, and
each value corresponds to an entry within a table of the relational database.

8. The tangible, non-transitory, machine-readable medium of claim 7 , wherein:
an entry within the table of the relational database is a row that includes a plurality of values, each value associated with a different one of the fields, and
the different ones of the fields correspond to different columns associated with a respective set of values from a plurality of entries within the table.

9. The tangible, non-transitory, machine-readable medium of claim 1 , wherein:
a reference is indicative of a location of a plain text value within the second database and not the plain text value, and
reference values of the respective references within the given field in the second subset of fields are not indicative of an order amongst plain text values stored at the respective locations.

10. The tangible, non-transitory, machine-readable medium of claim 9 , wherein:
the sort keys of the respective references within the given field are operable to determine the order of the plain text values stored at the respective locations without one or both of:
sorting the plain text values at query time, and
retrieving the plain text values at query time.

11. The tangible, non-transitory, machine-readable medium of claim 1 , wherein:
the first database is a structured query language database, and
the second database is a blockchain-based database.

12. The tangible, non-transitory, machine-readable medium of claim 1 , wherein:
the namespace of the sort keys for the given field comprises a set of possible sort key values that is greater than the set of references of the given field to map to sort keys, and
values of respective sort keys mapped to the references within the given field are different for at least some different possible sequences in which the references may be mapped without changing order of the references.

13. A computer-implemented method, the computer-implemented method comprising:
obtaining access to a first database having a first trust level and second database having a second, higher trust level, the second database storing at least some information designated as sensitive and not stored in the first database, wherein:
the first database stores relationships between values of a plurality of fields, values of a first subset of the fields, and references to locations of values of a second subset of the fields stored in the second database, and
the references do not reveal the values stored in the second database at the locations indicated by the references;

for a given field in the second subset, forming a mapping of each reference stored in the first database under the given field to a sort key, wherein:
the sort keys are in a namespace that indicates order of the sort keys, such that some sort keys are greater than other sort keys in the namespace,
the sort key namespace is larger than a cardinality of the given field,
at least some sort keys are selected to be ordered in the namespace between:
sort keys mapped to references that correspond to values in the second database that are larger than a value in the second database

Assignees

• Altr Solutions Inc

Inventors

• Beecham James Douglas
• Fly Justin W
• Struttmann Christopher Edward
• Goldfarb Scott Nathaniel
• Chaiken Jackson
• Daly Thomas
• Locke Judson Benton
• Snellman Mark

Classifications

• H04L9/50

  using hash chains, e.g. blockchains or hash trees · CPC title

• G06F2221/2113

  Multi-level security, e.g. mandatory access control · CPC title

• G06F21/62

  Protecting access to data via a platform, e.g. using keys or access control rules · CPC title

• G06F21/6227

  where protection concerns the structure of data, e.g. records, types, queries · CPC title

• H04L9/0637

  Modes of operation, e.g. cipher block chaining [CBC], electronic codebook [ECB] or Galois/counter mode [GCM] · CPC title