Inferring null join dependencies in relational databases |
| |
Authors: | Mark Levene George Loizou |
| |
Affiliation: | (1) Department of Computer Science, University College London, Gower Street, WC1E 6BT London, UK;(2) Department of Computer Science, Birkbeck College, Malet Street, WC1E 7HX London, UK |
| |
Abstract: | The inference problem for data dependencies in relational databases is the problem of deciding whether a set of data dependencies logically implies another data dependency. For join dependencies (JDs), the inference problem has been extensively studied by utilising the well-known chase procedure. We generalise JDs to null join dependencies (NJDs) that hold in relations which may contain null values. In our model for incomplete information we allow only a single unmarked null value denoted bynull. This allows us to solve the inference problem for NJDs by extending the chase procedure to the or-chase procedure. In order to define the or-chase procedure we generalise relations with nulls to or-relations which contain a limited form of disjunctive information. The main result of the paper shows that the inference problem for NJDs, including embedded NJDs (which are a special case of NJDs), is decidable; this is realised via the or-chase procedure. |
| |
Keywords: | H.2.1 |
本文献已被 SpringerLink 等数据库收录! |
|