Data lineage data type

[0002] This application is related by subject matter to the inventions disclosed in commonly assigned pending U.S. patent application Ser. No. 09/212,218, filed on Dec. 16, 1998, entitled “DATA LINEAGE” and pending U.S. patent application Ser. No. 09/213,069, filed on Dec. 16, 1998, entitled “DATA PUMP FOR DATABASE.”

[0003] The present invention relates generally to database systems, and more particularly to a system for maintaining lineage information for data stored in a database.

[0004] A relational database is a collection of related data that is organized in related two-dimensional tables of columns and rows wherein information can be derived by performing set operations on the tables, such as join, sort, merge, and so on. The data stored in a relational database is typically accessed by way of a user-defined query that is constructed in a query language such as Structured Query Language (“SQL”). A SQL query is non-procedural in that it specifies the objective or desired result of the query in a language meaningful to a user but does not define the steps to be performed, or the order of the steps in order to accomplish the query.

[0005] Moreover, very large conventional database systems provide a storehouse for data generated from a variety of locations and applications (often referred to as data warehouses or data marts). The quality and reliability of the storehouse is greatly effected by the quality and reliability of its underlying data. Because the data can originate from a variety of sources, the quality and reliability of data will often depend on the quality and reliability of the source. Moreover, the matter is further complicated because individual rows of data within a single table can originate from different sources.

[0006] Currently, if the data in a database is questionable, there is no easy way to track the history of the data to determine where it originate or how it may have been changed. As such, it would be advantageous to users of a database to have tools that allow the users to trace aspects of the history (i.e., where the data originated and how the data has been transformed) of the data in a database.

[0007] The task of tracing aspects of the history of data in a database is further complicated in enterprise-wide databases (such as data warehouses) where data may flow into the database from direct as well as indirect data sources, (i.e., the data may have been collected from another database that itself directly or indirectly derived the data). In other words, the data may have made multiple “hops” before reaching the destination database of interest.

[0008] As such, there is a need for providing method and apparatus for determining information about the history (i.e., lineage) of data contained within a database.

[0009] Briefly, the present invention is directed toward database technology that provides users with powerful tools necessary to manage and exploit data. The present invention provides a system and method for tracking the lineage of data within database tables. According to an aspect of the invention, data within the tables are tracked by attaching lineage information to the data, preferably, by adding a lineage identifier to each row in a table. Data that share a common lineage can be identified by virtue of sharing a common lineage identifier.

[0010] The lineage identifier can then be used to trace the source of the data, i.e., data having a common identifier share a common history. Additionally, the lineage identifier can provide details about transformations undergone by the data. For example, the lineage identifier can act as a pointer to a detailed history files of operations that were performed on the data to transform it into its current form. Preferably, the lineage identifier tracks program modules as well as specific versions of the program modules that transformed the particular data under consideration.

[0011] As a result of the data lineage mechanism, users can trace the history data in a table, even when that data has made several hops among databases, where the data has undergone one or more transformations, or where the transforming program modules have themselves under gone revision. This provides users with a powerful mechanism to have higher confidence in the quality and reliability of data in a database and to quickly trace and correct errors in the data.

[0012] Preferably, the lineage data type is an identifier that is universally unique and is optimized to provide little impact on the performance of the data base. For example, by providing a sufficient size identifier to ensure its uniqueness while minimizing storage size. More preferably, the data lineage data type is a sixteen-byte number.

[0013] Other features of the invention are further apparent from the following detailed description of presently preferred exemplary embodiments of the invention taken in conjunction with the accompanying drawings, of which:

[0014] FIG. 1 is a block diagram representing a computer system in which aspects of the present invention may be incorporated;

[0015] FIG. 2A is schematic diagram representing a network in which aspects of the present invention may be incorporated;

[0016] FIG. 2B is a diagram representing tables in an exemplary database;

[0017] FIG. 3 is an architecture of an exemplary database management system;

[0018] FIG. 4 is a network of database systems depicting the logical flow of data;

[0019] FIG. 5 is a diagram showing the transformation of data as it moves between databases;

[0020] FIG. 6 is a diagram of the binding of data lineage information to rows of data in a database;

[0021] FIG. 7 is a functional diagram of a data transformation package;

[0022] FIGS. 8A-8C are depictions of a graphical interface for attaching data lineage information to data imported into a database;

[0023] FIG. 9 is an ActiveX® script for importing data into a database while adding data lineage information;

[0024] FIG. 10 is a data pump architecture for importing data into a database;

[0025] FIG. 11 illustrates the generation of long and short data lineage values; and

[0026] FIG. 12 is a window showing data lineage information attached to a row of data.

[0027] The present invention provides a database management system that provides for tracking and tracing the lineage of data stored in a database. The present exemplary embodiments described herein describe the invention in connection with row level lineage. However, the invention is by no means limited to row level lineage, as the invention could be applied on a column basis or a table basis as well.

[0028] 1. A Computer Environment

[0029] FIG. 1 and the following discussion are intended to provide a brief general description of a suitable computing environment in which the invention may be implemented. Although not required, the invention will be described in the general context of computer-executable instructions, such as program modules, being executed by a computer, such as a workstation or server. Generally, program modules include routines, programs, objects, components, data structures and the like that perform particular tasks or implement particular abstract data types. Moreover, those skilled in the art will appreciate that the invention may be practiced with other computer system configurations, including hand-held devices, multi-processor systems, microprocessor-based or programmable consumer electronics, network PCS, minicomputers, mainframe computers and the like. The invention may also be practiced in distributed computing environments where tasks are performed by remote processing devices that are linked through a communications network. In a distributed computing environment, program modules may be located in both local and remote memory storage devices.

[0030] With reference to FIG. 1, an exemplary system for implementing the invention includes a general purpose computing device in the form of a conventional personal computer 20 or the like, including a processing unit 21, a system memory 22, and a system bus 23 that couples various system components including the system memory to the processing unit 21. The system bus 23 may be any of several types of bus structures including a memory bus or memory controller, a peripheral bus, and a local bus using any of a variety of bus architectures. The system memory includes read-only memory (ROM) 24 and random access memory (RAM) 25. A basic input/output system 26 (BIOS), containing the basic routines that help to transfer information between elements within the personal computer 20, such as during start-up, is stored in ROM 24. The personal computer 20 may further include a hard disk drive 27 for reading from and writing to a hard disk, not shown, a magnetic disk drive 28 for reading from or writing to a removable magnetic disk 29, and an optical disk drive 30 for reading from or writing to a removable optical disk 31 such as a CD-ROM or other optical media. The hard disk drive 27, magnetic disk drive 28, and optical disk drive 30 are connected to the system bus 23 by a hard disk drive interface 32, a magnetic disk drive interface 33, and an optical drive interface 34, respectively. The drives and their associated computer-readable media provide non-volatile storage of computer readable instructions, data structures, program modules and other data for the personal computer 20. Although the exemplary environment described herein employs a hard disk, a removable magnetic disk 29 and a removable optical disk 31, it should be appreciated by those skilled in the art that other types of computer readable media which can store data that is accessible by a computer, such as magnetic cassettes, flash memory cards, digital video disks, Bernoulli cartridges, random access memories (RAMs), read-only memories (ROMs) and the like may also be used in the exemplary operating environment. Further, as used herein, the term “computer readable medium” includes one or more instances of a media type (e.g., one or more floppy disks, one or more CD-ROMs, etc.).

[0031] A number of program modules may be stored on the hard disk, magnetic disk 29, optical disk 31, ROM 24 or RAM 25, including an operating system 35, one or more application programs 36, other program modules 37 and program data 38. A user may enter commands and information into the personal computer 20 through input devices such as a keyboard 40 and pointing device 42. Other input devices (not shown) may include a microphone, joystick, game pad, satellite disk, scanner or the like. These and other input devices are often connected to the processing unit 21 through a serial port interface 46 that is coupled to the system bus, but may be connected by other interfaces, such as a parallel port, game port or universal serial bus (USB). A monitor 47 or other type of display device is also connected to the system bus 23 via an interface, such as a video adapter 48. In addition to the monitor 47, personal computers typically include other peripheral output devices (not shown), such as speakers and printers.

[0032] The personal computer 20 may operate in a networked environment using logical connections to one or more remote computers, such as a remote computer 49. The remote computer 49 may be another personal computer, a server, a router, a network PC, a peer device or other common network node, and typically includes many or all of the elements described above relative to the personal computer 20, although only a memory storage device 50 has been illustrated in FIG. 1. The logical connections depicted in FIG. 1 include a local area network (LAN) 51 and a wide area network (WAN) 52. Such networking environments are commonplace in offices, enterprise-wide computer networks, Intranets and the Internet.

[0033] When used in a LAN networking environment, the personal computer 20 is connected to the local network 51 through a network interface or adapter 53. When used in a WAN networking environment, the personal computer 20 typically includes a modem 54 or other means for establishing communications over the wide area network 52, such as the Internet. The modem 54, which may be internal or external, is connected to the system bus 23 via the serial port interface 46. In a networked environment, program modules depicted relative to the personal computer 20, or portions thereof, may be stored in the remote memory storage device. It will be appreciated that the network connections shown are exemplary and other means of establishing a communications link between the computers may be used.

[0034] 2. A Network Environment

[0035] FIG. 2 illustrates an exemplary network environment in which the present invention may be employed. Of course, actual network and database environments can be arranged in a variety of configurations; however, the exemplary environment shown here provides a framework for understanding the type of environment in which the present invention operates.

[0036] The network may include client computers 20a,a server computer 20b,data source computers 20c,and databases 70, 72a,and 72b.The client computers 20aand the data source computers 20care in electronic communication with the server computer 20bvia communications network 80, e.g., an Intranet. Client computers 20aand data source computers 20care connected to the communications network by way of communications interfaces 82. Communications interfaces 82 can be any one of the well-known communications interfaces such as Ethernet connections, modem connections, and so on.

[0037] Server computer 20bprovides management of database 70 by way of database server system software, described more fully below. As such, server 20bacts as a storehouse of data from a variety of data sources and provides that data to a variety of data consumers.

[0038] In the example of FIG. 2, data sources are provided by data source computers 20c.Data source computers 20ccommunicate data to server computer 20bvia communications network 80, which may be a LAN, WAN, Intranet, Internet, or the like. Data source computers 20cstore data locally in databases 72a,72b,which may be relational database servers, excel spreadsheets, files, or the like. For example, database 72ashows data stored in tables 150, 152, and 154. The data provided by data sources 20cis combined and stored in a large database such as a data warehouse maintained by server 20b.

[0039] Client computers 20athat desire to use the data stored by server computer 20bcan access the database 70 via communications network 80. Client computers 20arequest the data by way of SQL queries (e.g., update, insert, and delete) on the data stored in database 70.

[0040] 3. Database Architecture

[0041] A database is a collection of related data. In one type of database, a relational database, data is organized in a two-dimensional column and row form called a table. FIG. 2B illustrates tables such as tables 150, 152, and 154 that are stored in database 72a.A relational database typically includes multiple tables. A table may contain zero or more records and at least one field within each record. A record is a row in the table that is identified by a unique numeric called a record identifier. A field is a subdivision of a record to the extent that a column of data in the table represents the same field for each record in the table.

[0042] A database typically will also include associative structures. An example of an associative structure is an index, typically, but not necessarily, in a form of B-tree or hash index. An index provides for seeking to a specific row in a table with a near constant access time regardless of the size of the table. Associative structures are transparent to users of a database but are important to efficient operation and control of the database management system. A database management system (DBMS), and in particular a relational database management system (RDBMS) is a control system that supports database features including, but not limited to, storing data on a memory medium, retrieving data from the memory medium and updating data on the memory medium.

[0043] As shown in FIG. 2B, the exemplary database 72acomprises employee table 150, department table 152, and sysindexes table 154. Each table comprises columns 156 and rows 158 with fields 160 formed at the intersections. Exemplary employee table 150 comprises multiple columns 158 including empl_id, empl_name, and empl_salary, dept_id. Columns 158 in department table 152 include dept_id, dept_name, and dept_location. Sysindexes table 154 contains information regarding each table in the database.

[0044] Generally, data stored in a relational database is accessed by way of a user-defined query that is constructed in a query language such as SQL. Typically, for any given SQL query there are numerous procedural operations that need be performed on the data in order to carry out the objectives of the SQL query. For example, there may be numerous joins and table scans that need to be performed so as to accomplish the desired objective.

[0045] As noted control and management of the tables is maintained by a DBMS, e.g., a RDBMS. An exemplary SQL Server RDBMS architecture 90 is graphically depicted in FIG. 3. The architecture comprises essentially three layers. Layer one provides for three classes of integration with the SQL Server, comprising: (1) a SQL Server Enterprise Manager 92 that provides a common environment for managing several types of server software in a network and provides a primary interface for users who are administering copies of SQL Server on the network; (2) an Applications Interface 93 that allows integration of a server interface into user applications such as Distributed Component Object Modules (DCOM); and (3) a Tools Interface 94 that provides an interface for integration of administration and configuration tools developed by Independent Software Vendors (ISV).

[0046] Layer two opens the functionality of the SQL server to other applications by providing three application programming interfaces (API): SQL Namespace 95, SQL Distributed Management Objects 99, and Data Transformation Services 100. A user interface 91 is provided by Wizards, HTML, and so on. SQL Namespace API 95 exposes the user interface (UI) elements of SQL Server Enterprise Manager 92. This allows applications to include SQL Server Enterprise Manager UI elements such as dialog boxes and wizards.

[0047] SQL Distributed Management Objects API 99 abstracts the use of DDL, system stored procedures, registry information, and operating system resources, providing an API to all administration and configuration tasks for the SQL Server.

[0048] Distributed Transformation Services API 100 exposes the services provided by SQL Server to aid in building data warehouses and data marts. As described more fully below, these services provide the ability to transfer and transform data between heterogeneous OLE DB and ODBC data sources. Data from objects or the result sets of queries can be transferred at regularly scheduled times or intervals, or on an ad hoc basis.

[0049] Layer three provides the heart of the SQL server. This layer comprises an SQL Server Engine 97 and a SQL Server Agent 96 that monitors and controls SQL Server Engine 97 based on Events 98 that inform SQL Server Agent of the status of the SQL Server Engine 97. The Server Engine processes SQL statements, forms and optimizes query execution plans, and so on.

[0050] The above description focused on physical attributes of an exemplary database environment in which the present invention operates. FIG. 4 logically illustrates the manner in which data moves among a number of database servers, which may simultaneously be data sources for other database servers, to the destination database.

[0051] Here, Database server 20bprovides management of database 70. Data for database 70 is provided by data sources 72aand 72b, which are managed by database servers 20c′ and 20c, respectively. Significantly, database 20c′ gathers data from databases 72cand 72d,which are managed by servers 20d.Thus, database 70 is fed directly with data from databases 72aand 72band indirectly with data from databases 72cand 72d.

[0052] According to an aspect of the present invention, data moving through several systems toward a destination database can be traced. For example, in the exemplary system of FIG. 4, data from database 72cmoves through database 72aand then on to database 70. Along the way, the data may also undergo transformation. As described more fully below, data lineage information may be attached to data as it moves through systems thereby allowing the history and origin of data to be traced. For example, the data lineage information might indicate that data stored in database 70 data originated from database 72a, 72b, 72c,72d,and so on. Moreover, the lineage information could indicate that data originated in database 72c, passed through database 72aand then moved to database 70. The above examples, merely illustrate the general concept of tracing data movement though several hops before reaching a database server of interest. Those skilled in the art will recognize that many other combinations of movement and transformation of data is possible.

[0053] As described above, data lineage may track the movement of data, the transformation of data, or both. Data lineage tags the information as it moves throught the system. FIG. 5 illustrates one such transformation. In this exemplary transfer, data is merged from two different tables that reside in two different databases into a third table residing in a third database. For example, table 150 resides in database 72awhereas table 149 resides in database 72b. The tables are merged into a third table 151 that is maintained in database 70.

[0054] Although both tables 149, 150 contain similar information, it is not in an identical format. As a result, the data must be transformed into the format of table 151. For example, table 150 maintains a column empl_name that contains employee names as first name followed by last name; whereas, table 149 maintains a column name that contains employee names as last name followed by first name. Table 151 contains employee names in the form of table 150. In order for the name columns of table 149 to be inserted into the empl_name column of table 151, the name must be converted to the proper form. Similarly, table 149 does not contain dept_id information.

[0055] The above example illustrates that data moving between databases may need to be transformed in some manner before insertion into the target database. In FIG. 5, for example, transformation application 204 transform the data of table 149 into proper form for table 151 and transformation application 202 transforms the data of table 150 into proper form for table 151.

[0056] A user of the data contained in table 151 may want to trace the lineage of the data for the purpose of verifying its accuracy, tracing it source, and so on. To that end table 151 contains an additional column 157. Lineage column 157 contains information to provide a link to the lineage of the data. In the present example, notice that each row that passes through transform 202 is appended with the same unique data lineage value. Each row passing through transform 204 is appended with a unique identifier that is different from the identifier associated with the rows originating from table 150.

[0057] The data lineage information attached to the data is preferably stored as a data lineage data type. A data lineage data type comprises a globally unique identifier that is assigned to a row of data in a table. The globally unique identifier preferably uniquely identifies data as having a particular lineage, preferably on at least a table level, and more preferably on a row level. Hence, two or more rows of data having identical data lineage values will have a common lineage.

[0058] Referring to FIG. 5, for example, data lineage value “435492295” identifies one set of rows sharing a common lineage and “32549227” identified another set of rows sharing a common lineage. Based on this example, a user comparing a row having lineage value “435492295” and a row having a lineage value “32549227” can know at least that the two rows have origins in different tables.

[0059] According to another aspect of the present invention, the data lineage data type can contain a value that points to an object containing lineage additional lineage information. Referring to FIG. 6, this further aspect of data lineage is illustrated. Again, table 151 having a data lineage data type column appended to the data is shown.

[0060] Table 151 is stored in database 70, which is maintained by server computer 20b.Also coupled to server computer 20bis an object repository 71 which may be maintained as part of database 70 but which is preferably maintained as a separate database. Repository 71 contains two exemplary objects, 206 and 208. Object 206 is pointed to by data lineage value “435492295” and object 208 is pointed to by data lineage value “32549227.” That is, having the unique data lineage value, a corresponding data lineage object can be located in repository 71. By examining the contents of the corresponding data lineage object, further data lineage information is provided for all data that is bound to that data lineage object.

[0061] The data lineage object preferably contains the source data base tables from which the row of interest was formed and the transformation that was used to move the data from the source row and change the data before moving it into the row of interest. Preferably, the data lineage object comprises a package as exemplified in FIG. 7.

[0062] As illustrated in FIG. 7, each package comprises a steps 212 that convert the data among formats (e.g., convert from spread sheet to database form), task(s) 216 that transform the data to a format of the destination table, and global variables 222 that are available system wide. Steps 212 define a set of precedence 214 that must be performed on the data in a particular order before the data can be operated upon.

[0063] Once the data is in a usable format, transformation tasks 216 transform the data before moving it to the destination row (e.g., see FIG. 5 showing the conversion of name in table 149). The tasks could be custom procedural scripts, ActiveX® scripts, or, as described more fully below data pump connections. The task defines the source table 218, the destination table 219, and corresponding columns that join the two tables together. And, the transformation algorithm 221 defines how the data is changed.

[0064] FIGS. 8A-8C show an exemplary transform for moving data from an external source table (e.g., from database 72a) into a destination table (e.g., to database 70) while adding data lineage information by way of the “data pump”. Here, dialog boxes corresponding to package boxes 218, 219, and 221 are provided that graphically allows users to import and transform data. In FIG. 8B, a user can define the selected rows of the selected table to import. Here, a definition is provided by way of an SQL query. In FIG. 8C, a user can define a destination table to accept the data to be imported. Finally in FIG. 8A, a user can define the relationship of source to destination rows as indicated by arrow 220 and select a predefined transformation to apply to the data during the importation. Here, a simple row copy has been selected. Notably, two columns have been added to the destination column: Lineage_Full 233; and Lineage_Short 234.

[0065] Lineage_Full contains a unique identifier as described in detail above. To ensure uniqueness, Lineage_Full contains a sixteen-byte value that is generated by using the standard MICROSOFT® WINDOWS® call to CoCreateGUID (which returns a globally unique identifier (“GUID”)). The resulting value should be unique for all databases. However, adding sixteen bytes to every row in a database requires a substantial storage cost and potentially performance cost. An optional shorter lineage value is available by using Lineage_Short. Preferably, Lineage_Short is an integer number, most preferably about 4 bytes long.

[0066] According to an aspect of the present invention, Lineage_Short is a function of a universally unique value, such as a value returned from the CoCreateGUID function. After obtaining the universally unique value, e.g., a Lineage_Long value, that value is compressed to obtain the Lineage_Short value.

[0067] FIG. 11, illustrates the creation of long and short lineage values. Initially a call is made to CoCreateGUID function 262. CoCreateGUID returns a sixteen-byte value Lineage_Long 234. The Lineage_Long value 234 is then compressed by compression function 264, which outputs a four-byte Lineage_Short value. An exemplary compression function is a standard Cyclical Redundancy Check (CRC) calculation. The CRC produces a four-byte integer value from the sixteen-byte input value. The Lineage_Short value can then be used in place of the Lineage Long value, providing significant likelihood of uniqueness while also enhancing database performance over the Lineage_Long value.

[0068] As the data is moved into the destination table, the system automatically adds the data lineage value for each row passing through the transform 221. Before or after the transform is complete, a copy of the package is stored in repository 71 (See FIG. 6). Thereafter, at any time in the future, a user can retrieve and view the exact package that was used to transform the data as it moved into the database by using the lineage pointer to recover the package from the repository.

[0069] FIG. 9 illustrates a simple VISUAL BASIC® transformation script 216bthat performs the same function as the graphical importation described above in reference to FIGS. 8A-8C. As with the UI package described above. The VISUAL BASIC transform forms part of a package 210 that is also stored in repository 71 and pointed to by the data lineage value for all rows that it transformed.

[0070] The data lineage information is added as data is imported into the destination database, e.g., database 70. FIG. 10 schematically depicts the architecture of adding data lineage information to incoming data by way of a streaming system referred to previously as a “data pump” 216c.As each row is pulled from source database, e.g., 72ainto data pump 216c,a transform 221 is applied and data lineage information is bound to the data. The information is then pumped out into the destination database 70.

[0071] After the data lineage information is stored in the repository and linked to the data stored in the database, a user can use the data lineage to trace the history of data. FIG. 12 illustrates a lineage WINDOW 250 that is displaying lineage information for a selected exemplary Lineage_Short 233 value, i.e., “−435492295.” WINDOW 250 displays an associated Lineage_Long 234 value, a Package identifier 254, and a Package version identifier 255. The Package and Package Version identifiers 254, 255 can then be used to browse in repository 71 for the procedure used to transform the data associated with the selected lineage value.

[0072] Package version identifier 255 indicates the particular version of the procedure. Thus, as a particular package is modified, the data lineage will still be able to recover the procedure that transformed particular data using well known versioning techniques.

[0073] In summary, a system for tracking the lineage of data as it moves through a network of databases has been described. The system function by attaching an identifier to data as it is imported into a database. The specific example above illustrated how the data lineage information is attached for importation into a single database. However, data can be tracked over several “hops” among databases by repeatedly tagging a data lineage identifier to the data during the importation into each database along the path that the data travels. In that way, the source of data can be traced over a plurality of databases.

[0074] Those skilled in the art understand that computer readable instructions for performing the above described processes can be generated and stored on a computer readable medium such as a magnetic disk or CD-ROM. Further, a computer such as that described with reference to FIG. 1 may be arranged with other similarly equipped computers in a network, and each computer may be loaded with computer readable instructions for performing the above described processes. Specifically, referring to FIG. 1, microprocessor 21 may be programmed to operate in accordance with the above described processes.

[0075] While the invention has been described and illustrated with reference to specific embodiments, those skilled in the art will recognize that modification and variations may be made without departing from the principles of the invention as described above and set forth in the following claims. In particular, the invention may employed with any type of database including those not in relational format. Further, the invention may be employed in any database that uses statistics in any way to select a plan for processing a user defined query. Also, the statistics may be of any type and are not limited to those described above. Indeed, the statistics may be derived for single columns of data, multiple columns of data or for any other division of data. Accordingly, reference should be made to the appended claims as indicating the scope of the invention.