More Web Proxy on the site http://driver.im/

Article

Free access

Functional dependencies on cyclic database schemes

Authors:

Alberto O. Mendelzon,

Marc H. GrahamAuthors Info & Claims

SIGMOD '83: Proceedings of the 1983 ACM SIGMOD international conference on Management of data

Pages 79 - 91

https://doi.org/10.1145/582192.582208

Published: 01 May 1983 Publication History

Abstract

We study how functional dependencies affect the cyclicity of a database scheme; in particular, when does a set of functional dependencies make a cyclic database scheme behave like an acyclic one.A database scheme is fd-acyclic if every pairwise-consistent database state that satisfies the fd's is join-consistent. We give a simple characterization of fd-acyclicity over a restricted class of database schemes. We then give a tableau-based characterization for the general case that leads to an algorithm for testing fd-acyclicity. This algorithm actually solves the more general problem of query equivalence under functional dependencies and typed inclusion dependencies.

References

[1]

{ASU} Aho, A., Sagiv, Y., Ullman, J., "Equivalences Among Relational Expressions", SIAM J. Comp. 8,2 (1979), pp. 218--246.

[2]

{B+} Beeri, C., Fagin, R., Maier, D., Mendelzon, A.O., Ullman, J.D., Yannakakis, M., "Properties of Acyclic Database Schemes", Proc. 13th Ann. ACM Symp. Theory of Comp., (1981).

Digital Library

[3]

{BFMY} Beeri, C., Fagin, R., Maier, D., Yannakakis, M., "On The Desirable Properties of Acyclic Database Schemas", IBM Report RJ3131, San Jose, Calif., 1981.

[4]

{BG} Bernstein, P.A., Goodman, N., "The Power of Natural Semi-Joins", Siam J. of Comp., 10,4, (1981).

[5]

{CFP} Casanova, M.A., Fagin, R., Papadimitriou, C.H., "Inclusion Dependencies and Their Interaction with Functional Dependencies", Proc. First ACM SIGACT-SIGMOD Conf. on Principles of Database Systems (1982), pp. 171--176.

Digital Library

[6]

{CM} Chan, E., Mendelzon, A.O., "Separable and Independent Database Schemes", to appear, Second ACM SIGACT-SIGMOD Conf. on Principles of Database Systems, 1983.

Digital Library

[7]

{F1} Fagin, R., "Horn Clauses and Data Dependencies", JACM 29, 4 (1982), pp. 952--985.

Digital Library

[8]

{F2} Fagin, R., "Multivalued Dependencies and a New Normal Norm for Relational Databases", ACM Trans. Database Syst., 2,3 (1977), pp. 262--278.

Digital Library

[9]

{FMU} Fagin, R., Mendelzon, A.O., Ullman, J.D., "A Simplified Universal Relation Assumption and its Properties", ACM Trans. Database Syst., 7,3 (1982), pp. 343--360.

Digital Library

[10]

{G} Graham, M.H., "Satisfying Database States", Ph.D. thesis, University of Toronto, Dept. of Computer Science, 1981.

Digital Library

[11]

{GM} Graham, M., Mendelzon, A.O., "Strong Equivalence of Relational Expressions Under Dependencies", Infor. Proc. Letters, 14,2, (1982), pp. 57--62.

[12]

{GS} Goodman, N., Shmueli, O., "Tree Queries: A Simple Class of Relational Queries", ACM Trans. Database Syst., 7,4 (1982), pp. 653--677.

Digital Library

[13]

{GS2} Goodman, N., Shmueli, O., "Limitations of the Chase", Infor. Proc. Letters, 13,4 (1982), pp. 154--157.

[14]

{GY} Graham, M., Yannakakis, M., "Independent Database Schemes", Proc. First ACM SIGACT-SIGMOD Conf. on Principles of Database Systems (1982), pp. 199--205.

Digital Library

[15]

{H} Honeyman, P., "Testing Satisfaction of Functional Dependencies", JACM 29,3 (1982), pp. 668--677.

Digital Library

[16]

{JK} Johnson, D.S., Klug,A., "Testing Containment of Conjunctive Queries under Functional and Inclusion Dependencies", Proc. First ACM SIGACT-SIGMOD Conf. on Principles of Database Systems (1982), pp. 164--169.

Digital Library

[17]

{K} Katsumo, H., "A Desirable Class of Sets Of FD's and MVD's", NTT Technical Report, Japan, (1982).

[18]

{L} Laver, K., Forthcoming Ph.D. dissertation, Univ. of Toronto.

[19]

{MMS} Maier, D., Mendelzon, A.O., Sagiv, Y., "Testing Implications of Data Dependencies", ACM Trans. Database Syst., 4,4 (1979), pp. 455--469.

Digital Library

[20]

{S} Sagiv, Y., "Can we use the universal instance assumption without using nulls?", Proc. ACM-SIGMOD 1981 International Conf. on Management of Data (1981), pp. 108--120.

Digital Library

[21]

{U} Ullman, J.D., "Principles of Database Systems", Computer Science Press, 2nd ed., (1982).

Digital Library

[22]

{V} Vassiliou, Y., "A Formal Treatment of Imperfect Information in Database Management", Ph.D thesis, Univ. of Toronto, (1980).

Digital Library

Cited By

Fagin RVardi M(2005)The theory of data dependencies — An overviewAutomata, Languages and Programming10.1007/3-540-13345-3_1(1-22)Online publication date: 28-May-2005
https://doi.org/10.1007/3-540-13345-3_1
Sagiv YShmueli O(1993)Solving queries by tree projectionsACM Transactions on Database Systems10.1145/155271.15527718:3(487-511)Online publication date: 1-Sep-1993
https://dl.acm.org/doi/10.1145/155271.155277
Sagiv YSilberschatz A(1985)Sagiv,Y-On finite FD-acyclicityProceedings of the fifth ACM SIGACT-SIGMOD symposium on Principles of database systems10.1145/6012.15422(173-182)Online publication date: 1-Jun-1985
https://dl.acm.org/doi/10.1145/6012.15422
Show More Cited By

Recommendations

Functional dependencies on cyclic database schemes

We study how functional dependencies affect the cyclicity of a database scheme; in particular, when does a set of functional dependencies make a cyclic database scheme behave like an acyclic one.A database scheme is fd-acyclic if every pairwise-...
On the boundedness of relational database schemes with respect to functional dependencies
A complete axiomatization for functional and multivalued dependencies in database relations
SIGMOD '77: Proceedings of the 1977 ACM SIGMOD international conference on Management of data

We investigate the inference rules that can be applied to functional and multivalued dependencies that exist in a database relation. Three types of rules are discussed. First, we list the well known rules for functional dependencies. Then we investigate ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SIGMOD '83: Proceedings of the 1983 ACM SIGMOD international conference on Management of data

May 1983

252 pages

ISBN:0897911040

DOI:10.1145/582192

Conference Chair:
Michael Stonebraker
University of California, Berkeley, CA

ACM SIGMOD Record Volume 13, Issue 4
May 1983
245 pages
ISSN:0163-5808
DOI:10.1145/971695
Issue’s Table of Contents

Copyright © 1983 ACM.

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

SIGMOD: ACM Special Interest Group on Management of Data
IEEE TC on Design Automation
ACM SIGBDP
IEEE TC on VLSI
IEEE TC on Database Engineering

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 May 1983

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Acceptance Rates

Overall Acceptance Rate 785 of 4,003 submissions, 20%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

10
Total Citations
View Citations
475
Total Downloads

Downloads (Last 12 months)89
Downloads (Last 6 weeks)17

Reflects downloads up to 11 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Fagin RVardi M(2005)The theory of data dependencies — An overviewAutomata, Languages and Programming10.1007/3-540-13345-3_1(1-22)Online publication date: 28-May-2005
https://doi.org/10.1007/3-540-13345-3_1
Sagiv YShmueli O(1993)Solving queries by tree projectionsACM Transactions on Database Systems10.1145/155271.15527718:3(487-511)Online publication date: 1-Sep-1993
https://dl.acm.org/doi/10.1145/155271.155277
Sagiv YSilberschatz A(1985)Sagiv,Y-On finite FD-acyclicityProceedings of the fifth ACM SIGACT-SIGMOD symposium on Principles of database systems10.1145/6012.15422(173-182)Online publication date: 1-Jun-1985
https://dl.acm.org/doi/10.1145/6012.15422
Sagiv YShmueli OSilberschatz A(1985)The equivalence of solving queries and producing tree projections (extended abstract)Proceedings of the fifth ACM SIGACT-SIGMOD symposium on Principles of database systems10.1145/6012.15413(160-172)Online publication date: 1-Jun-1985
https://dl.acm.org/doi/10.1145/6012.15413
Cosmadakis SKanellakis PSedgewick R(1985)Equational theories and database constraintsProceedings of the seventeenth annual ACM symposium on Theory of computing10.1145/22145.22176(273-284)Online publication date: 1-Dec-1985
https://dl.acm.org/doi/10.1145/22145.22176
Cosmadakis SKanellakis PRosenkrantz DFagin R(1984)Functional and inclusion dependencies a graph theoretic approachProceedings of the 3rd ACM SIGACT-SIGMOD symposium on Principles of database systems10.1145/588011.588016(29-37)Online publication date: 2-Apr-1984
https://dl.acm.org/doi/10.1145/588011.588016
Sacca DMaufredi FMecchia ARosenkrantz DFagin R(1984)Properties of database schemata with functional dependenciesProceedings of the 3rd ACM SIGACT-SIGMOD symposium on Principles of database systems10.1145/588011.588015(19-28)Online publication date: 2-Apr-1984
https://dl.acm.org/doi/10.1145/588011.588015
D'Atri AMoscarini MRosenkrantz DFagin R(1984)On the recognition and design of acyclic databasesProceedings of the 3rd ACM SIGACT-SIGMOD symposium on Principles of database systems10.1145/588011.588013(1-8)Online publication date: 2-Apr-1984
https://dl.acm.org/doi/10.1145/588011.588013
KANELLAKIS P(1990)Elements of Relational Database TheoryFormal Models and Semantics10.1016/B978-0-444-88074-1.50022-6(1073-1156)Online publication date: 1990
https://doi.org/10.1016/B978-0-444-88074-1.50022-6
(1986)Invited Paper referencesRelational Databases10.1016/B978-0-08-034094-4.50022-X(273-289)Online publication date: 1986
https://doi.org/10.1016/B978-0-08-034094-4.50022-X

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 Publication

Media

Figures

Other

Tables

View Table of Contents