Increasing the expressivity of Conditional Functional Dependencies without extra complexity

被引:27
作者
Bravo, Loreto [1 ]
Fan, Wenfei [1 ]
Geerts, Floris [1 ]
Ma, Shuai [1 ]
机构
[1] Univ Edinburgh, Sch Informat, Edinburgh EH8 9YL, Midlothian, Scotland
来源
2008 IEEE 24TH INTERNATIONAL CONFERENCE ON DATA ENGINEERING, VOLS 1-3 | 2008年
关键词
D O I
10.1109/ICDE.2008.4497460
中图分类号
TP [自动化技术、计算机技术];
学科分类号
0812 ;
摘要
The paper proposes an extension of CFDS [1], referred to as extended Conditional Functional Dependencies (eCFDS). In contrast to CFDs, CCFDS specify patterns of semantically related values in terms of disjunction and inequality, and are capable of catching inconsistencies that arise in practice but cannot be detected by CFDs. The increase in expressive power does not incur extra complexity: we show that the satisfiability and implication analyses of eCFDs remain NP -complete and CONP -complete, respectively, the same as their CFDS counterparts. In light of the intractability, we present an algorithm that approximates the maximum number of CCFDS that are satisfiable. In addition, we revise SQL techniques for detecting CFD violations, and show that violations of multiple CCFDS can be captured via a single pair of SQL queries. We also introduce an incremental SQL technique for detecting eCFD violations in response to database updates. We experimentally verify the effectiveness and efficiency of our SQL -based detection methods.
引用
收藏
页码:516 / 525
页数:10
相关论文
共 20 条
[1]  
Arenas M., 1999, PODS
[2]   Constraint-generating dependencies [J].
Baudinet, M ;
Chomicki, J ;
Wolper, P .
JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1999, 59 (01) :94-115
[3]  
Bertossi L, 2006, SIGMOD REC, V35, P68, DOI 10.1145/1147376.1147391
[4]  
Bohannon P., 2007, ICDE
[5]  
Bohannon P., 2005, SIGMOD
[6]  
Bra P. D., 1983, C AUT LANG PROGR
[7]  
BRY E, 1998, DDLP
[8]   Minimal-change integrity maintenance using tuple deletions [J].
Chomicki, J ;
Marcinkowski, J .
INFORMATION AND COMPUTATION, 2005, 197 (1-2) :90-121
[9]  
GRAHNE G., 1991, PROBLEM INCOMPLETE I
[10]   INCOMPLETE INFORMATION IN RELATIONAL DATABASES [J].
IMIELINSKI, T ;
LIPSKI, W .
JOURNAL OF THE ACM, 1984, 31 (04) :761-791