# ML Based Lineage in Databases

arXiv: https://arxiv.org/abs/2109.06339 · HTML: https://mlsanity.com/paper/2109.06339/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 10 of its 52 references that are in the map.
- First posted on arXiv 13 Sep 2021.

## Builds on (most cited first, 10 of 10)

- [BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding](https://mlsanity.com/paper/1810.04805/) (2018)
- [Efficient Estimation of Word Representations in Vector Space](https://mlsanity.com/paper/1301.3781/) (2013)
- [Distributed Representations of Words and Phrases and their Compositionality](https://mlsanity.com/paper/1310.4546/) (2013)
- [Google's Neural Machine Translation System: Bridging the Gap between Human and Machine Translation](https://mlsanity.com/paper/1609.08144/) (2016)
- [Universal Sentence Encoder](https://mlsanity.com/paper/1803.11175/) (2018)
- [Multilingual Language Processing From Bytes](https://mlsanity.com/paper/1512.00103/) (2015)
- [Enabling Cognitive Intelligence Queries in Relational Databases using Low-dimensional Word Embeddings](https://mlsanity.com/paper/1603.07185/) (2016)
- [Cognitive Database: A Step towards Endowing Relational Databases with Artificial Intelligence Capabilities](https://mlsanity.com/paper/1712.07199/) (2017)
- [On Embeddings in Relational Databases](https://mlsanity.com/paper/2005.06437/) (2020)
- [Efficient Approximate Search for Sets of Vectors](https://mlsanity.com/paper/2107.06817/) (2021)

## Abstract (arXiv)

We track the lineage of tuples throughout their database lifetime. That is, we consider a scenario in which tuples (records) that are produced by a query may affect other tuple insertions into the DB, as part of a normal workflow. As time goes on, exact provenance explanations for such tuples become deeply nested, increasingly consuming space, and resulting in decreased clarity and readability. We present a novel approach for approximating lineage tracking, using a Machine Learning (ML) and Natural Language Processing (NLP) technique; namely, word embedding. The basic idea is summarizing (and approximating) the lineage of each tuple via a small set of constant-size vectors (the number of vectors per-tuple is a hyperparameter). Therefore, our solution does not suffer from space complexity blow-up over time, and it "naturally ranks" explanations to the existence of a tuple. We devise an alternative and improved lineage tracking mechanism, that of keeping track of and querying lineage at the column level; thereby, we manage to better distinguish between the provenance features and the textual characteristics of a tuple. We integrate our lineage computations into the PostgreSQL system via an extension (ProvSQL) and extensive experiments exhibit useful results in terms of accuracy against exact, semiring-based, justifications, especially for the column-based (CV) method which exhibits high precision and high per-level recall. In the experiments, we focus on tuples with textitmultiple generations of tuples in their lifelong lineage and analyze them in terms of direct and distant lineage.