Abstract
This paper proposes a natural extension of conditional functional dependencies (cfds [14]) and conditional inclusion dependencies (cinds [8]), denoted by cfd ps and cind ps, respectively, by specifying patterns of data values with ≠, <, ≤, > and ≥ predicates. As data quality rules, cfd ps and cind ps 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 cfd ps and cind ps. (a) One concerns the satisfiability and implication problems for cfd ps and cind ps, 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 cfd ps and cind ps retain the same complexity as their cfds and cinds counterparts. (b) The other concerns validation of cfd ps and cind ps. We show that given a set \(\it \Sigma\) of cfd ps and cind ps 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 \(\it \Sigma\). This provides commercial dbms with an immediate capability to detect errors based on cfd ps and cind ps.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Abiteboul, S., Hull, R., Vianu, V.: Foundations of Databases. Addison-Wesley, Reading (1995)
Arenas, M., Bertossi, L.E., Chomicki, J.: Consistent query answers in inconsistent databases. In: PODS (1999)
Baudinet, M., Chomicki, J., Wolper, P.: Constraint-Generating Dependencies. J. Comput. Syst. Sci. 59(1), 94–115 (1999)
Bertossi, L.E., Bravo, L., Franconi, E., Lopatenko, A.: The complexity and approximation of fixing numerical attributes in databases under integrity constraints. Inf. Syst. 33(4-5), 407–434 (2008)
Bohannon, P., Fan, W., Flaster, M., Rastogi, R.: A cost-based model and effective heuristic for repairing constraints by value modification. In: SIGMOD (2005)
Bra, P.D., Paredaens, J.: Conditional dependencies for horizontal decompositions. In: ICALP (1983)
Bravo, L., Fan, W., Geerts, F., Ma, S.: Increasing the expressivity of conditional functional dependencies without extra complexity. In: ICDE (2008)
Bravo, L., Fan, W., Ma, S.: Extending dependencies with conditions. In: VLDB (2007)
Chen, W., Fan, W., Ma, S.: Incorporating cardinality constraints and synonym rules into conditional functional dependencies. IPL 109(14), 783–789 (2009)
Chiang, F., Miller, R.J.: Discovering data quality rules. In: VLDB (2008)
Chomicki, J.: Consistent query answering: Five easy pieces. In: ICDT (2007)
Chomicki, J., Marcinkowski, J.: Minimal-change integrity maintenance using tuple deletions. Inf. Comput. 197(1-2), 90–121 (2005)
Cong, G., Fan, W., Geerts, F., Jia, X., Ma, S.: Improving data quality: Consistency and accuracy. In: VLDB (2007)
Fan, W., Geerts, F., Jia, X., Kementsietsidis, A.: Conditional functional dependencies for capturing data inconsistencies. TODS 33(2) (2008)
Fan, W., Geerts, F., Lakshmanan, L.V., Xiong, M.: Discovering conditional functional dependencies. In: ICDE (2009)
Flesca, S., Furfaro, F., Parisi, F.: Consistent query answers on numerical databases under aggregate constraints. In: Bierman, G., Koch, C. (eds.) DBPL 2005. LNCS, vol. 3774, pp. 279–294. Springer, Heidelberg (2005)
Garey, M., Johnson, D.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Company, New York (1979)
Golab, L., Karloff, H.J., Korn, F., Srivastava, D., Yu, B.: On generating near-optimal tableaux for conditional functional dependencies. In: VLDB (2008)
Maher, M.J.: Constrained dependencies. TCS 173(1), 113–149 (1997)
Maher, M.J., Srivastava, D.: Chasing Constrained Tuple-Generating Dependencies. In: PODS (1996)
Van der Meyden, R.: The complexity of querying indefinite data about linearly ordered domains. JCSS 54(1) (1997)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2009 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Chen, W., Fan, W., Ma, S. (2009). Analyses and Validation of Conditional Dependencies with Built-in Predicates. In: Bhowmick, S.S., Küng, J., Wagner, R. (eds) Database and Expert Systems Applications. DEXA 2009. Lecture Notes in Computer Science, vol 5690. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-03573-9_48
Download citation
DOI: https://doi.org/10.1007/978-3-642-03573-9_48
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-03572-2
Online ISBN: 978-3-642-03573-9
eBook Packages: Computer ScienceComputer Science (R0)