On fixing broken lineage

Data lineage is an important part of today's information systems.Several methods for providing means of recording and querying original sources for data stored in the system have been developed.Unfortunately, unless all of the system components provide support for recording/extracting and exchange of data lineage, obtaining full lineage information may be impossible.Consequently, lineage can sometimes be "broken."Possible causes for breaking lineage include: (1) usage of auxiliary data structures during processing, such as in-memory or temporary tables, (2) data cleaning performed semi-automatically and involving user intervention, and (3) ETL processes employing user-implemented "black box" steps which are not integrated into lineage tracking subsystem.In this paper, we present ideas for deducing lineage by observing data only.We assume almost no prior knowledge about the datasets and almost no meta-data available.We do not aim to provide a complete lineage tracking system, but rather provide a set of algorithms that can be integrated into existing data lineage systems and provide additional information about possible sources for data.