Edinburgh Research Explorer

Extending Conditional Dependencies with Built-in Predicates

Research output: Contribution to journalArticle

  • Shuai Ma
  • Liang Duan
  • Wenfei Fan
  • Chunming Hu
  • Wenguang Chen

Related Edinburgh Organisations

Open Access permissions

Open

Documents

http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=7145438
Original languageEnglish
Pages (from-to)3274 - 3288
Number of pages15
JournalIEEE Transactions on Knowledge and Data Engineering
Volume27
Issue number12
DOIs
Publication statusPublished - 30 Jun 2015

Abstract

This paper proposes a natural extension of conditional functional dependencies (CFDs [1]) and conditional inclusion dependencies (CINDs [2]), denoted by CFDps and CINDps, respectively, by specifying patterns of data values with 6 ≠, <;,≤, >, and ≥ predicates. As data quality rules, CFDps and CINDps are able to capture errors that commonly arise in practice but cannot be detected by CFDs and CINDs. We establish two sets of results for central technical problems associated with CFDps and CINDps. (a) One concerns the satisfiability and implication problems for CFDps and CINDps, taken separately or together. These are important for, e.g. deciding whether data quality rules are dirty themselves, and for removing redundant rules. We show that despite the increased expressive power, the static analyses of CFDps and CINDps retain the same complexity as their CFDs and CINDs counterparts. (b) The other concerns validation of CFDps and CINDps. We show that given a set X of CFDps and CINDps on a database D, a set of SQL queries can be automatically generated that, when evaluated against D, return all tuples in D that violate some dependencies in Σ. We also experimentally verified the efficiency and effectiveness of our SQL based error detection techniques, using real-life data. This provides commercial DBMS with an immediate capability to detect errors based on CFDps and CINDps.

Download statistics

No data available

ID: 19940024