Note: Descriptions are shown in the official language in which they were submitted.
Attorney Docket No. 05793.3620-00000
SYSTEMS AND METHODS FOR CODE PARSING AND LINEAGE DETECTION
CROSS-REFERENCE TO RELATED APPLICATIONS
[001] This application claims priority under 35 U.S.C. 119 to U.S.
Provisional
Application No. 62/527,816, filed on June 30, 2017, which is expressly
incorporated
herein by reference in its entirety.
DESCRIPTION
Technical Field
[002] This disclosure generally relates to big data analytics, and more
particularly, to lineage detection and code parsing.
Background
[003] Most financial and information technology companies now rely on various
database management systems (DBMS) to store and manipulate "big data," that
is,
large and complex collections of data, in order to conduct business. For
example,
companies may create databases in connection with their DBMSs consisting of
structured sets of these data collections. The DBMSs may use database
applications to
operate on the databases to perform many complex calculations for their
customers.
Programming languages such as SQL are often used by these applications to
create,
manage, and use the databases. For these companies, accuracy is often an
important
factor in the operation of a DBMS, because inaccurate calculations performed
in the
applications may lead to various negative business and legal outcomes.
However,
accurate, efficient, and fast calculations may lead to positive outcomes.
[004] Thus, many financial companies seek to improve the operation of their
DBMSs by identifying and quickly resolving various data defects related to
calculations
1
CA 2983510 2017-10-24
4.
Attorney Docket No. 05793.3620-00000
performed by database applications. Often, this involves determining the "data
lineage"
of calculations of interest. Data lineage includes identifying the hierarchy,
discovering
the location, and monitoring changes of data elements within a database used
in a
calculation. However, DBMSs themselves are often unable to provide this data
lineage
information; thus, accurate and reliable solutions are needed.
[005] To address this issue, third parties have provided diagnostic
applications
for "parsing," that is, dividing an SQL file into smaller portions by
following a set of rules
to understand the structure and "grammar" of the SQL code. These software
applications, such as ZQLTM, JSqlParserTM, or General SQL ParserTM, work by
externally analyzing SQL code in SQL files and providing an output. Once an
SQL file
is parsed, these applications attempt to identify data lineage information
based on the
parsed SQL.
[006] However, these third parties' applications are often inadequate for
determining data lineage for many SQL files. For example, they cannot
determine the
data lineage for complex SQL files embodying advanced but common SQL concepts,
such as "select all" statements, orphaned columns, column aliases, multiple
dependent
queries, etc.
[007] In view of these and other shortcomings and problems with database
management systems and third party software applications, improved systems and
techniques for lineage detection and code parsing are desirable.
SUMMARY
[008] The present invention addresses the disadvantages of the prior art by
providing novel lineage detection systems, methods, and techniques for lineage
detection of components of a database. Unlike any prior implementations, the
disclosed
2
CA 2983510 2017-10-24
Attorney Docket No. 05793.3620-00000
systems and methods improve data quality by allowing for the construction of
accurate
metadata of Important Data Elements (i.e., data elements that are critical in
business
analysis and decision-making) in various environments. This is significant
because
many critical business models have multiple metrics, defined by multiple
Important Data
Elements (IDEs) residing in different and complex databases. Thus, the
disclosed
systems and methods may provide clean, accurate, and complete lineage
detection of
database components to help consumers and programmers understand the
definition of
calculations, quickly identify the source of data defects, and efficiently
resolve other
data issues. Moreover, the disclosed systems and methods may improve existing
computing systems not only as discussed above, but also by providing the
capability to
universally process SQL code. For example, this universal processing of SQL
code
involves parsing multiple disparate implementations of SQL code employed by
various
DBMS products (e.g., Oracle , Teradata , PostgreSQLTM, Microsoft SQL Server ,
and
MySQL-rm). To provide these improvements, the disclosed systems and methods
may
be implemented using a combination of conventional hardware, firmware, and/or
software, as well as specialized hardware, firmware, and/or software, such as
a
machine constructed and/or programmed specifically for performing functions
associated with the disclosed method steps. However, in some embodiments,
disclosed systems and methods may be implemented instead in dedicated
electronic
hardware.
[009] According to the disclosed embodiments, a lineage detector or system may
comprise a processor and a memory device storing instructions. Lineage
detector may
acquire a first parameter specifying a body of source code and a second
parameter
3
CA 2983510 2017-10-24
Attorney Docket No. 05793.3620-00000
specifying a target calculation. The target calculation may include one or
more metrics,
processes, IDEs, or the like.
[010] In some embodiments, lineage detector may also parse the source code
using various techniques, such as translating "select all" statements,
resolving orphaned
columns, resolving column aliases, and resolving references between multiple
queries,
etc. After parsing the source code, lineage detector may determine the data
lineage of
the specified target calculation based on the parsed source code. According to
some
embodiments, it may also follow that lineage detector may generate an output
of the
determined data lineage and display the generated output.
[011] Consistent with the present embodiments, a method for detecting data
lineage is also disclosed. The method may include various steps, for example,
acquiring a first parameter identifying a body of source code and a second
parameter
identifying a target calculation in the source code body; parsing the source
code;
determining data lineage of the target calculation based on the parsed source
code; and
generating an output of the determined data lineage.
[012] Morevoer, according to the disclosed embodiments, a code parser is
disclosed. The code parser or system, for example, may have a memory device
storing
instructions and a processor configured to execute instructions to, for
example, acquire
a first parameter identifying source code; acquire the source code from the
first
parameter; parse the source code by modifying at least one of a "select all"
statement in
the source code, a derived column in the source code, a column alias in the
source
code, or a first query in the source code that is dependent on a second query
in the
source code; and generate an output of the parsed source code.
4
CA 2983510 2017-10-24
Attorney Docket No. 05793.3620-00000
[013] Consistent with the present embodiments, a method for code parsing is
also disclosed. The method may include various steps, for example, acquiring a
first
parameter identifying source code; acquiring the source code from the first
parameter;
parsing the source code by modifying at least one of a "select all" statement
in the
source code, a derived column in the source code, a column alias in the source
code, or
a first query in the source code that is dependent on a second query in the
source code;
and generating an output of the parsed source code.
[014] Aspects of the disclosed embodiments may also include a tangible, non-
transitory, computer-readable medium that stores software instructions that,
when
executed by one or more processors, are configured for and capable of
performing and
executing one or more of the methods, operations, and the like consistent with
the
disclosed embodiments.
[015] It is to be understood that both the foregoing general description and
the
following detailed description are exemplary and explanatory only, and are not
restrictive of the disclosed embodiments as claimed.
BRIEF DESCRIPTION OF THE DRAWINGS
[016] The accompanying drawings, which are incorporated in and constitute a
part of this specification, illustrate several embodiments and, together with
the
description, serve to explain the disclosed principles. In the drawings:
[017] FIG. 1 is a block diagram of an exemplary system environment for lineage
detection, consistent with disclosed embodiments.
[018] FIG. 2 is a block diagram of an exemplary lineage detector configured to
perform functions of the disclosed methods, consistent with disclosed
embodiments.
CA 2983510 2017-10-24
Attorney Docket No. 05793.3620-00000
[019] FIG. 3 is a flowchart of an exemplary lineage detection process,
consistent
with disclosed embodiments.
[020] FIG. 4 is a flowchart of an exemplary code parsing process, consistent
with
disclosed embodiments.
[021] FIG. 5 is an exemplary diagram of converted source code, consistent with
disclosed embodiments.
[022] FIG. 6 is an exemplary interface for viewing data lineage, consistent
with
disclosed embodiments.
DESCRIPTION OF THE EMBODIMENTS
[023] Generally, disclosed embodiments are directed to systems and techniques
for providing a computerized lineage detector that allows financial
institutions (such as
banks) to perform lineage detection. In some embodiments, the term "lineage
detection" may be used interchangeably with "determining the data lineage" or
"data
lineage detection." Either term may be interpreted as the process of
identifying the
hierarchy, discovering the location, and monitoring the changes of all data
elements of a
database component (e.g., calculation).
[024] Therefore, it follows that embodiments may be described as detecting the
lineage of database components (e.g., calculations, processes, metrics, IDEs,
and the
like). It should be understood that processes, metrics, and IDEs are related.
For
illustrative purposes only, consider the situation where a financial
institution needs to
determine a customer's account balance in an interest-bearing savings account.
This
process may require one or more metrics, such as the total amount of interest
earned
and an original balance. A metric may be constructed using various IDEs, such
as the
6
CA 2983510 2017-10-24
Attorney Docket No. 05793.3620-00000
principal amount, the interest rate, the time in years for the interest to
accumulate, the
number of times per year the interest is compounded, etc. And these IDEs may
contain
other data elements, such as an interest rate that is calculated based on
various factors.
Thus, it follows that a process may contain one or more metrics, and a metric
may
contain one or more IDEs.
[025] Further, embodiments are directed to "source code." Source code may
include instructions written in various programming languages, such as SQL TM,
PerlTM,
JavaScriptTM, Python TM, RUbYTM, etc. In reference to SQL, the term "query"
may be
used. A query is denoted as an instruction written in SQL that allows a user
to request
desired data and allows a DBMS to plan, optimize, and perform the physical
operations
necessary to produce the result desired by the user.
[026] Reference will now be made in detail to exemplary embodiments,
examples of which are illustrated in the accompanying drawings and disclosed
herein.
Wherever convenient, the same reference numbers will be used throughout the
drawings to refer to the same or like parts. For ease of discussion, the
present
disclosure may describe embodiments in the context of a financial service
provider
using a lineage detector to determine the data lineage of one or more
financial
processes, financial metrics, financial important data elements, or financial
data
elements. It is to be understood, however, that disclosed embodiments are not
limited
to this context. Rather, disclosed systems, methods, and techniques to provide
lineage
detection may be employed to apply to any type of lineage detection, and are
not limited
to the financial services industry.
7
CA 2983510 2017-10-24
Attorney Docket No. 05793.3620-00000
[027] FIG. 1 is a schematic diagram illustrating an exemplary system
environment for lineage detection, consistent with disclosed embodiments. In
particular,
FIG. 1 shows an exemplary system 100, revealing some technical aspects of the
present disclosure for achieving the intended results of the present
disclosure.
Referring to FIG. 1, system 100 may include one or more of client devices 102a-
102n, a
network 104, a local network 106, a lineage detector 108, data repositories
110, server
clusters 112a-112n, and a cloud service 114. The components and arrangements
shown in FIG. 1 are not intended to limit the disclosed embodiments, as the
components used to implement the disclosed processes and features may vary.
[028] As shown in FIG. 1, client device(s) 102 may be implemented using a
variety of different equipment, such as supercomputers, personal computers,
servers,
mainframes, mobile devices, smartphones, tablets, etc. In some embodiments,
client
devices 102 may be configured to receive input from a user, such as a request
to
determine the data lineage of a calculation in a body of source code. For
example,
client devices 102 may execute a web browser application to present a web page
through which a user may submit a request to parse the source code. Client
devices
102 may send the submitted request with parameters included (e.g.,
identification of the
body of source code desired to be analyzed and an identification of a specific
calculation that a user wants to target within the body of source code) to
lineage
detector 108 for processing. Client devices 102 may also be connected to a
network,
such as network 104. In some embodiments, client devices 102 may be connected
to a
local network, such as local network 106.
8
CA 2983510 2017-10-24
Attorney Docket No. 05793.3620-00000
[029] Network 104, in some embodiments, may comprise one or more
interconnected wired or wireless data networks that receive data from one
service or
device (e.g., lineage detector 108) and send it to other services or devices
(e.g., client
devices 102, data repositories 110, server clusters 112, and/or cloud service
114). For
example, network 104 may be implemented as the Internet, a wired Wide Area
Network
(WAN), a wired Local Area Network (LAN), a wireless LAN (e.g., IEEE 802.11,
Bluetooth, etc.), a wireless WAN (e.g., WiMAX), and the like. Each component
in
system 100 may communicate bidirectionally with other system 100 components
either
through network 104 or through one or more direct communication links (not
shown).
[030] Lineage detector 108 may be implemented for use with a variety of
equipment, such as supercomputers, personal computers, servers (e.g., server
clusters
112 and/or cloud service 114), mainframes, data repositories 110, one or more
client
devices 102, or the like. In some embodiments, lineage detector 108 may
comprise
hardware, software, and/or firmware modules. Lineage detector 108 may be
configured
to acquire parameters inputted by a user or by an external program, and
determine data
lineage of a calculation specified by the parameters. Lineage detector 108 may
then
analyze components of the source code, such as translating "select all"
statements
(e.g., SELECT * FROM DATABASENAME"), resolving orphaned columns, resolving
column aliases, and resolving references between multiple queries within the
source
code. Additionally or alternatively, lineage detector 108 may generate an
output of the
determined data lineage and display output of the determined data lineage.
[031] Consistent with the disclosed embodiments, data repositories 110 may be
configured to store information received, obtained, gathered, collected,
generated, or
9
CA 2983510 2017-10-24
Attorney Docket No. 05793.3620-00000
produced by components of system 100. In certain embodiments, for instance,
components of system 100 may receive or obtain information for storage over
network
104 (and/or local network 106). By way of example, data repositories 110 may
store
databases related to source code desired to be analyzed. In other aspects,
components of system 100 may store information in data repository 110 without
using
network 104 (e.g., via a direct connection). In some embodiments, components
of
system 100, including but not limited to lineage detector 108, may use
information
stored in data repository 110 for processes consistent with the disclosed
embodiments.
[032] Server clusters 112 may each be located in the same data center or in
different physical locations. Multiple server clusters 112 may be formed as a
grid to
share resources and workloads. Each server cluster 112 may include a plurality
of
linked nodes operating collaboratively to run various applications, software
modules,
analytical models, rule engines, etc. Each node may be implemented using a
variety of
different equipment, such as a supercomputer, personal computer, a server, a
mainframe, a mobile device, or the like. In some embodiments, the number of
servers
and/or server clusters 112 may be expanded or reduced based on workload.
[033] Cloud service 114 may include a physical and/or virtual storage system
associated with cloud storage for storing data and providing access to data
via a public
network such as the Internet. Cloud service 114 may include cloud services
such as
those offered by, for example, Amazon , Apple , Cisco , Citrix , IBM , Joyent
,
Google , Microsoft , Rackspace , Salesforce.com , and Verizonefferremark , or
other
types of cloud services accessible via network 104. In some embodiments, cloud
service 114 comprises multiple computer systems spanning multiple locations
and
CA 2983510 2017-10-24
Attorney Docket No. 05793.3620-00000
having multiple databases or multiple geographic locations associated with a
single or
multiple cloud storage service(s). As used herein, cloud service 114 refers to
physical
and virtual infrastructure associated with a single cloud storage service, and
may
manage and/or store data associated with lineage detection.
[034] FIG. 2 is a diagram of an exemplary lineage detector configured to
perform
functions of the disclosed methods, consistent with disclosed embodiments. As
shown,
lineage detector 108 may include at least one processor 260, at least one
input/output
("I/O") device 270, and memory 280 storing data, programs 282 (e.g., operating
system
288), and lineage detection module(s) 292. As noted above, lineage detector
108 may
be implemented in a single server or in a distributed computer system
including multiple
servers or computers (e.g., server clusters 112 and/or cloud service 114) that
interoperate to perform one or more of the processes and functionalities
associated with
the disclosed embodiments. In some embodiments, lineage detector 108 is
specially
configured with hardware and/or software modules for performing functions of
disclosed
methods. The components of lineage detector 108 may be implemented as
specialized
circuitry integrated within processor 260 or in communication with processor
260, and/or
as specialized software stored in memory 280 executable by processor 260.
[035] Processor 260 may be implemented as one or more known or custom
processing devices designed to perform functions of the disclosed methods,
such as
single- or multiple- core processors capable of executing parallel processes
simultaneously to allow lineage detector 108 to execute multiple processes
simultaneously. For example, processor 260 may be configured with virtual
processing
technologies. Processor 260 may implement virtual machine technologies,
including a
11
CA 2983510 2017-10-24
Attorney Docket No. 05793.3620-00000
Java virtual machine, or other known technologies to provide the ability to
execute,
control, run, manipulate, store, etc. multiple software processes,
applications, programs,
etc. One of ordinary skill in the art would understand that other types of
processor
arrangements could be implemented that provide for the capabilities disclosed
herein.
[036] I/O device 270 may comprise one or more interfaces for receiving input
signals from other devices and for providing output signals to other devices
to allow
data to be received and/or transmitted by lineage detector 108. I/O device 270
may
also include interface components that display information and/or provide
interfaces to
one or more input devices, such as one or more keyboards, mouse devices, and
the
like, to enable lineage detector 108 to receive input from a user (not shown).
[037] Memory 280 may include instructions to enable processor 260 to execute
programs 282, such as operating system 288, server applications, network
communication processes, and any other type of application or software known
to be
available on computer systems. Alternatively or additionally, instructions may
be stored
in remote storage (not shown) in communication with lineage detector 108, such
as one
or more database or memory modules accessible over network 104. The internal
database and external storage may be implemented in volatile or non-volatile,
magnetic,
semiconductor, tape, optical, removable, non-removable, or other type of
storage device
or tangible (i.e., non-transitory) computer-readable medium.
[038] The remote storage may be configured to store information (e.g.,
structured, semi-structured, and/or unstructured data) and may be accessed
and/or
managed by lineage detector 108. By way of example, the remote storage may be
implemented as databases, such as Microsoft SQL databases, SharePointTM
12
CA 2983510 2017-10-24
Attorney Docket No. 05793.3620-00000
databases, Oracle databases, Sybase TM databases, or other databases. Systems
and
methods consistent with disclosed embodiments, however, are not limited to
separate
databases or even to the use of a database.
[039] In one embodiment, lineage detector 108 may include memory 280 that
includes instructions that, when executed by processor 260, perform one or
more
processes consistent with the functionalities disclosed herein. Methods,
systems, and
articles of manufacture consistent with disclosed embodiments are not limited
to
separate programs or computers configured to perform dedicated tasks. For
example,
lineage detector 108 may include memory 280 that may include one or more
programs 282 and/or lineage detection module 292 to perform one or more
functions of
the disclosed embodiments. Moreover, processor 260 may execute one or more
programs located remotely from system 100. For example, lineage detector 108
may
access one or more remote programs, that, when executed, perform functions
related to
disclosed embodiments.
[040] Programs 282 may also include one or more machine learning, trending,
and/or pattern recognition applications (not shown) that cause processor 260
to execute
one or more processes related to lineage detection. For example, the machine
learning, trending, and/or pattern recognition may provide, modify, or suggest
input
variables associated with one or more other programs 282.
[041] Lineage detection module 292 may be stored in memory 280 and executed
by processors 260 to implement one or more parts of the lineage detector 108.
Specifically, lineage detection module 292 may implement one or more parts of
lineage
detection process 300, discussed below. In some embodiments, lineage detection
13
CA 2983510 2017-10-24
Attorney Docket No. 05793.3620-00000
module 292 may also utilize third-party software to provide additional
functionality to
lineage detector 108. For example, lineage detection module 292 may utilize a
third-party parser, such as ZQLTM, JSqlParserTM, or General SQL ParserTM, to
perform
rudimentary parsing of source code. In other embodiments, lineage detection
module
292 may provide this functionality without any assistance from third-party
software.
[042] FIG. 3 is a flowchart of an exemplary lineage detection process 300 that
may be performed by lineage detector 108, consistent with disclosed
embodiments. In
the following description, reference is made to certain components of FIG. 3
for
purposes of illustration. It should be appreciated, however, that other
implementations
are possible and that components other than those illustrated above in FIG. 2
with
respect to lineage detector 108 may be utilized to implement the exemplary
method of
FIG. 3.
[043] At Step 310, lineage detector 108 may initially acquire one or more
parameters supplied as input. These input parameters may include one or more
calculation parameters specifying the calculations within the source code body
desired
by a user to be analyzed, the calculation parameters indicating (i.e.,
pointing to,
referencing, or being) one or more calculations. The indicated calculations
may also be
referred to as target calculations. A calculation may in turn reference a
process, metric,
IDE, or the like, as defined above.
[044] Lineage detector 108 may also acquire one or more source code
parameters that identify or specify the location of the body of source code to
be
analyzed. Lineage detector 108 may also acquire other parameters that specify
a
particular part of a calculation (e.g., the numerator in a metric that
includes division), a
14
CA 2983510 2017-10-24
Attorney Docket No. 05793.3620-00000
lineage focus time (e.g., the specific time that a process was ran), a
particular entity or
characteristic associated with a calculation (e.g., a particular user or type
of user
associated with determining the data lineage for a calculation), a detection
level (i.e., a
higher or lower hierarchical degree from an initial calculation), etc.
[045] Notably, acquiring the parameters above may occur in several, different
ways. For example, lineage detector 108 may acquire the parameters by
receiving a
request from a user. In this aspect, a user using client device 102 may send a
request
containing parameters to lineage detector 108 in order to determine the
lineage of data.
The user could send the request containing the parameters manually or
programmatically through one or more portals (e.g., websites, command
terminals,
batch processes, etc.) that are capable of electronically communicating with
lineage
detector 108. In other embodiments, the request sent by the user may not
contain the
parameters. Instead, the request sent by the user may contain a network
location
where lineage detector 108 could retrieve or acquire the necessary parameters.
[046] Lineage detector 108, as another example, may also acquire the
parameters by requesting them from an application program interface (API). In
the
alternative, lineage detector 108 may acquire the parameters by receiving a
request
from the API. Yet, in other embodiments, lineage detector 108 may acquire a
parameter by retrieving it from a location specified by another parameter or
stored in
memory 280 or on another storage device, such as a storage device located on
network
104 or on local network 106. These files may contain actual parameters,
network
locations pointing to the parameters, or both. These files may also be static
or dynamic.
CA 2983510 2017-10-24
Attorney Docket No. 05793.3620-00000
Lineage detector may also acquire the parameters from databases, memory, or
the like
coupled to network 104 and local network 106.
[047] It should be understood that lineage detector 108 may acquire the
necessary parameters by utilizing a technique disclosed in one of the examples
discussed above or in a combination of the techniques disclosed in the
examples
above. Regardless of the way the parameters are acquired, lineage detector 108
may
acquire updated parameters in real-time or on demand.
[048] At Step 320, after acquiring the parameters, lineage detector 108 may
parse source code. As noted above, the source code to be analyzed may include
non-
programming languages, programming languages, or both. With regards to
programming languages, this source code may include various known programming
language, such as SQLTM, PerlTM, JavaScriptTM, Python TM , Ruby TM, etc.
[049] Lineage detector 108 may have the capability to ignore or filter out
portions
of the source code not useful to lineage detection. For example, if a source
code
contains both RubyTm and SQL instructions, lineage detector 108 may parse only
the
SQL instructions while ignoring or filtering out the remaining Ruby TM
instructions.
Ultimately, lineage detector 108 will parse source code at least in the form
of SQL
because it is useful to lineage detection. Although other database management
languages, such as ScalaQLTM, ActiveRecordTM, SqlStatementTM, Haskell DBTM,
may
also be useful to lineage detection, for simplicity, any reference to source
code below
will be understood only to include SQL.
[050] To parse source code, lineage detector 108 may analyze each character,
word, line, statement, symbol, etc. in the entire remaining body of source
code one or
16
CA 2983510 2017-10-24
Attorney Docket No. 05793.3620-00000
more times, and may conduct this analysis recursively. Additionally, lineage
detector
108 may also execute one or more parts of the source code in a virtual
environment to
verify the operability of those parts of the source code. For example, lineage
detector
108 may verify that the source code has the correct syntax by running the
source code
in a virtual environment containing a compiler.
[051] During parsing, lineage detector 108 may edit the source code in memory.
For example, lineage detector 108 may create, read, update, or delete any
words, lines,
statements, symbols, and likewise in the source code at any time.
[052] In some embodiments, lineage detector 108 may make new or modified
source code files. These new or modified files may contain any original source
code of
the acquired source code or only the original source code essential to lineage
detection
at any time. Regarding each modification of source code, lineage detector 108
may
generate or display output, consistent with Steps 340 and 350 below.
[053] Ultimately, at Step 320, to parse code, lineage detector 108 may utilize
various specialized techniques to parse source code. It should be appreciated
that
these specialized techniques overcome the limitations of third-party software
applications, as described above, to detect the data lineage of calculations
in advanced
database systems.
[054] Turning to Fig. 4, a few of these specialized techniques are
demonstrated
including: translating "select all" statements (at Step 410), resolving
orphaned columns
(at Step 420), resolving column aliases (at Step 430), resolving references
between
multiple dependent queries (at Step 440), or performing other techniques (at
Step 450).
These techniques are described below as illustrative examples, but lineage
detector
17
CA 2983510 2017-10-24
Attorney Docket No. 05793.3620-00000
108 may utilize other equivalent or varied techniques in addition to those
described
below.
[055] In some embodiments, at Step 410, lineage detector 108 may translate one
or more "SELECT *" ("select all") statements in the source code. A "select
all"
statement translates all of the results in one or more tables of one or more
databases.
"Select all" statements are commonly used, but third-party software
applications do not
have the ability to accurately identify all the columns for particular tables
in a database
from source code. The inability of third-party software applications to
translate these
statements leads to poor results regarding lineage detection. Lineage detector
108
overcomes this limitation of these third-party applications.
[056] For example, using the statement illustrated below, lineage detector 108
may translate or modify "select all" statements to include all of the columns
in a table
identified as TABLENAME, which is located in a database identified as
DATBASENAME.
SELECT* FROM DATABASENAME.TABLENAME
[057] To accomplish this, lineage detector 108 may acquire or collect all the
column names in TABLENAME. To accomplish this, in some embodiments, lineage
detector may ask or query the database using SQL to retrieve all column names
of
TABLENAME. In other embodiments, lineage detector 108 may build a list, array,
map,
or the like of all the column names of TABLENAME while parsing through the
source
code. Lineage detector 108, for example, may store a reference to each column
(e.g., a
column name) of TABLENAME in one or more programming structures (e.g., a list,
18
CA 2983510 2017-10-24
Attorney Docket No. 05793.3620-00000
array, map, variable(s), or the like) in memory 280 until every column name of
TABLENAME is included in the programming structure(s). Further, lineage
detector 108
may translate or modify the "select all" statements in the source code to
identify all of
the columns of TABLENAME in DATABASENAME within the programming structure(s).
It should be understood that, although the previous example, for simplicity,
involves only
selecting all the columns of a single table in a database, lineage detector
108, using the
same techniques, can select all the columns in multiples tables within one or
more
databases.
[058] While parsing source code, at Step 420, lineage detector 108 may resolve
one or more orphaned columns in the source code. Although orphaned columns
appear to be normal database table columns to a casual observer, they are
actually
derived from other columns and are held in temporary memory rather than stored
in the
actual database. In view of the example statement below, a programmer may take
an
actual column named "FEET," referred to as the base column, in a database
table
named "MEASUREMENTS," and create an orphaned column named "YARDS" by
dividing each value in FEET by 3. Using SQL, a programmer may define this
relationship between the actual column and the orphaned as:
FEET / 3 AS YARDS
[059] However, if a programmer were to search for the YARDS column in the
MEASUREMENTS table, the programmer would not be able to find the YARDS column
because it would not be stored in the actual database as belonging to the
MEASUREMENTS table, It follows that, while orphan columns are dependent on a
19
CA 2983510 2017-10-24
Attorney Docket No. 05793.3620-00000
base column, they are not stored in the actual database. Because orphaned
columns
appear to be actual columns stored in the database, third-party software
applications
may fail to detect orphaned columns.
[060] In some embodiments, lineage detector 108 may resolve orphaned
columns in the source code by first identifying the corresponding base columns
in the
source code. For example, lineage detector 108 can identify base columns by
performing a search for the SQL keyword "AS" in the source code. Lineage
detector
108 may identify characters to the left of the keyword "AS" to include the
actual column
and characters right of the keyword "AS" to define the orphaned column.
Lineage
detector 108 may then filter out any operations, such as "I 3", on a set of
characters or
word, such as "FEET," to identify the base column. Lineage detector 108 may
also filter
out other SQL operations to determine the base column.
[061] In some embodiments, lineage detector 108 may modify any column name
derived from each base column in the source code to reflect the derived
columns'
dependency on the base columns. For example, lineage detector 108 may modify
the
derived columns in the source code to reflect base column names instead of the
derived
column names. Lineage detector 108 may recursively process step 420 until it
successfully reconstructs the column lineage of all of the derived columns in
the source
code.
[062] Moreover, in some embodiments, lineage detector 108 may resolve column
aliases in the source code (Step 430). Column aliases are a tool utilized by
programmers to substitute a more readable column name, that is, an "alias" for
the
actual name of a column in a database table. Similar to orphaned columns,
third-party
CA 2983510 2017-10-24
Attorney Docket No. 05793.3620-00000
software applications may fail to distinguish column aliases from actual
column names
in a database table.
[063] Lineage detector 108 may resolve these column aliases through recursion,
by first identifying a column containing an alias and then modifying every
reference in
the source code that refers to the column alias to reflect the actual column
name of the
column. For example, lineage detector 108, similar to identifying orphaned
columns,
can identify the actual name of a column by performing a search for the SQL
keyword
"AS" in the source code. Lineage detector 108 may identify characters to the
left of the
keyword "AS" to include the actual name of the column and characters right of
the
keyword "AS" to define the column's alias. Lineage detector 108 may also
filter out
other SQL operations to determine the base column, such as any mathematical
operations, operations on characters, etc. Lineage detector 108 may
recursively
process step 430 until it resolves all of the column aliases in the source
code.
[064] At Step 440, lineage detector 108 may resolve references between
multiple
queries or statements in the source code. For example, source code might
include a
first query that is dependent on a second query. Therefore, it follows that in
order to
properly parse the first query, the second query would need to be parsed
first.
Third-party software applications may not have the ability understand,
decipher, and
parse statements that are dependent upon each other.
[065] On the other hand, lineage detector 108 may resolve references between
multiple queries in the source code. In some embodiments, lineage detector 108
may
require the use of Steps 410-430 or 450-460, as described above and below,
and, in
other embodiments, lineage detector 108 may employ other techniques.
21
CA 2983510 2017-10-24
Attorney Docket No. 05793.3620-00000
[066] Regardless, to resolve references between queries, lineage detector 108
may parse each individual or independent query in the source code and place
the
elements of the independent query into a temporary programming structure, such
as a
tree having one or more nodes. Once each query is parsed into a separate tree,
lineage detector 108 may reference, or link, corresponding nodes in each tree.
[067] Additionally, in some embodiments, lineage detector 108 may perform
other techniques (at Step 450). Lineage detector 108 may make the source code
more
readable by, for example, applying a predefined format to the source code to
make the
source code appear "cleaner" to a programmer. As another example, lineage
detector
may detect syntax errors in the source code that might prevent the source code
from
executing, and display or send a notification to a user. The notification may
also include
the line number where the syntax error was found, along with the statement or
query
containing the error.
[068] Lineage detector 108 may target potentially harmful SQL characters and
either delete, highlight, or modify (i.e., "escape") them, and display or send
a notification
identifying the potential harmful SQL characters. The notification may specify
the line
number in the source code where the harmful character was found along, with
the
statement or query containing the harmful character.
[069] In some embodiments, at Step 460, lineage detector 108 may also utilize
third-party software, such as ZQLTM, JSqlParserTM, or General SQL ParserTM, or
the
like, to perform one or more of these techniques. In these embodiments,
lineage
detector 108 may perform techniques to prepare the source code before
utilizing the
third-party software in order to obtain accurate results. For example, lineage
detector
22
CA 2983510 2017-10-24
Attorney Docket No. 05793.3620-00000
108 may convert or process strings, numeric data, or SQL functions in the
source code
to comply with requirements of the third party software. As part of this
conversion
process, lineage detector 108 may, for example, take out special characters
denoting
comments in the source code, replace timestamps in the source code, modify
SQL's
substring function, and/or the like. Lineage detector 108 may also perform any
of steps
410-450 to prepare the source code.
[070] Returning now to Fig. 3, after parsing the source code, at Step 330,
lineage
detector 108 may determine data lineage of calculations specified by input
parameters
to data lineage detector 108. Specifically, lineage detector 108 may perform
this
determination by converting the parsed source code into a temporary
programming
structure, such as a tree having one or more branches with one or more nodes
N.
Lineage detector 108 may then determine the data lineage of a specified
calculation by
"walking down" each branch of the tree that has relevant data elements. As an
example, for illustrative purposes only, FIG. 5 is provided as an exemplary
diagram of
converted source code. It will be assumed that lineage detector 108 has
acquired a
calculation parameter of parameter "p2" and a source code parameter of source
code
that, when parsed and converted into a tree structure, may be represented by
tree
structure 500.
[071] As illustrated, top nodes 510 of the tree consist of multiple processing
nodes (Np1, Np2, and Np3). Each top node 510 is connected to (e.g., used by)
one or
more metric nodes 520 (Nmi, Nm2, Nm3, and Nm4). Next, each metric node 520 is
connected to one or more respective data element or IDE nodes 530 (Ndi, Nd2,
Nd3, Nd4,
Nd5, and Nd6). Data element nodes 530 are further connected to other data
element
23
CA 2983510 2017-10-24
Attorney Docket No. 05793.3620-00000
nodes 540 (Nd7, Ndg, Ndg, and Kilo), and so on, until bottom nodes, that is,
nodes that do
not have any other child nodes, are constructed. In this illustration, Ndl,
Ndg, Nd7, Nd8,
Ndg, and Ndip constitute bottom nodes 540.
[072] To determine the data lineage of calculation parameter p2, lineage
detector
108 attempts to find all nodes that descend from, that is, are child nodes of
calculation
parameter, "p2." In the example of Fig. 5, lineage detector 108 searches for
calculation
parameter "p2" among top nodes 510. Accordingly, lineage detector 108 locates
node
Np2 containing calculation parameter "p2."
[073] Following this, lineage detector 108 determines the data lineage of
calculation parameter "p2" by acquiring or collecting all of the child nodes
of node Np2,
including the content of the child nodes. In this example, lineage detector
may first
"walk down" to nodes Nm2 and Nm3 of metric nodes 520, which are child nodes of
process node Np2. Lineage detector 108 then continues determining the data
lineage by
identifying child nodes of Nm2 and Nm3, namely, data nodes Nd2 and Nd3; and
Nd4, and
Ndg, respectively. The method continues until all bottom nodes contributing to
process
node Np2 are identified, in this example Nd7, Nd8, Ndg, and Ndio. All of these
nodes, Nm2
and Nm3; Nd2, Nd3, Nd4. and Ndg; and Nd7, Nd8, Ndg, and Nd10, belong to the
data lineage of
p2. All of the nodes traversed by lineage detector 108 and their relationship
to each
other represent the data lineage of the calculation parameter p2.
[074] In some embodiments, the calculation parameter may not correspond to
any node among top nodes 510. In such a case, lineage detector 108 may
traverse the
tree until it finds a node corresponding to the desired calculation parameter.
In other
embodiments, lineage detector 108 may traverse the tree from the bottom up,
starting
24
CA 2983510 2017-10-24
Attorney Docket No. 05793.3620-00000
with nodes 540. It should be understood that FIG. 5 serves as an illustration
and other
techniques such as breadth first search, depth first search, and/or different
programming structures, such as linked-list, maps, etc., could be used to
determine
data lineage.
[075] Referring back to FIG. 3, at Step 340, lineage detector 108 may generate
one or more outputs. For example, lineage detector 108 may generate an output
for the
determined data lineage as a listing all child nodes of any calculation
parameters
determined at Step 330. These outputs may be generated by creating and storing
a file.
In some embodiments, lineage detector 108 may generate an output consisting of
a file
of Extensible Markup Language (XML) code to represent the data lineage. In
other
embodiments, lineage detector 108 may generate objects in an object-oriented
programming and utilize one or more Extensible Stylesheet Language
Transformations
(XSLT) to transform the object into an XML file.
[076] Lineage detector 108 could also generate an output using other
programming languages or in other ways. For example, lineage detector 108 may
generate data lineage output by using a third party application, such as
General SQL
ParserTM. Also, it should also be understood that lineage detector 108 is not
limited to
generating outputs of only data lineage. Lineage detector 108 may additionally
generate one or more output of modified source code files, visual
representations of the
data lineage, processing logs, error logs, or the like.
[077] At Step 350, lineage detector 108 may display the outputs of step 350.
To
display an output, in some embodiments, lineage detector 108 may automatically
cause
one or more of client devices 102 to display an interface for viewing data
lineage. In
CA 2983510 2017-10-24
Attorney Docket No. 05793.3620-00000
other embodiments, a user may upload one or more files of the output generated
in
Step 340, as illustrated in FIG. 6. Once uploaded, lineage detector 108 may
then cause
one or more client devices 102 to display an interface for viewing data
lineage.
[078] Lineage detector 108 may utilize various programming languages, such as
(Hypertext Markup Language (HTML), Cascading Style Sheets (CSS), JavaScript,
jQuery TM, etc.), to cause one or more of client devices 102 to display an
interface and
asynchronously modify the interface in real-time. Lineage detector 108 may
also use
one or more third-party application, such as Shiny by RStudio, to aid in the
displaying of
output.
[079] FIG. 6 is an exemplary interface 600 for interacting with data lineage
detector 108, consistent with disclosed embodiments. Interface 600 may include
input
fields 602 (text fields, drop-down menus, checkboxes, image upload areas,
etc.) for
accepting one or more output files generated at Step 340 of lineage detection
process
300.
[080] In some embodiments, lineage detector 108 may access a network location
to obtain an output file generated at Step 340 for display on interface 600.
Interface 600
may also contain one or more viewing options, such as tabs 604a, 604b, for
viewing the
output in various ways. For example, tab 604a comprises a data lineage section
showing the data lineage output in grid form, and tab 604b comprises a summary
section showing a summary in the form of FIG. 5. Viewing options may be
selected in
ways other than tabs, such as an accordion-type section, etc.
[081] In some embodiments, interface 600's data lineage tab 604a may include
grid 606. Grid 606 may display the entire data lineage of the source code
parsed in
26
CA 2983510 2017-10-24
Attorney Docket No. 05793.3620-00000
step 320 or may display the data lineage for only certain target calculation
parameters
acquired in step 310.
[082] Grid 606 has columns 608a-n for each entry of data lineage of a
calculation
parameter referencing a parent location or the location of a parent data
element (e.g.,
parent database 608a, parent table 608b, parent column 608c) and child
location or the
location of a child data element (e.g., child database 608d, child table 608e,
and child
column 6080. Along with these columns, interface 600 may also include, as an
illustrative example, rows 610a-n in table 606. Rows 610a-n and columns 608a-n
may
represent only the data lineage of one or more calculation parameters acquired
in step
310 or the entire data lineage of the source code parsed in step 320.
[083] Row 610a, as illustrated, lists the same target location (i.e., parent
location)
and source location (i.e., child location). As shown, row 610 lists a parent
and child
both located at database DB1, table Table1, and column Column1. It should be
understood that if a row lists the same parent location and child location,
then that row
represents either a top node 510 or bottom 540 as exemplified by Fig. 5 and
described
above.
[084] Row 610b, on the other hand, has a parent located at database DB1, table
Table1, and column Column1 and a child located at database DB2, table Table2,
and
column Column2. Also, row 610c has a parent located at database DB1, table
Table1,
and column Column1 and a child located at database DB3, table Table3, and
column
Column3. It should be understood that rows 610b and 610c define the child
elements of
the parent defined by row 610a.
27
CA 2983510 2017-10-24
Attorney Docket No. 05793.3620-00000
[085] Row 610e, like row 610a, has the same parent and child locations.
Therefore, it should be understood that row 610e is a bottom node (e.g.,
illustrated in
Fig. 5 as bottom nodes 520) because it depends from another row or node (610a)
but
refers to itself (i.e., has the same parent and child locations) in the
database. Notice
that the parent defined by 610a, however, depends from no other rows or nodes,
so as
illustrated in Fig. 5, it is a top node because it refers to itself but does
not depend on any
other rows or nodes.
[086] Using the same techniques as described above in reference to 610a-610d,
it is understood that rows 610f and 610e define child nodes that depend from a
parent
located at database DB3, table Table3, and column Column3. It is also
understood that
this parent located at database DB3, table Table3, and column Column3 is a
child of the
parent node defined by row 610a and located at database DB1, table Table1, and
column Column1. The rest of table 606 may be understood using these same
techniques. However, the relationships described by table 606 are not limited
to the
ones illustrated nor is the way the relationships are displayed limited to the
ones
illustrated. Other techniques may be used to visually display data
illustrative of data
lineage.
[087] Interface 600 may also include one or more table controls 612 that
change
the number of entries displayed, the type of entries displayed, the type of
columns
displayed, etc. Interface 600 may be visually depicted in a number of
arrangements or
the like.
[088] Descriptions of the disclosed embodiments are not exhaustive and are not
limited to the precise forms or embodiments disclosed. Modifications and
adaptations
28
CA 2983510 2017-10-24
=
Attorney Docket No. 05793.3620-00000
of the embodiments will be apparent from consideration of the specification
and practice
of the disclosed embodiments. For example, the described implementations
include
hardware, firmware, and software, but systems and techniques consistent with
the
present disclosure may be implemented as hardware alone. Additionally, the
disclosed
embodiments are not limited to the examples discussed herein.
[089] Computer programs based on the written description and methods of this
specification are within the skill of a software developer. The various
programs or
program modules may be created using a variety of programming techniques. For
example, program sections or program modules may be designed in or by means of
Java, C, C++, assembly language, or any such programming languages. One or
more
of such software sections or modules may be integrated into a computer system,
non-
transitory computer-readable media, or existing communications software.
[090] Moreover, while illustrative embodiments have been described herein, the
scope includes any and all embodiments having equivalent elements,
modifications,
omissions, combinations (e.g., of aspects across various embodiments),
adaptations or
alterations based on the present disclosure. The elements in the claims are to
be
interpreted broadly based on the language employed in the claims and not
limited to
examples described in the present specification or during the prosecution of
the
application; such examples are to be construed as non-exclusive. Further, the
steps of
the disclosed methods may be modified in any manner, including by reordering
steps or
inserting or deleting steps. It is intended, therefore, that the specification
and examples
be considered as exemplary only, with the true scope and spirit being
indicated by the
following claims and their full scope of equivalents.
29
CA 2983510 2017-10-24
