skip to main content
10.1145/1055558.1055603acmconferencesArticle/Chapter ViewAbstractPublication PagespodsConference Proceedingsconference-collections
Article

Multi-valued dependencies in the presence of lists

Published: 14 June 2004 Publication History

Abstract

Multi-valued depdendencies (MVDs) are an important class of relational constraints. We axiomatise MVDs in data models that support nested list types. In order to capture different data models at a time, an abstract approach based on nested attributes is taken. The set of subattributes of some fixed nested attribute carries the structure of a co-Heyting algebra. This enables us to generalise significant features of MVDs from the relational data model to the presence of lists. It is shown that an MVD is satisfied by some instance exactly when this instance can be decomposed without loss of information. The full power of the algebraic framework allows to provide a sound and complete set of inference rules for the finite implication of MVDs in the context of lists. The presence of the list operator calls for a new inference rule which is not required in the relational data model. Further differences become apparant when the minimality of the inference rules is investigated. The extension of the relational theory of MVDs to the presence of lists allows to specify more real-world constraints and increases therefore the number of application domains.

References

[1]
S. Abiteboul, P. Buneman, and D. Suciu. Data on the Web: From Relations to Semistructured Data and XML. Morgan Kaufmann Publishers, 2000.
[2]
S. Abiteboul, R. Hull, and V. Vianu. Foundations of Databases. Addison-Wesley, 1995.
[3]
M. Arenas and L. Libkin. A normal form for XML documents. In PODS 2002. ACM, 2002.
[4]
M. Atkinson, F. Bancilhon, D. DeWitt, K. Dittrich, D. Maier, and S. Zdonik. The object-oriented database system manifesto. In Proc. of Intl. Conf. on Deductive and Object-Oriented Databases, pages 40--57, 1989.
[5]
C. Batini, S. Ceri, and S. B. Navathe. Conceptual Database Design: An Entity-Relationship Approach, Benjamin Cummings, 1992.
[6]
C. Beeri. On the membership problem for functional and multivalued dependencies in relational databases. TODS, 5(3):241--259, 1980.
[7]
C. Beeri. A formal approach to object-oriented databases. Data and Knowledge Engeneering, 5(4):353--382, 1990.
[8]
C. Beeri and P. A. Bernstein. Computational problems related to the design of normal form relational schemata. In Transactions on Database Systems, pages 30--59. ACM, 1979.
[9]
C. Beeri, R. Fagin, and J. H. Howard. A complete axiomatization for functional and multivalued dependencies in database relations. In International Conference on Management of Data, pages 47--61. ACM, 1977.
[10]
J. Biskup. On the complementation rule for multivalued dependencies in database relations. Acta Informatica, 10(3):297--305, 1978.
[11]
J. Biskup,. Database schema design theory:achievements and challenges. In International Conference on Information Systems and Management of Data, number 1066 in LNCS, pages 14--44. Springer, 1995.
[12]
J. Biskup. Achievements of relational database schema design theory revisited. In Semantics in databases, number 1358 in LNCS, pages 29 54. Springer, 1998.
[13]
F. Bry and P. Kröger. A computational biology database digest: data, data analysis, and data management. Distributed and Parallel Databases, 13(1):7--42, 2003.
[14]
P. Buneman, S. Davidson, W. Fan, C. Hara, and W. Tan. Keys for XML. In Tenth WWW Conference. IEEE, 2001.
[15]
P. P. Chen. The entity-relationship model: Towards a unified view of data. ACM Transactions Database Systems 1, pages 9--36, 1976.
[16]
P. P. Chen. English sentence structure and entity-relationship diagrams. Information Science 29, pages 127--149, 1983.
[17]
C. Delobel. Normalisation and hierarchical dependencies in the relational data model. ToDS, 3(3):201--222, 1978.
[18]
A. Dovier, A. Policriti, and G. Rossi. A uniform axiomatic view of lists, multisets, and sets, and the unification algorithm. Fundamenta Informaticae, 36(2/3):201--234, 1998.
[19]
R. Fagin. Multivalued dependencies and a new normal form for relational databases. Association for Computing Machinery, 2(3):262--278, 1977.
[20]
R. Fagin. A normal form for relational databases that is based on domains and keys. TODS, pages 387--415, 1981.
[21]
R. Fagin and M. Vardi. The theory of data dependencies: a survey. In Mathematics of Information Processing: Proceedings of Symposia in Applied Mathematics, pages 19--71. American Mathematical Society, 1986.
[22]
W. Fan and L. Libkin. On XML integrity constraints in the presence of DTDs. In PODS 2001. ACM, 2001.
[23]
W. Fan and J. Siméon. Integrity constraints for XML. In PODS 2000. ACM, 2000.
[24]
D. Fishman, D. Beech, H. Cate, and E. e. a. Chow. Iris:an object-oriented database management system. ToIS, 5(1), 1987.
[25]
Z. Galil. An almost linear-time algorithm for computing a dependency basis in a relational database. Journal of the ACM, 29(1):96--102, 1982.
[26]
G. Gardarin, J.-P. Cheiney, G. Kiernan, D. Pastre, and H. Stora. Managing complex objects in an extensible relational DBMS. In VLDB, 1989, Amsterdam, pages 55--65. Morgan Kaufmann, 1989.
[27]
G. Grahne and K. Räihä. Database decomposition into 4NF. In 9th VLDB, pages 186--196, 1983.
[28]
K. Hagihara, M. Ito, K. Taniguchi, and T. Kasami. Decision problems for multivalued dependencies in relational databases. SIAM Journal of Computation, 8(2):247--264, 1979.
[29]
S. Hartmann. Decomposing relationship types by pivoting and schema equivalence. Data & Knowledge Engineering, 39:75--99, 2001.
[30]
S. Hartmann and S. Link, More functional dependencies for XML. In Advances in Databases and Information Systems, volume 2798 of Lecture Notes in Computer Science, pages 355--369, 2003.
[31]
S. Hartmann, S. Link, and K.-D. Schewe. A new normal form for conceptual databases. In Information Modelling and Knowledge Bases XV, Frontiers in Artificial Intelligence and Applications, pages 88--105. IOS Press, 2003.
[32]
S. Hartmann, S. Link, and K.-D. Schewe. Functional dependencies in the presence of records, lists, sets and multisets. Technical Report 1/2004, Information Science Research Centre, Massey University, Department of Information Systems, Palmerston North, New Zealand, 2004.
[33]
S. Hartmann, S. Link, and K.-D. Schewe. Reasoning about functional and multi-valued dependencies in the presence of lists. In Foundations of Information and Knowledge Systems, volume 2942 of Lecture Notes in Computer Science, pages 134--154, 2004.
[34]
R. Hull and R. King. Semantic database modeling: Survey, applications and research issues. ACM Computing Surveys, 19(3), 1987.
[35]
M. Levene. The Nested Universal Relation Database Model. Springer, 1992.
[36]
J. McKinsey and A. Tarski. On closed elements in closure algebras. Annals of Mathematics, 47:122--146, 1946.
[37]
A. Mendelzon. On axiomatising multivalued dependencies in relational databases. Journal of the ACM, 26(1):37--44, 1979.
[38]
W. Y. Mok, Y. K. Ng, and D. W. Embley. A normal form for precisely charachterizing redundancy in nested relations. Transactions on Database Systems, 21:77--106, 1996.
[39]
S. Naqvi and S. Tsur. A logical language for data and knowledge bases. Computer Science Press, 1989.
[40]
Z. M. özsoyoglu and L. Y. Yuan. A new normal form for nested relations. Transactions on Database Systems, 12:111--136, 1987.
[41]
Z. M. özsoyoglu and L. Y. Yuan. Reduced mvds and minimal covers. Transactions on Database Systems, 12(3):377--394, 1987.
[42]
J. Paredaens, P. De Bra, M. Gyssens, and D. Van Gucht. The Structure of the Relational Database Model. Springer-Verlag, 1989.
[43]
J. Richardson. Supporting lists in a datamodel. In Proceeding of VLDB, pages 127--192, 1992.
[44]
Y. Sagiv. An algorithm for inferring multivalued dependencies with an application to propositional logic. Journal of the ACM, 27(2):250--262, 1980.
[45]
K.-D. Schewe and B. Thalheim. Fundamental concepts of object oriented databases. Acta Cybernetica, 11(4):49--85, 1993.
[46]
M. Scholl and H.-J. Schek. A relational object model. In Proceedings of International Conference on Database Theory (ICDT), pages 89--105. Springer Lecture Notes Series, 1990.
[47]
P. Seshadri, M. Livny, and R. Ramakrishnan. The design and implementation of sequence database system. In VLDB, Mumbai, India, 1996.
[48]
Z. Tari, J. Stokes, and S. Spaccapietra. Object normal forms and dependency constraints for object-oriented schemata. ACM ToDS, 22:513--569, 1997.
[49]
B. Thalheim. Dependencies in Relational Databases. Teubner-Verlag, 1991.
[50]
B. Thalheim. Entity-Relationship Modeling: Foundations of Database Technology. Springer-Verlag, 2000.
[51]
A. M. Tjoa and L. Berger. Transformation of requirement specifications expressed in natural language into an eer model. In Entity-Relationship Approach, volume 823 of Lecture Notes in Computer Science. Springer, 1993.
[52]
M. Y. Vardi. Fundamentals of dependency theory. In E. Börger, editor, Trends in Theoretical Computer Science, pages 171--224. Computer Science Press, 1987.
[53]
M. Vincent and J. Liu. Multivalued dependencies in XML. In BNCOD, volume 2712 of Lecture Notes in Computer Science, pages 4--18. Springer, 2003.
[54]
M. Vincent, J. Liu, and C. Liu. A redundancy free 4NF for XML. In XML Database Symposium, 2003.
[55]
M. Vincent and B. Srinivasan. Redundancy and the justification of fourth normal form in relational databases. International Journal of Foundations of Computer Science, 4(4):355--365, 1993.
[56]
M. Vincent and B. Srinivasan. Update anomalies and the justification of fourth normal form in relational databases. Information Sciences, 81:87--102, 1994.
[57]
G. Vossen. A new characterization of fd implication with an application to update anomalies. Information Processing Letters, 29:131--135, 1988.
[58]
W3C. Xml schema part 2: Datatypes. http://www.w3.org/TR/xmlschema-2/#datatype, 2001.
[59]
C. Zaniolo. Analysis and Design of Relational Schemata for Database Systems. PhD thesis, UCLA, Technical Report UCLA-ENG-7769, 1976.

Cited By

View all

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
PODS '04: Proceedings of the twenty-third ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems
June 2004
350 pages
ISBN:158113858X
DOI:10.1145/1055558
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 14 June 2004

Permissions

Request permissions for this article.

Check for updates

Qualifiers

  • Article

Conference

SIGMOD/PODS04

Acceptance Rates

Overall Acceptance Rate 642 of 2,707 submissions, 24%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)0
  • Downloads (Last 6 weeks)0
Reflects downloads up to 30 Jan 2025

Other Metrics

Citations

Cited By

View all
  • (2023)Entity integrity management under data volume, variety and veracityKnowledge and Information Systems10.1007/s10115-022-01814-165:7(2895-2934)Online publication date: 25-Jan-2023
  • (2016)Keys with Probabilistic IntervalsConceptual Modeling10.1007/978-3-319-46397-1_13(164-179)Online publication date: 7-Oct-2016
  • (2016)Possibilistic Cardinality Constraints and Functional DependenciesConceptual Modeling10.1007/978-3-319-46397-1_11(133-148)Online publication date: 7-Oct-2016
  • (2007)On inferences of full hierarchical dependenciesProceedings of the thirtieth Australasian conference on Computer science - Volume 6210.5555/1273749.1273758(69-78)Online publication date: 30-Jan-2007
  • (2007)On utilizing variables for specifying FDs in data-centric XML documentsData & Knowledge Engineering10.1016/j.datak.2006.03.00960:3(494-510)Online publication date: 1-Mar-2007
  • (2007)Full hierarchical dependencies in fixed and undetermined universesAnnals of Mathematics and Artificial Intelligence10.1007/s10472-007-9067-050:1-2(195-226)Online publication date: 1-Jun-2007
  • (2007)Unlocking keys for XML treesProceedings of the 11th international conference on Database Theory10.1007/11965893_8(104-118)Online publication date: 10-Jan-2007
  • (2006)On the logical implication of multivalued dependencies with null valuesProceedings of the Twelfth Computing: The Australasian Theory Symposium - Volume 5110.5555/2523791.2523807(113-122)Online publication date: 16-Jan-2006
  • (2006)On the logical implication of multivalued dependencies with null valuesProceedings of the 12th Computing: The Australasian Theroy Symposium - Volume 5110.5555/1151785.1151799(113-122)Online publication date: 1-Jan-2006
  • (2006)Deciding implication for functional dependencies in complex-value databasesTheoretical Computer Science10.1016/j.tcs.2006.08.005364:2(212-240)Online publication date: 6-Nov-2006
  • Show More Cited By

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media