BACKGROUND

This specification relates to storing semi-structured data.

Semi-structured data is self-describing data that does not conform to a static, predefined format. For example, one semi-structured data format is JavaScript Object Notation (JSON). A JSON data item generally includes one or more JSON objects. i.e., one or more unordered sets of key/value pairs. Another example semi-structured data format is Extensible Markup Language (XML) An XML data item generally includes one or more XML elements that define values for one or more keys.

SUMMARY

In general, this specification describes techniques for extracting facts from collections of documents.

In general, one innovative aspect of the subject matter described in this specification can be embodied in methods that include the actions of maintaining a plurality of schemas, wherein each schema is associated with one or more encoded data items stored in a first data format in a data item repository, wherein each encoded data item stores a respective value at each of one or more locations in the encoded data item, and wherein each schema maps each of the locations in the data items associated with the schema to a respective key to which the value stored at the location in the data items associated with the schema corresponds; receiving a first semi-structured data item, wherein the first semi-structured data item is in a semi-structured data format, and wherein the first semi-structured data item comprises one or more first key/value pairs, determining that the first semi-structured data item does not match any of the schemas in the plurality of schemas; and in response to determining that the first semi-structured data item does not match any of the schemas in the plurality of schemas: generating a new schema, wherein the new schema maps each of the locations in a first new encoded data item to a respective key to which the value that is stored at the location in the first new encoded data item corresponds, encoding the first semi-structured data item in the first data format to generate the first new encoded data item by storing values corresponding to values from the first key/value pairs at respective locations in the first new encoded data item in accordance with the new schema, storing the first new encoded data item in the data item repository, and associating the first new encoded data item with the new schema.

Other embodiments of this aspect include corresponding computer systems, apparatus, and computer programs recorded on one or more computer storage devices, each configured to perform the actions of the methods. For a system of one or more computers to be configured to perform particular operations or actions means that the system has installed on it software, firmware, hardware, or a combination of them that in operation cause the system to perform the operations or actions. For one or more computer programs to be configured to perform particular operations or actions means that the one or more programs include instructions that, when executed by data processing apparatus, cause the apparatus to perform the operations or actions.

These and other aspects can optionally include one or more of the following features. Determining that the first semi-structured data item does not match any of the schemas in the plurality of schemas comprises determining that the keys from the first key/value pairs do not match the keys mapped to by any of the plurality of schemas. The first schema of the plurality of schemas maps each of the keys from the first key/value pairs to locations and identifies requirements for values of one or more of the keys from the first key/value pairs, and determining that the first semi-structured data item does not match any of the schemas in the plurality of schemas includes determining that the values from the first key/value pairs do not satisfy the requirements identified in the first schema.

The aspect further includes the actions of receiving a second semi-structured data item, wherein the second semi-structured data item comprises one or more second key/value pairs; determining that the second semi-structured data item matches a second schema from the plurality of schemas; and in response to determining that the second semi-structured data item matches the second schema: encoding the second semi-structured data item in the first data format to generate a second new encoded data item by storing values corresponding to the values from the second key/value pairs at respective locations in the second new encoded data item in accordance with the second schema, storing the second new encoded data item in the data item repository, and associating the second new encoded data item with the second schema. Determining that the second semi-structured data item matches the second schema from the plurality of schemas includes determining that the keys mapped to locations by the second schema match the keys from the second key/value pairs. The second schema identifies requirements for values of one or more of the keys mapped to locations by the second schema. Determining that the second semi-structured data item matches the second schema from the plurality of schemas includes determining that the values from the second key/value pairs satisfy the requirements identified in the second schema.

The aspect further includes receiving a query for semi-structured data items, wherein the query specifies requirements for values for one or more keys; identifying schemas from the plurality of schemas that identify locations for values corresponding to each of the one or more keys; for each identified schema, searching the encoded data items associated with the schema to identify encoded data items that satisfy the query; and providing data identifying values from the encoded data items that satisfy the query in response to the query. Searching the encoded data items associated with the schema includes: searching, for each encoded data item associated with the schema, the locations in the encoded data item identified by the schema as storing values for the specified keys to identify whether the encoded data item stores values for the specified keys that satisfy the requirements specified in the query.

Particular embodiments of the subject matter described in this specification can be implemented so as to realize one or more of the following advantages. By dynamically generating schemas for received semi-structured data items, semi-structured data can be stored in an efficient data format without requiring a schema for the semi-structured data to be specified in advance. Queries for data items stored in the efficient data format can be processed efficiently. Using the dynamically generated schemas, users can easily and effectively analyze the semi-structured data that has been stored by an application in a data item repository. For example, users can easily identify potential data quality issues, e.g., by querying for data items that don't follow an expected schema or schemas that match very few data items. As another example, users can easily identify data items that share common properties or particularly popular schemas, i.e., schemas that are associated with large numbers of data items. As another example, because the schemas are generated when encoded data items are converted, users can precisely determine which schemas are being maintained by a semi-structured data storage system at any given point in time. As another example, application developers developing applications that interact with a semi-structured data storage system can more easily develop applications by being provided an understanding of the schemas being maintained by the semi-structured data storage system.

The details of one or more embodiments of the subject matter of this specification are set forth in the accompanying drawings and the description below. Other features, aspects, and advantages of the subject matter will become apparent from the description, the drawings, and the claims.

