article

Free access

A new normal form for nested relations

Editor: Robert W. Taylor Authors:

Z. Meral Ozsoyoglu,

Li-Yan YuanAuthors Info & Claims

ACM Transactions on Database Systems (TODS), Volume 12, Issue 1

Pages 111 - 136

https://doi.org/10.1145/12047.13676

Published: 01 March 1987 Publication History

Abstract

We consider nested relations whose schemes are structured as trees, called scheme trees, and introduce a normal form for such relations, called the nested normal form. Given a set of attributes U, and a set of multivalued dependencies (MVDs) M over these attributes, we present an algorithm to obtain a nested normal form decomposition of U with respect to M. Such a decomposition has several desirable properties, such as explicitly representing a set of full and embedded MVDs implied by M, and being a faithful and nonredundant representation of U. Moreover, if the given set of MVDs is conflict-free, then the nested normal form decomposition is also dependency-preserving. Finally, we show that if M is conflict-free, then the set of root-to-leaf paths of scheme trees in nested normal form decomposition is precisely the unique 4NF decomposition [9, 16] of U with respect to M.

References

[1]

ABITEBOUL, S., AND B{DOIT, N. Non-first normal for relations to represent hierarchically organized data. In Proceedings o{ the 3rd A CM SIGACT/SIGMOD Symposium on Principles of Database Systems (Waterloo, Ont., Apr. 2-4, 1984), ACM, 191-200.

Digital Library

[2]

BANCILHON, F., ET AL. VERSO: A relational back end data base machine. In Proceedings of the International Workshop on Database Machines (San Diego, Calif., 1982),

[3]

BEERI, C., BERNSTEIN, P. A., AND GOODMAN, N. A sophisticate's introduction to database normalization theory. In Proceedings of the Conference on Very Large Data Bases (1978), 113- 123.

[4]

BEERI, C., FAGIN, R., AND HOWARD, J. A complete axiomatization for FDs and MVDs. In Proceedings of the International Conference on Management of Data (Toronto, Aug. 3-5, 1977), ACM, New York, 1977, 47-61.

Digital Library

[5]

BEER{, C., FAG{N, R., MAIER, D., AND YANNAKAKIS, M. On the desirability of acyclic database schemes. J. ACM 30, 3 (July 1983), 479-513.

Digital Library

[6]

BEERI, C., AND KIFER, M. Elimination of intersection anomalies from database schemes. In Proceedings of the 2nd A CM SIGACT/SIGMOD Symposium on Principles of Database Systems (Atlanta, Ga., Mar. 21-23, 1983), ACM, New York, 1983, 340-351.

Digital Library

[7]

BEERI, C., AND KIFER, M. Comprehensive approach to the design of relational database schemes. In Proceedings of the Conference on Very Large Data Bases (Singapore, Aug. 1984), 196-207.

Digital Library

[8]

COBB, E. A relational model for large shared data banks. Commun. ACM 13, 6 (June 1970), 377-387.

Digital Library

[9]

FAGIN, R. Multivalued dependencies and a new normal form for relational databases. ACM Trans. Database Syst. 2, 3 (Sept. 1977), 262-278.

Digital Library

[10]

FISCHER, P. C., AND GUCHT, D. V. Weak multivalued dependencies. In Proceedings of the 3rd ACM SIGACT/SIGMOD Symposium on Principles of Database Systems (Waterloo, Ont., Apr. 2-4, 1984), ACM, New York, 1984, 266-274.

Digital Library

[11]

FISHER, P. C., AND THOMAS, S.J. Operations for non-first-normal form relations. In Proceedings of the IEEE Computer Software and Applications Conference (Oct. 1983), IEEE, New York, 1983, 464-475.

[12]

HAWRYSZKIEWYCZ, I.T. Database Analysis and Design. SRA, 1984.

Digital Library

[13]

JAESCHKE, G., AND SCHEK, H.d. Remarks on the algebra of nonfirst normal form relations. In Proceedings of the A CM Symposium on Principles of Data Systems (Los Angeles, Calif., Mar. 29-31, 1982), ACM, New York, 1982, 124-138.

Digital Library

[14]

KAMBAYASHI, Y., TANAKA, K., AND TAKEDA, K. Synthesis of unnormalized relations incorporating more meaning. Inf. Sci. 29 (1983), 201-247.

[15]

LIEN, Y.E. Hierarchical schemata for relational databases. ACM Trans. Database Syst. 6, 1 (Mar. 1981), 48-69.

Digital Library

[16]

LIEN, Y.E. On the equivalence of database models. J. ACM 29, 2 (Apr. 1982), 333-362.

Digital Library

[17]

MAIER, D. The Theory of Relational Databases. Computer Science Press, Potomac, Md., 1983.

Digital Library

[18]

MAKINOUCHI, A. A consideration on normal form of not-necessarily-normalized relations in the relational data model. In Proceedings of the Conference on Very Large Data Bases (Tokyo, 1977), 447-453.

[19]

OzsoYOGLU, G., MATOS, V., AND OZSOYOGLU, Z.M. Extending relational algebra and relational calculus with set-valued attributes and aggregate functions. Tech. Rep., Dept. of Computer Science, Case Western Reserve Univ., 1985.

[20]

OzsoYOGLU, Z. M., AND OZSOYOGLU, G. An extension of relational algebra for summary tables. in Proceedings Statistical Database Workshop (LBL, Univ. of California, San Jose, Calif., 1983), 202-211.

Digital Library

[21]

OzsoYoGLU, Z. M., AND YUAN, L. Y. Reduced MVDs and minimal covers. Tech. Rep. CES-84-06, Dept. of Computer Science, Case Western Reserve Univ., 1984.

[22]

ROTH, M. A., KORTH, H. F., AND SILBERSCHATZ, A. Theory of non-first-normal form relational databases. TR-84-36, Dept. of Computer Science, Univ. of Texas at Austin, (Dec. 1984).

[23]

SCIORE, E. Real world MVDs. In Proceedings of the International Conference on the Management of Data (Ann Arbor, Mich., Apr. 29-May 1, 1981), ACM, New York, 1981, 121-132.

Digital Library

[24]

ULLMAN, J.D. Principles of Database Systems. Computer Science Press, Potomac, Md., 1983.

Digital Library

[25]

YUAN, L. Y., AND OZSOYOOLU, Z.M. Unifying functional and multivalued dependencies for relational database design. In Proceedings of the 5th A CM SIGACT/SIGMOD Symposium on Principles of Database Systems (Cambridge, Mass., Mar. 24-26, 1986), ACM, New York, 1986, 183-190.

Digital Library

[26]

ZANIOLA, C., AND MELKANOFF, M.A. On the design of relational database schemata. ACM Trans. Database Syst. 6, 1 (Mar. 1981), 1-47.

Digital Library

Cited By

Tansel A(2024)Temporal data modelling and integrity constraints in relational databases*International Journal of Computer Mathematics: Computer Systems Theory10.1080/23799927.2023.23000839:1(1-20)Online publication date: 31-Jan-2024
https://doi.org/10.1080/23799927.2023.2300083
Bathini AGoto KToyama M(2019)Generation of Test Cases for Testing SuperSQLProceedings of the 21st International Conference on Information Integration and Web-based Applications & Services10.1145/3366030.3366131(430-436)Online publication date: 2-Dec-2019
https://dl.acm.org/doi/10.1145/3366030.3366131
Colhon MCristea DGîfu D(2016)Discovering Semantic Relations Within NominalsLinguistic Linked Open Data10.1007/978-3-319-32942-0_6(85-100)Online publication date: 10-Apr-2016
https://doi.org/10.1007/978-3-319-32942-0_6
Show More Cited By

Index Terms

A new normal form for nested relations

Recommendations

A normal form for precisely characterizing redundancy in nested relations

We give a straightforward definition for redundancy in individual nested relations and define a new normal form that precisely characterizes redundancy for nested relations. We base our definition of redundancy on an arbitrary set of functional and ...
Theoretical and practical implications of a new definition for nested normal form
Restructuring Partitioned Normal Form Relations without Information Loss

Nested relations in partitioned normal form (PNF) are an important subclass of nested relations that are useful in many applications. In this paper we address the question of determining when every PNF relation stored under one nested relation scheme ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Database Systems

ACM Transactions on Database Systems Volume 12, Issue 1

March 1987

136 pages

ISSN:0362-5915

EISSN:1557-4644

DOI:10.1145/12047

Editor:
Robert W. Taylor

Issue’s Table of Contents

Copyright © 1987 ACM.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 March 1987

Published in TODS Volume 12, Issue 1

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

125
Total Citations
View Citations
887
Total Downloads

Downloads (Last 12 months)109
Downloads (Last 6 weeks)12

Reflects downloads up to 03 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Tansel A(2024)Temporal data modelling and integrity constraints in relational databases*International Journal of Computer Mathematics: Computer Systems Theory10.1080/23799927.2023.23000839:1(1-20)Online publication date: 31-Jan-2024
https://doi.org/10.1080/23799927.2023.2300083
Bathini AGoto KToyama M(2019)Generation of Test Cases for Testing SuperSQLProceedings of the 21st International Conference on Information Integration and Web-based Applications & Services10.1145/3366030.3366131(430-436)Online publication date: 2-Dec-2019
https://dl.acm.org/doi/10.1145/3366030.3366131
Colhon MCristea DGîfu D(2016)Discovering Semantic Relations Within NominalsLinguistic Linked Open Data10.1007/978-3-319-32942-0_6(85-100)Online publication date: 10-Apr-2016
https://doi.org/10.1007/978-3-319-32942-0_6
Olteanu DZávodný J(2015)Size Bounds for Factorised Representations of Query ResultsACM Transactions on Database Systems10.1145/265633540:1(1-44)Online publication date: 25-Mar-2015
https://dl.acm.org/doi/10.1145/2656335
Nissan E(2014)Multilingual Lexis, Semantics, and Onomasiology. Terminological Database Modelling, by Using the CuProS Metarepresentation Language: An XML-Compatible XML-Precursor Enabling Flexible Nested-Relation StructuresLanguage, Culture, Computation. Computational Linguistics and Linguistics10.1007/978-3-642-45327-4_8(122-173)Online publication date: 2014
https://doi.org/10.1007/978-3-642-45327-4_8
Nissan E(2014)Etymothesis, Fallacy, and Ontologies: An Illustration from PhytonymyLanguage, Culture, Computation. Computational Linguistics and Linguistics10.1007/978-3-642-45327-4_10(207-364)Online publication date: 2014
https://doi.org/10.1007/978-3-642-45327-4_10
Nissan EEl-Sana J(2014)A Retrospective of a Pioneering Project. Earlier Than XML, Other Than SGML, Still Going: CuProS Metadata for Deeply Nested Relations and Navigating for Retrieval in RAFFAELLOLanguage, Culture, Computation. Computing - Theory and Technology10.1007/978-3-642-45321-2_20(425-583)Online publication date: 2014
https://doi.org/10.1007/978-3-642-45321-2_20
Sali ASchewe K(2011)Weak functional dependencies on trees with restructuringActa Cybernetica10.14232/actacyb.20.2.2011.520:2(285-329)Online publication date: 1-Feb-2011
https://dl.acm.org/doi/10.14232/actacyb.20.2.2011.5
Nissan ENissan E(2011)Accounting for Social, Spatial, and Textual InterconnectionsComputer Applications for Handling Legal Evidence, Police Investigation and Case Argumentation10.1007/978-90-481-8990-8_6(483-765)Online publication date: 24-Oct-2011
https://doi.org/10.1007/978-90-481-8990-8_6
Benedikt MSenellart P(2011)DatabasesComputer Science10.1007/978-1-4614-1168-0_10(169-229)Online publication date: 22-Oct-2011
https://doi.org/10.1007/978-1-4614-1168-0_10
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

Figures

Tables

Media

View Issue’s Table of Contents