| Title | Incorporating cardinality constraints and synonym rules into conditional functional dependencies |
| Authors | Chen, Wenguang Fan, Wenfei Ma, Shuai |
| Affiliation | Univ Edinburgh, Edinburgh EH8 9YL, Midlothian, Scotland. Peking Univ, Beijing, Peoples R China. Bell Labs, Murray Hill, NJ USA. |
| Keywords | Computational complexity Databases Specification languages DATABASES COMPLEXITY |
| Issue Date | 2009 |
| Publisher | information processing letters |
| Citation | INFORMATION PROCESSING LETTERS.2009,109,(14),783-789. |
| Abstract | We propose an extension of conditional functional dependencies (CFDs), denoted by CFD(c)s, to express cardinality constraints. domain-specific conventions, and patterns of semantically related constants in a uniform constraint formalism. We show that despite the increased expressive power, the satisfiability and implication problems for CFD(c)s remain NP-complete and coNP-complete, respectively, the same as their counterparts for CFDs. We also identify tractable special cases. (C) 2009 Elsevier B.V. All rights reserved. |
| URI | http://hdl.handle.net/20.500.11897/163259 |
| ISSN | 0020-0190 |
| DOI | 10.1016/j.ipl.2009.03.021 |
| Indexed | SCI(E) EI |
| Appears in Collections: | 待认领 |
