Welcome to DiSC 2002
SIGMOD 2001
PODS 2001
SIGMOD RECORD 2001
CIKM 2001
CoopIS 2001
DASFAA 2001
DASFAA 2000
DBPL 2001
Data Engineering Bul
DEXA_EC-WEB 2001
DMKD 2001
DPDJ 2001
HYPERTEXT 2001
ICDE 2001
ICDM 2001
ICDT 2001
JCDL 2001
KDD 2001
KDD_EXPLORATIONS 20
KRDB 2001
MDM 2001
MIR 2001
MIS 2001
RIDE 2001
SBBD 2001
SIGIR 2001
SIGIR FORUM 2001
SSDBM 2001
= SSDBM'01 Website
<<< = SSDBM'01 Papers>>>
SSTD 2001
TODS 2001
TIME 2001
VLDB 2001
VLDBJ 2001

Tracing Lineage of Array Data


Arunprasad P. Marathe

  View Paper (PDF)  

Return to Index Structures for SSDBM


Abstract

Arrays are a common and important class of data. They can model digital images, digital video, scientific and experimentation data, matrices, finite element grids, and many other types of data. Although array manipulations are diverse and domain-specific, they often exhibit structural regularities. This paper presents an algorithm called SUB-pushdown to compute data lineage in such array computations. The array manipulations are expressed in the Array Manipulation Language (AML) that was introduced previously. SUB-pushdown has several useful features. First, the lineage computation is expressed as an AML query. Second, it is not necessary to evaluate the AML lineage query to compute the array data lineage. Third, SUB-pushdown never gives false-negative answers. SUB-pushdown has been implemented as part of the ArrayDB prototype array database system that we have built.


DiSC'02 © 2003 Association for Computing Machinery