On Desirable Semantics of Functional Dependencies over Databases with Incomplete Information

• Autorzy: Badia A. , Lemire D.

Identyfikatory

DOI

10.3233/FI-2018-1651

• Języki publikacji: EN

Abstrakty

EN

Codd’s relational model describes just one possible world. To better cope with incomplete information, extended database models allow several possible worlds. Vague tables are one such convenient extended model where attributes accept sets of possible values (e.g., the manager is either Jill or Bob). However, conceptual database design in such cases remains an open problem. In particular, there is no canonical definition of functional dependencies (FDs) over possible worlds (e.g., each employee has just one manager). We identify several desirable properties that the semantics of such FDs should meet including Armstrong’s axioms, the independence from irrelevant attributes, seamless satisfaction and implied by strong satisfaction. We show that we can define FDs such that they have all our desirable properties over vague tables. However, we also show that no notion of FD can satisfy all our desirable properties over a more general model (disjunctive tables). Our work formalizes a trade-off between having a general model and having well-behaved FDs.

Słowa kluczowe

EN

conceptual design; database design; functional dependencies; incomplete information; relational database

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2018
• Tom: Vol. 158, nr 4
• Strony: 327--352
• Opis fizyczny: Bibliogr. 29 poz., rys., tab.

Twórcy

autor

Badia A.

• CECS Department, University of Louisville, Louisville KY 40292, USA

autor

Lemire D.

• LICEF, Université du Québec, 5800 Saint-Denis, Montreal, QC, H2S 3L5 Canada

Bibliografia

• [1] Amarilli A. The Possibility Problem for Probabilistic XML, Proceedings of the 8th Alberto Mendelzon Workshop on Foundations of Data Management (G. Gottlob, J. Pérez, Eds.), 1189, CEUR-WS.org, Cartagena de Indias, Colombia, June 2014. doi:10.3166/isi.20.5.53-75.
• [2] Badia A, and Lemire D. A call to arms: revisiting database design, SIGMOD Rec., 2011;40(3):61-69. doi:10.1145/2070736.2070750.
• [3] Badia A, and Lemire D. Functional Dependencies with null Markers, Comp. J., 2015;58(5):1160-1168. doi:10.1093/comjnl/bxu039.
• [4] Beaubouef T, and Petry F. Rough and Rough-Fuzzy Sets in Design of Information Systems, in: Computational Complexity (R. A. Meyers, Ed.), Springer, New York, NY, 2012 pp. 2702-2715. ISBN: 978-1-4614-1799-6.
• [5] Bosc P, Dubois D, and Prade H. Fuzzy functional dependencies and redundancy elimination, JASIST, 1998;49(3):217-235. doi:10.1002/(SICI)1097-4571(199803)49:3¡217::AID-ASI4¿3.0.CO;2-D.
• [6] Bosc P, Dubois D, and Prade H. Fuzzy Functional Dependencies and Redundancy Elimination, J. Am. Soc. Inf. Sci., 1998;49(3):217-235, ISSN: 0002-8231.
• [7] Bosc P, and Pivert O. On the impact of regular functional dependencies when moving to a possibilistic database framework, Fuzzy Sets and Syst., 2003;140(1):207-227. URL https://doi.org/10.1016/S0165-0114(02)00530-4.
• [8] Bosc P, and Pivert O. About projection-selection-join queries addressed to possibilistic relational databases, IEEE Trans. Fuzzy Syst., 2005;13(1):124-139. doi:10.1109/TFUZZ.2004.836070.
• [9] Bosc P, and Pivert O. Functional Dependencies Over Possibilistic Databases: An Interpretation Based on the Possible Worlds Semantics, Proceedings of the Third VLDB workshop on Management of Uncertain Data (MUD2009) in conjunction with VLDB 2009, Centre for Telematics and Information Technology (CTIT), University of Twente, The Netherlands, Lyon, France, August 2009.
• [10] Bosc P, and Pivert O. Querying Possibilistic Databases: Three Interpretations, in: Soft Computing: State of the Art Theory and Novel Applications (R. R. Yager, A. M. Abbasov, M. Z. Reformat, S. N. Shahbazova, Eds.), vol. 291 of Studies in Fuzziness and Soft Computing, Springer, Berlin Heidelberg, 2013 pp. 161-176. ISBN: 978-3-642-34921-8.
• [11] Brodie M, and Liu J. Keynote: The Power and Limits of Relational Technology in the Age of Information Ecosystems, in: On the Move to Meaningful Internet Systems, OTM 2010 (R. Meersman, T. Dillon, P. Herrero, Eds.), vol. 6427 of Lecture Notes in Computer Science, Springer, Berlin Heidelberg, 2010 pp. 706-707. ISBN: 978-3-642-16948-9.
• [12] Codd EF. Missing information (applicable and inapplicable) in relational databases, SIGMOD Rec., 1986;15(4):53-53. ISSN: 0163-5808.
• [13] Cordero P, Enciso M, Mora A, and de Guzmán IP. Rodríguez-Jiménez, J. M.: An efficient algorithm for reasoning about fuzzy functional dependencies, Advances in Computational Intelligence - 11th International Conference on Artificial Neural Networks (IWANN), Springer Berlin Heidelberg, Torremolinos, Malaga, Spain, June 8-10 2011. doi: https://doi.org/10.1007/978-3-642-21498-1_52.
• [14] Das Sarma A, Benjelloun O, Halevy A, Nabar S, and Widom, J. Representing uncertain data: models, properties, and algorithms, VLDB J., 2009;18(5):989-1019. ISSN: 1066-8888.
• [15] Hartmann S, and Link S. When data dependencies over SQL tables meet the logics of paradox and S-3, Proceedings of the twenty-ninth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, ACM New York, NY, Indianapolis, IN, June 6-11 2010 pp. 317-326. doi:10.1145/1807085.1807126.
• [16] Imieliński T. Incomplete information in logical databases, IEEE Data Eng. Bull., 1989;12(2):29-40. doi:10.1145/1634.1886.
• [17] Imieliński T, and Lipski Jr. W. Incomplete Information and Dependencies in Relational Databases, Proceedings of the 1983 ACM SIGMOD International Conference on Management of Data, ACM New York, NY, San Jose, California, May 23-26 1983 pp. 178-184. ISBN: 0-89791-104-0. doi:10.1145/971695.582222.
• [18] Karp RM, Vazirani UV, and Vazirani VV. An Optimal Algorithm for On-line Bipartite Matching, Proceedings of the Twenty-second Annual ACM Symposium on Theory of Computing, STOC ’90, ACM, New York, NY, 1990 pp. 352-358. ISBN: 0-89791-361-2. doi:10.1145/100216.100262.
• [19] Levene M, and Loizou G. The additivity problem for functional dependencies in incomplete relations, Acta Inf., 1997;34(2):135-149. doi: https://doi.org/10.1007/s002360050076.
• [20] Levene M, and Loizou G. Axiomatisation of functional dependencies in incomplete relations, Theor. Comput. Sci., 1998;206(1-2):283-300. URL https://doi.org/10.1016/S0304-3975(98)80029-7.
• [21] Levene M, and Loizou G. Database Design for Incomplete Relations, ACM Trans. Database Syst., 1999;24(1):80-126. ISSN: 0362-5915.
• [22] Link S, and Prade H. Relational Database Schema Design for Uncertain Data, Technical report, Technical Report CDMTCS-469, The University of Auckland, Auckland, Australia, 2014.
• [23] Liu JY-C, and Huang C-H. Handling Missing Data in Extended Possibility-based Fuzzy Relational Databases, Third International Conference on Innovations in Bio-Inspired Computing and Applications (IBICA), 2012, IEEE Piscataway, NJ, Kaohsiung, Taiwan, September 26-28 2012. doi:10.1109/IBICA.2012.39.
• [24] Lu A, and Ng W. Maintaining consistency of vague databases using data dependencies, Data Knowl. Eng., 2009;68(7):622-641. doi:10.1016/j.datak.2009.02.007.
• [25] Myszkorowski K. Analysis of fuzzy -ary relations with the use of interval-valued fuzzy functional dependencies, Int. J. Gen. Syst., 2013;42(6):635-658.
• [26] Qureshi M, Sharif M, and Iqbal N. Using Fuzzy Logic to Evaluate Normalization Completeness for An Improved Database Design, IJITCS, 2012;4(2):48-55. doi:10.5815/ijitcs.2012.02.07.
• [27] Raju KVSVN, Majumdar AK. Fuzzy Functional Dependencies and Lossless Join Decomposition of Fuzzy Relational Database Systems, ACM Trans. Database Syst., 1988;13(2):129-166, ISSN: 0362-5915. doi:10.1145/42338.42344.
• [28] Sarma AD, Ullman JD, and Widom J. Schema Design for Uncertain Databases, Proceedings of the 3rd Alberto Mendelzon International Workshop on Foundations of Data Management, 450, CEUR-WS.org Aachen, Arequipa, Peru, May 12-15 2009. URL http://ilpubs.stanford.edu:8090/820/.
• [29] Wu Y, and Ng W. Maintaining consistency of probabilistic databases: a linear programming approach, Conceptual Modeling-ER 2010, Springer, Berlin Heidelberg, Vancouver, BC, Canada, November 1-4, 2010 pp. 302-316. doi: https://doi.org/10.1007/978-3-642-16373-9_22.

Uwagi

Opracowanie rekordu w ramach umowy 509/P-DUN/2018 ze środków MNiSW przeznaczonych na działalność upowszechniającą naukę (2018).