# Presentation: 211327

## The Why and Where ofData ProvenancePeter BunemanSanjeev KhannaWang-Chiew TanUniversity of Pennsylvania

- DL-2 grant IIS 98-17444
- http://db.cis.upenn.edu
- http://db.cis.upenn.edu/Research/provenance.html

## Data Provenance

- When you see some data on the Web, do you know
- _where_ it came from?
- _why_ is it there?
- This information (provenance) is typically lost in the process of copying/transforming databases
- Loss of provenance is an acute problem in some scientific databases

## Provenance of Data Derived via Queries

- 500 databases in molecular biology
- only a handful are source data
- rest are materialized views

## Database Inter-dependence is Complex

- GERD*

- TRRD*

- GenBank*

- Swissprot*

- EpoDB*

- TransFac*

- GAIA

- BEAD*

## Provenance of Data Derived via Queries

- 500 databases in molecular biology
- only a handful are source data
- rest are materialized views

- If the data comes from a curated database, can we carry through relevant annotations ?

- We see a piece of data in some view
- the origins of this piece of data
- the process by which it was included

## Database Inter-dependence is Complex

- GERD*

- TRRD*

- GenBank*

- Swissprot*

- EpoDB*

- TransFac*

- GAIA

- BEAD*

## Two kinds of provenance

- SELECT name, born
- FROM   composer
- WHERE  born < 1700

- name	born
- J.S. Bach 	1685
- G.F. Handel 	1685

## Why vs. Where-Provenance

- SELECT name, telephone
- FROM    employee
- WHERE salary > SELECT AVERAGE salary FROM employee

- What specific part of input data contributed to my inclusion in the output ?
- the entire employee database

- Given that I am in the output, where did my telephone number come from ?
- just my record in the employee database

## The problem at hand

- Given a database D=Q(D1,...,Dn) and a component c of D, what is the “why” and “where” provenance of c?
- We expect the answer, in each case, to be a set of components of D1,...,Dn
- What are the relevant components ?
- How do we identify them ?

## The Goals of this Project

- Describe provenance

- Construct data that knows
- why it exists and where it came from

- Infer provenance

- Annotate data with provenance

## Semistructured data --deterministic model

**“****I have enough”**

**“****Art thou troubled?”**

**num: “BWV 82”**

**title**

**title**

**num: HWV19**

**works**

**works**

**period**

**name: “J.S. Bach”**

**name: “G.F. Handel”**

**“****baroque”**

**num: “BWV552”**

## A deterministic model for semi-structured (and structured) data

- Based on common model of semistructured data as an edge-labeled graph.
- Less general
- Deterministic (outgoing edges are distinct)
- More general
- Labels can have structure

## Relationship with XML

**“****I have enough”**

**composer**

**“****Art thou troubled?”**

**“****BWV 82”**

**“****HWV 19**

**num**

**title**

**num**

**title**

**num**

**opus**

**opus**

**opus**

**name**

**name**

**works**

**works**

**period**

**composer**

**db**

**“****J.S. Bach”**

**“****G.F. Handel”**

**“****baroque”**

**“****BWV 552**

**born**

**1685**

**born**

**1685**

**...**

**1756**

**born**

**composer**

## Relationship with XML

**“****I have enough”**

**composer**

**“****Art thou troubled?”**

**“****BWV 82”**

**“****HWV 19**

**num**

**title**

**num**

**title**

**num**

**opus**

**opus**

**opus**

**name**

**name**

**works**

**works**

**period**

**composer**

**db**

**“****J.S. Bach”**

**“****G.F. Handel”**

**“****baroque”**

**“****BWV 552**

**born**

**1685**

**born**

**1685**

**...**

**1756**

**born**

**composer**

## An Example

**Find all composers **
**born in the same year**

**<year born=****1685****>**
**   ****<name> ****G.F. Handel**** </name>**
**   ****<name> ****J.S. Bach**** </name>**
**</year>**

**Why?**

## The Why-Provenance

**“****I have enough”**

**composer**

**“****Art thou troubled?”**

**“****BWV 82”**

**“****HWV 19**

**num**

**title**

**num**

**title**

**num**

**opus**

**opus**

**opus**

**name**

**name**

**works**

**works**

**period**

**composer**

**db**

**“****J.S. Bach”**

**“****G.F. Handel”**

**“****baroque”**

**“****BWV 552**

**born**

**1685**

**born**

**1685**

- [1]

- [1]

- [1]

- [1]

- [1]

- [1]

- [1]

- [1]

- [1]

- [1]

- [1]

- [1]

- [1]

- [1]

- [1]

- [1]

- [2]

- [2]

- [2]

- [2]

- [2]

- [2]

- [3]

- [3]

- [1]

- [4]

- [1]

**...**

- [1]

- [1]

- [3]

**1756**

**born**

**composer**

## The Why-Provenance

**“****I have enough”**

**composer**

**“****Art thou troubled?”**

**“****BWV 82”**

**“****HWV 19**

**num**

**title**

**num**

**title**

**num**

**opus**

**opus**

**opus**

**name**

**name**

**works**

**works**

**period**

**composer**

**db**

**“****J.S. Bach”**

**“****G.F. Handel”**

**“****baroque”**

**“****BWV 552**

**born**

**1685**

**born**

**1685**

- [1]

- [1]

- [1]

- [1]

- [1]

- [1]

- [1]

- [1]

- [1]

- [1]

- [1]

- [1]

- [1]

- [1]

- [1]

- [1]

- [2]

- [2]

- [2]

- [2]

- [2]

- [2]

- [3]

- [3]

- [1]

- [4]

- [1]

**...**

- [1]

- [1]

- [3]

**1756**

**born**

**composer**

## An Example

**<year born=****1685****>**
**   ****<name> ****G.F. Handel**** </name>**
**   ****<name> ****J.S. Bach**** </name>**
**</year>**

**Where?**

**Find all composers **
**born in the same year**

## The Where-Provenance

**“****I have enough”**

**composer**

**“****Art thou troubled?”**

**“****BWV 82”**

**“****HWV 19**

**num**

**title**

**num**

**title**

**num**

**opus**

**opus**

**opus**

**name**

**name**

**works**

**works**

**period**

**composer**

**db**

**“****J.S. Bach”**

**“****G.F. Handel”**

**“****baroque”**

**“****BWV 552**

**born**

**1685**

**born**

**1685**

- [1]

- [1]

- [1]

- [1]

- [1]

- [1]

- [1]

- [1]

- [1]

- [1]

- [1]

- [1]

- [1]

- [1]

- [1]

- [1]

- [2]

- [2]

- [2]

- [2]

- [2]

- [2]

- [3]

- [3]

- [1]

- [4]

- [1]

**...**

- [1]

- [1]

- [3]

**1756**

**born**

**composer**

## A Query Language

- A complex query can be transformed into an equivalent canonical form:
- 	Q = Q1  ...  Qn
- Each Qi has the form
- where p1 in D1,
-            ...
-            pn in Dn,
-            condition
- collect e

- Each pi is a “path”-pattern
- Each Di is some database name
- Output e is a “path”-pattern as well

## How does this help compute provenance?

- We are interested in the provenance of some component of the database.
- This component is specified by a path *p* (a path expression without variables)
- Map the variables in the output expression e to the path *p*
- Track these variables though the query to identify provenance

## Demo Computing Data Provenance and Carry Annotations through Querieshttp://hobbit.cis.upenn.edu:8080

**This title is better than the previous one.**

## A Join Query

**Project the name and grade of the join of **
**Students and Enrollments relation**

## A Join Query

## Results

- Previous work (Cui, Widom, and Wiener) provides a solution for relational databases.
- deals with “why” provenance
- For why-provenance, we get same answers by very different framework
- Where-provenance -- seems new !

## Closing Thoughts

- Data provenance is a subtle issue

- Where provenance allows to carry over meaningful annotations

- Annotations are expensive

## Slide 27

## Closing Thoughts

- Data provenance is a subtle issue

- Where provenance allows to carry over meaningful annotations

- Annotations are expensive

- Meaningful annotations require versioning

- Imagine recursive annotation trees !
- What compression techniques work ?

## Using “persistent” representations

## The “compressed” version

## END