Semmle Limited

Microsoft Technology Licensing, LLC

Michael Peyton Jones

Alexander Eyers-Taylor

Aditya Sharad

Methods, systems, and apparatus, including computer programs encoded on computer storage media, for performing local distribution heuristics. One of the methods includes receiving an original expression having a conjunction comprising a context term and a disjunction of a plurality of other terms. The context term and the disjunction are evaluated according to one or more local distribution heuristics to determine that the context term is a candidate for distribution across the disjunction of the plurality of other terms. In response, a transformed expression is generated in which the candidate context term is distributed across the disjunction of the plurality of other terms.

Query language distribution heuristics

Methods, systems, and apparatus, including computer programs encoded on computer storage media, for performing differential recursive evaluation. One of the methods includes receiving an original recursive expression that defines tuples belonging to an output relation. A final delta expression is generated including repeatedly applying one or more delta rules to the initial delta expression, wherein the final delta expression has at least one call to a delta relation that represents tuples generated by the final delta expression on a previous iteration. Until the final delta expression generates no new tuples, the final delta expression is evaluated using the tuples computed by the final delta expression on the previous iteration wherever the call to the delta relation occurs and the output relation is updated including adding to the output relation any tuples newly generated by evaluating the final delta expression.

Differential recursive evaluation

Methods, systems, and apparatus, including computer programs encoded on computer storage media, for performing differential recursive evaluation of recursive aggregates. One of the methods includes receiving an original recursive expression that defines tuples belonging to an output relation, wherein the original recursive expression has a recursive aggregation construct, the recursive aggregation construct having a range and a recursive term. An aggregates delta rule is applied to the initial delta expression to generate a final delta expression having an existential term and a gamma term. The existential term is evaluated to generate tuples related by the range and tuples in the delta relation, and the aggregation construct is evaluated using tuples generated by the existential term as the range of the aggregation construct. The output relation is updated including adding to the output relation any tuples newly generated by evaluating the final delta expression.

Growing community of inventors

Oxford, United Kingdom

Michael Peyton Jones