Algebraic data types for database query languages

Patent metadata

Field	Value
Publication number	US-10042884-B2
Application number	US-201715638186-A
Country	US
Kind code	B2
Filing date	Jun 29, 2017
Priority date	Sep 30, 2016
Publication date	Aug 7, 2018
Grant date	Aug 7, 2018

Abstract

Methods, systems, and apparatus, including computer programs encoded on computer storage media, for implementing algebraic data types in database query languages. One of the methods includes receiving an expression in a database query language, the expression having a programming language construct representing an algebraic data type, wherein the expression specifies two or more alternative subtypes. Respective domain relations are generated using definitions of each of the alternative subtypes within the expression. Unique domain identifiers are assigned among domain tuples belonging to each alternative subtype. A union relation is generated for the algebraic data type. Unique union identifiers are assigned for union tuples belonging to the union relation. Respective injector relations are generated for each of the alternative subtypes.

First claim

What is claimed is:

1. A computer-implemented method comprising:
receiving an expression in a query language, the expression having a query language construct representing an algebraic data type, wherein the expression specifies two or more alternative subtypes;
generating, for each of the alternative subtypes, a respective domain relation having domain tuples that satisfy a definition of the alternative subtype within the expression;
generating a respective domain id relation for each of the domain relations of the alternative subtypes, wherein the domain id relation for a corresponding domain relation of an alternative subtype has domain id tuples that each assign a respective unique domain identifier to each of the domain tuples belonging to the corresponding domain relation of the alternative subtype;
generating a union relation for the algebraic data type, wherein the union relation assigns a respective branch identifier to each of the two or more alternative subtypes and, for each of the domain id relations, defines union tuples that each have i) a respective unique domain identifier of a domain id tuple of the corresponding domain id relation and ii) a branch identifier for the alternative subtype to which the domain id relation belongs;
assigning unique union identifiers to each of the union tuples belonging to the union relation;
generating a respective injector relation for each of the alternative subtypes, wherein each injector relation for an alternative subtype has injector tuples, each injector tuple having i) a first element from a particular domain tuple of the domain relation for the alternative subtype and ii) a union identifier assigned to a union tuple having (a) a unique domain identifier of the particular domain tuple according to the domain id relation for the alternative subtype and (b) a branch identifier for the alternative subtype;
receiving a query referencing a variable having the algebraic data type, the algebraic data type having the two or more alternative subtypes;
computing query results for the query including identifying one or more injector tuples that satisfy the query, each injector tuple satisfying the query belonging to one of the injector relations generated for the two or more alternative subtypes of the algebraic data type referenced by the query; and
providing the computed query results in response to receiving the query.

2. The method of claim 1 , wherein assigning unique union identifiers to each of the union tuples belonging to the union relation comprises generating a union id relation for the union relation, wherein the union id relation defines uniquely identified union tuples that each assign a unique number to each of the union tuples.

3. The method of claim 2 , wherein generating a respective injector relation for each of the alternative subtypes comprises generating injector tuples by matching domain identifiers in a domain id relation for the alternative subtype to domain identifiers in a union id relation for the algebraic data type to determine domain tuples that should be paired with respective union identifiers in the injector tuples.

4. The method of claim 1 , wherein computing query results for the query comprises computing:
a first injector tuple for a first alternative subtype of the two or more alternative subtypes, and
a second injector tuple for a second alternative subtype of the two or more alternative subtypes.

5. The method of claim 1 , wherein the injector relations are mutually disjoint.

6. The method of claim 5 , further comprising:
determining that an alternative subtype from the alternative subtypes that is an argument in an expression invocation is incompatible with an expected alternative subtype from the alternative subtypes as the argument in the expression invocation; and
in response to determining that an alternative subtype from the alternative subtypes that is an argument in an expression invocation is incompatible with an expected alternative subtype from the alternative subtypes as the argument in the expression invocation, generating a type error.

7. The method of claim 1 , wherein at least one particular alternative subtype depends on another one of the alternative subtypes.

8. The method of claim 1 , wherein generating, for each of the alternative subtypes, a respective domain relation using a definition of the alternative subtype comprises evaluating the definition of the alternative subtype as a predicate in an underlying query language to generate tuples satisfying the definition of the alternative subtype.

9. The method of claim 1 , wherein generating a domain id relation for an alternative subtype comprises assigning the same unique domain identifier to all domain tuples having identical elements.

10. A system comprising one or more computers and one or more storage devices storing instructions that are operable, when executed by the one or more computers, to cause the one or more computers to perform operations comprising:
receiving an expression in a query language, the expression having a query language construct representing an algebraic data type, wherein the expression specifies two or more alternative subtypes;
generating, for each of the alternative subtypes, a respective domain relation having domain tuples that satisfy a definition of the alternative subtype within the expression;
generating a respective domain id relation for each of the domain relations of the alternative subtypes, wherein the domain id relation for a corresponding domain relation of an alternative subtype has domain id tuples that each assign a respective unique domain identifier to each of the domain tuples belonging to the corresponding domain relation of the alternative subtype;
generating a union relation for the algebraic data type, wherein the union relation assigns a respective branch identifier to each of the two or more alternative subtypes and, for each of the domain id relations, defines union tuples that each have i) a respective unique domain identifier of a domain id tuple of the corresponding domain id relation and ii) a branch identifier for the alternative subtype to which the domain id relation belongs;
assigning unique union identifiers to each of the union tuples belonging to the union relation;
generating a respective injector relation for each of the alternative subtypes, wherein each injector relation for an alternative subtype has injector tuples, each injector tuple having i) a first element from a particular domain tuple of the domain relation for the alternative subtype and ii) a union identifier assigned to a union tuple having (a) a unique domain identifier of the particular domain tuple according to the domain id relation for the alternative subtype and (b) a branch identifier for the alternative subtype;
receiving a query referencing a variable having the algebraic data type, the algebraic data type having the two or more alternative subtypes;
computing query results for the query including identifying one or more injector tuples that satisfy the query, each injector tuple satisfying the query belonging to one of the injector relations generated for the two or more alternative subtypes of the algebraic data type referenced by the query; and
providing the computed query results in response to receiving the query.

11. The system of claim 10 , wherein assigning unique union identifiers to each of the union tuples belonging to the union relation comprises generating a union id relation for the union relation, wherein the union id relation defines uniquely identified union tuples that each assign a unique number to each of the union tuples.

12. The system of claim

Assignees

• Semmle Ltd

Inventors

• Schaefer Max
• Eyers-Taylor Alexander

Classifications

• G06F16/2433

  Query languages · CPC title

• G06F16/2452 Primary

  Query translation · CPC title

• G06F16/2448

  for particular applications; for extensibility, e.g. user defined types · CPC title

• G06F16/2291

  User-Defined Types; Storage management thereof · CPC title

• G06F16/24566

  Recursive queries · CPC title