# Schema Design for Uncertain Databases

Das Sarma, Anish and Ullman, Jeffrey and Widom, Jennifer (2007) Schema Design for Uncertain Databases. In: Alberto Mendelzon Workshop on Foundations of Data Management.

 BibTeX DublinCore EndNote HTML

 Preview
PDF
259Kb

## Abstract

We address schema design in uncertain databases such as are found in Trio. Since uncertain data is relational in nature, decomposition becomes a key issue in design. Decomposition relies on dependency theory, and primarily on functional dependencies. We study the theory of functional dependencies (FDs) for uncertain relations. We define several kinds of {\em horizonal} FDs and {\em vertical} FDs, each of which is consistent with conventional FDs when an uncertain relation doesn't contain any uncertainty. In addition to standard forms of decompositions allowed by ordinary relations, our FDs allow more complex decompositions specific to uncertain data. First we give a sound and complete axiomatization of horizontal and vertical FDs. Next we show how our theory of FDs can be used for lossless decomposition of uncertain relations. We then present algorithms and complexity results for three fundamental problems with respect to FDs over ordinary and uncertain relations: (1) {\em Testing} whether a relation instance satisfies an FD; (2) {\em Finding} all FDs satisfied by a relation instance; and (3) {\em Inferring} all FDs that hold in the result of a query over uncertain relations with FDs. Finally, we look at keys as a special case of FDs, and briefly consider uncertain data that contains {\em confidence} values.

Item Type: Uncontrolled Keywords: Conference or Workshop Item (Paper) dependency theory; uncertain data; Miscellaneous Miscellaneous Project Homepage http://infolab.stanford.edu/ 820 Anish Das Sarma 29 Nov 2007 16:00 09 Mar 2009 09:02