US 9,959,295 B1Granted

S-expression based computation of lineage and change impact analysis

AssigneeNumerify, Inc.

InventorsRahul Kapoor, Sunny Tulsi Sreedhar Murthy

Life of this patent

Estimating the term…

Loading patent…

Abstract

Systems and processor-implemented methods of S-expression based computation of lineage and change impact analysis. An SQL expression is converted into an S-expression tabular structure. A function table including a plurality of functions associated with S-expression tabular structure tabulated against at least one of a function name, a derived column and a derived table and an argument table including plurality of arguments associated with the S-expression tabular structure tabulated against at least one of an argument type, a function identifier linking the arguments to the function table, a computed from function, a reference to entity or a literal value, is generated based on the S-expression tabular structure. At least one of lineage or change impact analysis for an entity is determined based on the function table and the argument table, where lineage provides a provenance of the entity or attribute from a source entity or a source attribute.

Claims20

Dependent claims

One or more non-transitory computer readable storage mediums storing one or more sequences of instructions, which when executed by one or more processors, causes:

converting a SQL expression into an S-expression tabular structure, wherein said S-expression tabular structure comprises a nested list data structure, wherein each element of said nested list data structure is a list in itself, and wherein said SQL expression is converted to the nested list data structure using a functional notation for the SQL expression, with SQL keywords at a plurality of levels of the SQL expression serving as function keywords, and each list of the nested list representation comprising the SQL keywords followed by arguments from the functional notation for the SQL expression;
generating a function table based on said S-expression tabular structure, wherein said function table comprises a plurality of functions associated with said S-expression tabular structure tabulated against at least one of a function name, a derived column, and a derived table;
generating an argument table based on said S-expression tabular structure, wherein said argument table comprises a plurality of arguments associated with said S-expression tabular structure tabulated against at least one of an argument type, a function identifier linking the arguments to the function table, a computed from function, a reference to entity or a literal value;
determining at least one of lineage or change impact analysis for an entity of said nested list data structure based on said function table and said argument table by computing a lineage list for a derived column by generating a pivoted function table which is a map of derived columns to functions contributing to derived columns, and by computing a change impact analysis list by computing a pivoted argument table which is a map of entities and functions to which they contribute, wherein said lineage provides a provenance of said entity or attribute from a source entity or a source attribute, and wherein said change impact analysis is an analysis of an impact of a change in at least one of a source attribute, a source entity, an intermediate attribute or an intermediate entity to one or more downstream attributes or one or more downstream entities;
and
creating a computer-generated model run on a computer based on at least one of the lineage or change impact analysis,
wherein said S-expression tabular structure improves a programming of the computer-generated model run on the computer compared to the SQL expression by programmatically decomposing, understanding, and manipulating programming expressions and reconstructing the expressions, and
wherein said S-expression tabular structure reduces a computational complexity of the lineage or change impact analysis.

5 more elements

A system comprising:

a processor;
and
a non-transitory computer readable storage medium comprising one or more modules executable by said processor, wherein said one or more modules comprises:
an S-expression conversion module for converting a SQL expression into an S-expression tabular structure, wherein said S-expression tabular structure comprises a nested list data structure, wherein each element of said nested list data structure is a list in itself, and wherein said SQL expression is converted to the nested list data structure using a functional notation for the SQL expression, with SQL keywords at a plurality of levels of the SQL expression serving as function keywords, and each list of the nested list representation comprising the SQL keywords followed by arguments from the functional notation for the SQL expression;
a function table module for generating a function table based on said S-expression, wherein said function table comprises a plurality of functions associated with said S-expression tabular structure tabulated against at least one of a function name, a derived column and a derived table;
an argument table module for generating an argument table based on said S-expression, wherein said argument table comprises a plurality of arguments associated with said S-expression tabular structure tabulated against at least one of an argument type, a function identifier linking the arguments to the function table, a computed from function, a reference to entity or a literal value;
a lineage module for determining a lineage for an entity of said nested list data structure based on said function table and said argument table by computing a lineage list for a derived column by generating a pivoted function table which is a map of derived columns to functions contributing to derived columns, wherein said lineage provides a provenance of said entity or an attribute from a source entity or a source attribute respectively;
a change impact analysis module for determining a change impact analysis for said entity based on said function table and said argument table by computing a change impact analysis list by computing a pivoted argument table which is a map of entities and functions to which they contribute, wherein said change impact analysis is an analysis of an impact of a change in at least one of a source attribute, a source entity, an intermediate attribute or an intermediate entity to one or more downstream attributes or one or more downstream entities;
and
a computer-generated model run on a computer based on at least one of the lineage or change impact analysis,
wherein said S-expression tabular structure improves a programming of the computer-generated model run on the computer compared to the SQL expression by programmatically decomposing, understanding, and manipulating programming expressions and reconstructing the expressions, and
wherein said S-expression tabular structure reduces a computational complexity of the lineage or change impact analysis.

9 more elements

A processor-implemented method comprising:

converting a SQL expression into an S-expression tabular structure, wherein said S-expression tabular structure comprises a nested list data structure, and wherein each element of said nested list data structure is a list in itself, and wherein said SQL expression is converted to the nested list data structure using a functional notation for the SQL expression, with SQL keywords at a plurality of levels of the SQL expression serving as function keywords, and each list of the nested list representation comprising the SQL keywords followed by arguments from the functional notation for the SQL expression;
generating a function table based on said S-expression tabular structure, wherein said function table comprises a plurality of functions associated with said S-expression tabular structure tabulated against at least one of a function name, a derived column, and a derived table;
generating an argument table based on said S-expression tabular structure, wherein said argument table comprises a plurality of arguments associated with said S-expression tabular structure tabulated against at least one of an argument type, a function identifier linking the arguments to the function table, a computed from function, a reference to entity or a literal value;
and
determining at least one of lineage or change impact analysis for an entity of said nested list data structure based on said function table and said argument table by computing a lineage list for a derived column by generating a pivoted function table which is a map of derived columns to functions contributing to derived columns, and by computing a change impact analysis list by computing a pivoted argument table which is a map of entities and functions to which they contribute, wherein said lineage provides a provenance of said entity or attribute from a source entity or a source attribute, and wherein said change impact analysis is an analysis of an impact of a change in at least one of a source attribute, a source entity, an intermediate attribute or an intermediate entity to one or more downstream attributes or one or more downstream entities;
and
creating a computer-generated model run on a computer based on at least one of the lineage or change impact analysis,
wherein said S-expression tabular structure improves a programming of the computer-generated model run on the computer compared to the SQL expression by programmatically decomposing, understanding, and manipulating programming expressions and reconstructing the expressions, and
wherein said S-expression tabular structure reduces a computational complexity of the lineage or change impact analysis.

6 more elements

Dependencies are inferred from the claim text.