Trio: A System for Integrated Management of Data, Accuracy, and Lineage
Published 1 August 2004
Jennifer Widom
Citations477
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
This paper provides numerous motivating applications for Trio and lays out preliminary plans for the data model, query language, and prototype system.
Abstract
Trio is a new database system that manages not only data, butalsotheaccuracy and lineage of the data. Inexact (uncertain, probabilistic, fuzzy, approximate, incomplete, and imprecise!) databases have been proposed in the past, and the lineage problem also has been studied. The goals of the Trio project are to combine and distill previous work into a simple and usable model, design a query language as an understandable extension to SQL, and most importantly build a working system—a system that augments conventional data management with both accuracy and lineage as an integral part of the data. This paper provides numerous motivating applications for Trio and lays out preliminary plans for the data model, query language, and prototype system.
Keywords
Computer ScienceDecision Sciences
IEEE ExpertData mining and knowledge discovery: making sense out of data
4,643 Citations1996U.M. Feyyad
Find loads of the data mining and knowledge discovery making sense out of data book catalogues in this site as the choice of you visiting this page.
Lecture notes in computer scienceWhy and Where: A Characterization of Data Provenance
1,310 Citations2001Peter Buneman, Sanjeev Khanna +1 more
An approach to computing provenance when the data of interest has been created by a database query is described, adopting a syntactic approach and present results for a general data model that applies to relational databases as well as to hierarchical data such as XML.
Journal of the ACMIncomplete Information in Relational Databases
1,018 Citations1984Tomasz Imieliński, Witold Lipski
There are precise conditions that should be satisfied in a semantically meaningful extension of the usual relational operators, such as projection, selection, union, and join, from operators on relations to operators on tables with “null values” of various kinds allowed.
The VLDB JournalEfficient query evaluation on probabilistic databases
979 Citations2006Nilesh Dalvi, Dan Suciu
It is shown that the data complexity of some queries is #P-complete, which implies that these queries do not admit any efficient evaluation methods, and an optimization algorithm is described that can compute efficiently most queries.
Data Mining and Knowledge DiscoveryReal-world Data is Dirty: Data Cleansing and The Merge/Purge Problem
813 Citations1998Mauricio A. Hernández, Salvatore J. Stolfo
This paper develops a system for accomplishing this Data Cleansing task and demonstrates its use for cleansing lists of names of potential customers in a direct marketing-type application and reports on the successful implementation for a real-world database that conclusively validates results previously achieved for statistically generated data.
Generalizing data to provide anonymity when disclosing information (abstract)
777 Citations1998Pierangela Samarati, Latanya Sweeney
An algorithm is described that, given a table, efficiently computes a preferred minimal gcnoralization to provide anonymity and the notions of generalized table and of minimal generalization of a table are introduced with respect to a k-anonymity requirement.
Interactive deduplication using active learning
693 Citations2002Sunita Sarawagi, Anuradha Bhamidipaty
This work presents the design of a learning-based deduplication system that uses a novel method of interactively discovering challenging training pairs using active learning and investigates various design issues that arise in building a system to provide interactive response, fast convergence, and interpretable output.
Elsevier eBooksHippocratic Databases
634 Citations2002Rakesh Agrawal, Jerry Kiernan +2 more
It is argued that future database systems must include responsibility for the privacy of data that they manage as a founding tenet, because of the explosive progress in networking, storage, and processor technologies.
Fuzzy Sets and SystemsA fuzzy representation of data for relational databases
613 Citations1982Bill P. Buckles, Frederick E. Petry
Two critical properties possessed by ordinary relational databases are proven to exist in the fuzzy relational structure, which means no two tuples have identical interpretations, and each relational operation has a unique result.
Chimera: a virtual data system for representing, querying, and automating data derivation
608 Citations2002Ian Foster, Jens Vöckler +2 more
The Chimera virtual data system is developed, which combines avirtual data catalog for representing data derivation procedures and derived data, with a virtual data language interpreter that translates user requests into data definition and query operations on the database.
ACM Transactions on Database SystemsUpdate semantics of relational views
583 Citations1981François Bancilhon, Nicolas Spyratos
The main result of the paper states that, given a complete set U of view updates, U has a translator if and only if U is translatable under constant complement.
Evaluating probabilistic queries over imprecise data
578 Citations2003Reynold Cheng, Dmitri V. Kalashnikov +1 more
This paper addresses the important issue of measuring the quality of the answers to query evaluation based upon uncertain data, and provides algorithms for efficiently pulling data from relevant sensors or moving objects in order to improve thequality of the executing queries.
Potter's Wheel: An Interactive Data Cleaning System
491 Citations2001Vijayshankar Raman, Joseph L. Hellerstein
Potter’s Wheel is presented, an interactive data cleaning system that tightly integrates transformation and discrepancy detection, and users can gradually build a transformation as discrepancies are found, and clean the data without writing complex programs or enduring long delays.
Robust and efficient fuzzy match for online data cleaning
456 Citations2003Surajit Chaudhuri, Kris Ganjam +2 more
A new similarity function is proposed which overcomes limitations of commonly used similarity functions, and an efficient fuzzy match algorithm is developed which can effectively clean an incoming tuple if it fails to match exactly with any tuple in the reference relation.
IEEE Transactions on Knowledge and Data EngineeringThe management of probabilistic data
451 Citations1992Daniel Barbará, Héctor García-Molina +1 more
A data model that includes probabilities associated with the values of the attributes, and the notion of missing probabilities is introduced for partially specified probability distributions, offers a richer descriptive language allowing the database to more accurately reflect the uncertain real world.
ACM Transactions on Database SystemsTracing the lineage of view data in a warehousing environment
436 Citations2000Yingwei Cui, Jennifer Widom +1 more
The lineage problem is formally defined, lineage tracing algorithms for relational views with aggregation are developed, and mechanisms for performing consistent lineage tracing in a multisource data warehousing environment are proposed.
An Efficient Domain-Independent Algorithm for Detecting Approximately Duplicate Database Records.
354 Citations1997Alvaro Monge, Charles Elkan
An eecient algorithm for recognizing clusters of approximately duplicate records that typically reduces by over 75% the number of times that the expensive pair-wise record matching (Smith-Waterman or other) is applied, without impairing accuracy.
The VLDB JournalLineage tracing for general data warehouse transformations
348 Citations2003Yangfan Cui, Jennifer Widom
This work formally defines the lineage tracing problem in the presence of general data warehouse transformations, and presents algorithms for lineage tracing in this environment, and can be used as the basis for a lineage tracing tool in a general warehousing setting.
ACM Transactions on Database SystemsProbView
345 Citations1997Laks V. S. Lakshmanan, Nicola Leone +2 more
This article characterize, using postulates, whole classes of strategies for conjunction, disjunction, and negation, meaningful from the viewpoint of probability theory, and shows that as long as the chosen strategies can be computed in polynomial time, queries in the positive fragment of the probabilistic relational algebra have essentially the same data complexity as classical relational algebra.
Declarative Data Cleaning: Language, Model, and Algorithms
317 Citations2001Héléna Galhardas, Daniela Florescu +3 more
This paper presents a language, an execution model and algorithms that enable users to express data cleaning specifications declaratively and perform the cleaning efficiently and experimental results report on the assessement of the proposed framework for data cleaning.
TAILOR: a record linkage toolbox
286 Citations2003Mohamed Elfeky, Vassilios S. Verykios +1 more
The results show that the proposed machine-learning record linkage models outperform the existing ones both in accuracy and in performance.
The VLDB JournalAn annotation management system for relational databases
277 Citations2005Deepavali Bhagwat, Laura Chiticariu +2 more
An annotation management system for relational databases where every piece of data in a relation is assumed to have zero or more annotations associated with it and annotations are propagated along, from the source to the output, as data is being transformed through a query.
The Design of the POSTGRES Storage System
255 Citations1987Michael Stonebraker
The design of the storage system for the POSTGRES data base system under construction at Berkeley is novel in several ways and suggests that it is performance competitive with WAL systems in many situations.
Automated Ranking of Database Query Results
236 Citations2003Sanjay Agrawal, Surajit Chaudhuri +2 more
The challenges and several approaches to enable ranking in databases, including adaptations of known techniques from information retrieval, are discussed and results of preliminary experiments are presented.
Supporting fine-grained data lineage in a database visualization environment
200 Citations2002Allison Woodruff, Michael Stonebraker
This paper proposes a novel method to support fine-grained data lineage that lazily computes the lineage using a limited amount of information about the processing operators and the base data, and introduces the notions of weak inversion and verification.
ACM SIGMOD RecordThe Aqua approximate query answering system
195 Citations1999Swarup Acharya, Phillip B. Gibbons +2 more
Adaptive precision setting for cached approximate values
191 Citations2001Chris Olston, Boon Thau Loo +1 more
A parameterized algorithm for adjusting the precision of cached approximations adaptively to achieve the best performance as data values, precision requirements, or workload vary, which easily outperforms previous algorithms for exact caching.
Very Large Data BasesApproximate Query Processing: Taming the TeraBytes
182 Citations2001Minos Garofalakis, Phillip B. Gibbon
Efficient record linkage in large data sets
173 Citations2003Liang Jin, Chen Li +1 more
This paper describes an efficient approach to record linkage that first map values to a multidimensional Euclidean space that preserves domain-specific similarity over individual attributes constituting the record.
RePEc: Research Papers in EconomicsA Polygen Model for Heterogeneous Database Systems: The Source Tagging Perspective
172 Citations1990Y. Richard Wang, Stuart Madnick
A polygen model for resolving the Data Source Tagging and Intermediate source Tagging problems is presented and a data-driven query translation mechanism for mapping a polygen query into a set of local queries dynamically is presented.
ACM SIGMOD RecordCombining fuzzy information
163 Citations2002Ronald Fagin
Algorithms for determining the top k objects, that is, k objects with the highest overall grades, are discussed and compared.
Offering a Precision-Performance Tradeoff for Aggregation Queries over Replicated Data
156 Citations2000Chris Olston, Jennifer Widom
The architecture of TRAPP replication systems is defined, some mechanics of caching data ranges are covered, and fine-grained control of the precision-performance tradeoff offered by TRAPP systems is presented.
ACM Transactions on Database SystemsArchiving scientific data
136 Citations2004Peter Buneman, Sanjeev Khanna +2 more
This article develops an archiving technique that is both efficient in its use of space and preserves the continuity of elements through versions of the database, something that is not provided by traditional minimum-edit-distance diff approaches and uses timestamps.
A Probabilistic Framework for Vague Queries and Imprecise Information in Databases
111 Citations1990Norbert Fuhr
A probabilistic learning model for vague queries and missing or imprecise information in databases is described, which yields a ranking of objects from the database in response to a query by using relevance judgements from the user about the objects retrieved.
Earth System Science Workbench: a data management infrastructure for earth science products
108 Citations2002James Frew, Rajendra Bose
An implementation of ESSW to track the processing of locally received satellite imagery is presented, demonstrating the Workbench's transparent and robust support for archiving and publishing data products.
ACM Transactions on Database SystemsIndefinite and maybe information in relational databases
106 Citations1990Ken‐Chih Liu, Rajshekhar Sunderraman
The relational model is extended in a semantically correct way to operate on I-tables, and an operator to remove redundant facts is presented.
IEEE Transactions on Knowledge and Data EngineeringAggregation of imprecise and uncertain information in databases
88 Citations2001Sally McClean, Bryan Scotney +1 more
This work considers the problem of aggregation using an imprecise probability data model that allows us to represent imprecision by partial probabilities and uncertainty using probability distributions to perform the operations necessary for knowledge discovery in databases.
GADT: a probability space ADT for representing and querying the physical world
78 Citations2003Anton K. Faradjian, Johannes Gehrke +1 more
A new object-relational abstract data type (ADT) is introduced - the Gaussian ADT - that models physical data as Gaussian PDFs, and it is shown that existing index structures can be used as fast access methods for GADT data.
Very Large Data BasesAn Extended Relational Database Model for Uncertain and Imprecise Information
74 Citations1992Suk Kyoon Lee
An extended relational database model which can model both uncertainty and imprecision in data is proposed which is based on Dempster-Shafer theory which has become popular in AI as an uncertainty reasoning tool.
Theoretical Computer ScienceQuery evaluation in probabilistic relational databases
72 Citations1997Esteban Zimányi
A sound and complete method is described for evaluating queries in probabilistic theories and can be incorporated into existing relational systems with the addition of a component for manipulating propositional formulas.
Nano LettersSuperimposed Information for the Internet.
66 Citations1999David Maier, Lois Delcambre
Two techniques to enhance the Q of a nanomechanical beam are explored, showing that by embedding a nanobeam in a 1D phononic crystal (PnC), it is possible to localize its flexural motion and shield it against radiation loss, and taking advantage of the mode-shape dependence of stress-induced "loss dilution.
Modeling uncertainty in databases
52 Citations2002Fereidoon Sadri
It is shown that extended relational algebra operations are precise, that is, they produce exactly the same answers that are expected under the semantic interpretation.
Management of uncertainty in database systems
44 Citations1995Amihai Motro
This chapter addresses issues of database uncertainty by defining basic terminology, and it classifies the various kinds of uncertainty.
Bundles in captivity: an application of superimposed information
43 Citations2002Lois Delcambre, David Maier +7 more
The SLIMPad (Superimposed Layer Information Manager scratchPad) is reported on, a superimposed application which was inspired by the "bundling" of information elements from disparate sources the authors observed in a medical setting.
IEEE Data(base) Engineering BulletinMeta-Data Support for Data Transformations Using Microsoft Repository.
39 Citations1999Philip A. Bernstein, Thomas Bergstraesser
This paper describes facilities that are integrated with Microsoft SQL Server 7.0, particularly as they relate to meta-data and information models in its shared repository, and discusses the use of XML to move meta- data between tools.
IEEE Transactions on Knowledge and Data EngineeringIncomplete relational database models based on intervals
36 Citations1993A. Ola, Gültekin Özsoyoğlu
For each of the models in the family, it is shown that query evaluation is sound in the Imielinski-Lipski sense, and none of the Models is complete in the Iliffe-Lipski sense.
PREDATOR
33 Citations1997Praveen Seshadri, Mark A. Paskin
The demonstration shows the following features of PREDATOR: (a) standard relational query processing capability through SQL queries, (b) extensibility with complex data types, (c) content-baaed feature extraction, indexing and retrieval using path indexes, and (d) extensible optimization of E-ADT expressions by reordering and merging.
Approximate selection queries over imprecise data
28 Citations2004Iosif Lazaridis, Sharad Mehrotra
This work allows queries to specify their own answer quality requirements, and establishes that the answer accuracy/performance tradeoff can be realized in a more general setting than previously seen.
Uncertain, Incomplete, and Inconsistent Data in Scientific and Statistical Databases
21 Citations1997Stephen K. Kwan, Frank Olken +1 more
This chapter is a survey of several issues and applications in uncertain, inconsistent, and incomplete data in scientific and statistical databases (SSDBs).
A framework for implementing hypothetical queries
18 Citations1997Timothy G. Griffin, Richard Hull
An approach to optimizing the evaluation of hypothetical queries that uses deltas in the sense of Heraclitus, and permits a range of evaluation strategies from lazy to eager is developed.
ACM SIGMOD RecordOnline query processing
12 Citations2001Peter J. Haas, Joseph M. Hellerstein
This research agenda brings together a number of threads in database research, including query processing architectures and algorithms, sampling and statistical estimation, and user interfaces for data visualization and transformation.