Schema Design for Uncertain Databases

3rd Alberto Mendelzon International Workshop on Foundations of Data Management

Anish Das Sarma ; Jeffrey Ullman ; Jennifer Widom

Others  :  http://CEUR-WS.org/Vol-450/paper2.pdf
PID  :  4443

来源: CEUR

【 摘 要 】

We address schema design in uncertain databases. Since uncertain data is rela- tional 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 horizontal FDs and 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 ordi- nary relations, our FDs allow more complex decompositions specific to uncertain data. 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) Testing whether a relation instance satisfies an FD; (2) Finding all FDs satis- fied by a relation instance; and (3) Inferring all FDs that hold in the result of a query over uncertain relations with FDs. We also give a sound and complete ax- iomatization of horizontal and vertical FDs. We look at keys as a special case of FDs. Finally, we briefly consider uncertain data that contains confidence values.