Name
Title | ||
|---|---|---|
Membership Problem For Embedded Multivalued Dependencies Under Some Restricted Conditions |
Abstract | ||
|---|---|---|
It is known that there is no finite set of inference rules that is complete for embedded multivalued dependencies. This paper considers the problem, called membership problem, of deciding whether a given embedded multivalued dependency X ↠ V on U′ (or functional dependency X → V ) is implied by a given set D of functional and embedded multivalued dependencies. A new inference rule for embedded multivalued dependencies is presented and the following results about membership problems are shown. Let U be a set of attributes and let W n ⊊…⊊ W 0 ⊊ U . Let D = F ∪ E ∪ E 1 ∪…∪ E n , where 1. (i) F is a set of functional dependencies Y → Z satisfying Y ⊆ W 0 or Z ∩ W 0 =∅, 2. (ii) E is a set of embedded multivalued dependencies Y ↠ Z on T satisfying at least one of Y ⊆ W 0 ⊆ T , Z ∩ W 0 = ∅ and ( T − Y ∪ Z )∩ W 0 =∅ and 3. (iii) each E υ 1 ⩽ i ⩽ n , is a set of embedded multivalued dependencies on W . 1. (1) If X , V ⊆ U ′ ⊆ W 0 then the membership problem is solaable, that is, it is decidable whether X ↠ V on U′ (or X → V ) is implied by D . 2. (2) If X , V ⊆ U ′ ⊆ W n then the membership problem cah be solved in O (| D |·| V − X |) time, where | D | is the size of the description of D . 3. (3) If X ⊆ W n and X , V ⊆ U ′ ⊆ W 0 then the membership problem can be solved in O (| D | 2 ·| W n − X |· Π n t =1 (| W 1 − W 1+ l |+1)) time. |
Year | DOI | Venue |
|---|---|---|
1983 | 10.1016/0304-3975(83)90143-3 | THEORETICAL COMPUTER SCIENCE |
DocType | Volume | Issue |
Journal | 22 | 1-2 |
ISSN | Citations | PageRank |
0304-3975 | 1 | 0.85 |
References | Authors | |
7 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Minoru Ito | 1 | 6 | 1.24 |
| kenichi taniguchi | 2 | 256 | 35.56 |
| Tadao Kasami | 3 | 751 | 131.11 |