Propagating functional dependencies with conditions

ABSTRACT

The dependency propagation problem is to determine, given a view defined on data sources and a set of dependencies on the sources, whether another dependency is guaranteed to hold on the view. This paper investigates dependency propagation for recently proposed conditional functional dependencies (CFDs). The need for this study is evident in data integration, exchange and cleaning since dependencies on data sources often only hold conditionally on the view. We investigate dependency propagation for views defined in various fragments of relational algebra, CFDs as view dependencies, and for source dependencies given as either CFDs or traditional functional dependencies (FDs). (a) We establish lower and upper bounds, all matching, ranging from PTIME to undecidable. These not only provide the first results for CFD propagation, but also extend the classical work of FD propagation by giving new complexity bounds in the presence of finite domains. (b) We provide the first algorithm for computing a minimal cover of all CFDs propagated via SPC views; the algorithm has the same complexity as one of the most efficient algorithms for computing a cover of FDs propagated via a projection view, despite the increased expressive power of CFDs and SPC views. (c) We experimentally verify that the algorithm is efficient.

REFERENCES

• 1: Serge Abiteboul , Richard Hull , Victor Vianu, Foundations of Databases: The Logical Level, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1995
• 2: A. V. Aho, Y. Sagiv, and J. D. Ullman. Equivalences among relational expressions. SIAM J. Comput., 8(2):218--246, 1979.
• 3: Marianne Baudinet , Jan Chomicki , Pierre Wolper, Constraint-generating dependencies, Journal of Computer and System Sciences, v.59 n.1, p.94-115, Aug. 1999 [doi>10.1006/jcss.1999.1632]
• 4: Paul De Bra , Jan Paredaens, Conditional Dependencies for Horizontal Decompositions, Proceedings of the 10th Colloquium on Automata, Languages and Programming, p.67-82, July 18-22, 1983
• 5: Loreto Bravo , Wenfei Fan , Shuai Ma, Extending dependencies with conditions, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria
• 6: S. Davidson, W. Fan, C. Hara, and J. Qin. Propagating XML constraints to relations. In ICDE, 2003.
• 7: Ronald Fagin, Horn clauses and database dependencies, Journal of the ACM (JACM), v.29 n.4, p.952-985, Oct. 1982 [doi>10.1145/322344.322347]
• 8: Wenfei Fan , Floris Geerts , Xibei Jia , Anastasios Kementsietsidis, Conditional functional dependencies for capturing data inconsistencies, ACM Transactions on Database Systems (TODS), v.33 n.2, p.1-48, June 2008 [doi>10.1145/1366102.1366103]
• 9: P. C. Fischer, J. H. Jou, and D.-M. Tsou. Succinctness in dependency systems. TCS, 24:323--329, 1983.
• 10: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 11: Seymour Ginsburg , Sami Mohammed Zaiddan, Properties of functional-dependency families, Journal of the ACM (JACM), v.29 n.3, p.678-698, July 1982 [doi>10.1145/322326.322331]
• 12: G. Gottlob, Computing covers for embedded functional dependencies, Proceedings of the sixth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.58-69, March 23-25, 1987, San Diego, California, United States [doi>10.1145/28659.28665]
• 13: Qi He , Tok Wang Ling, Extending and inferring functional dependencies in schema transformation, Proceedings of the thirteenth ACM international conference on Information and knowledge management, November 08-13, 2004, Washington, D.C., USA [doi>10.1145/1031171.1031177]
• 14: R. Hull. Non-finite specifiability of projections of functional dependency families. TCS, 39:239--265, 1985.
• 15: A. Klug, Calculating constraints on relational expression, ACM Transactions on Database Systems (TODS), v.5 n.3, p.260-290, Sept. 1980 [doi>10.1145/320613.320615]
• 16: Anthony Klug , Rod Price, Determining View dependencies using tableaux, ACM Transactions on Database Systems (TODS), v.7 n.3, p.361-380, Sept. 1982 [doi>10.1145/319732.319738]
• 17: Phokion G. Kolaitis, Schema mappings, data exchange, and metadata management, Proceedings of the twenty-fourth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 13-15, 2005, Baltimore, Maryland [doi>10.1145/1065167.1065176]
• 18: Maurizio Lenzerini, Data integration: a theoretical perspective, Proceedings of the twenty-first ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 03-05, 2002, Madison, Wisconsin [doi>10.1145/543613.543644]
• 19: Michael J. Maher, Constrained dependencies, Theoretical Computer Science, v.173 n.1, p.113-149, Feb. 1997 [doi>10.1016/S0304-3975(96)00193-4]
• 20: Michael J. Maher , Divesh Srivastava, Chasing constrained tuple-generating dependencies, Proceedings of the fifteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.128-138, June 04-06, 1996, Montreal, Quebec, Canada [doi>10.1145/237661.237693]
• 21: Lucian Popa , Val Tannen, An Equational Chase for Path-Conjunctive Queries, Constraints, and Views, Proceedings of the 7th International Conference on Database Theory, p.39-57, January 10-12, 1999
• 22: Yehoshua Sagiv , Mihalis Yannakakis, Equivalences Among Relational Expressions with the Union and Difference Operators, Journal of the ACM (JACM), v.27 n.4, p.633-655, Oct. 1980 [doi>10.1145/322217.322221]
• 23: Abraham Silberschatz , Henry F. Korth , S. Sudershan, Database System Concepts, McGraw-Hill, Inc., New York, NY, 1998
• 24: David Toman , Grant Weddell, On reasoning about structural equality in XML: a description logic approach, Theoretical Computer Science, v.336 n.1, p.181-203, 25 May 2005 [doi>10.1016/j.tcs.2004.10.036]
• 25: D. Toman and G. E. Weddell. On keys and functional dependencies as first-class citizens in description logics. In IJCAR, 2006.
• 26: Jeffrey D. Ullman, Principles of Database Systems, W. H. Freeman & Co., New York, NY, 1983

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.1 Logical Design

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computations in finite fields
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Relational databases

General Terms:
Algorithms, Design, Management