article

Free access

Testing implications of data dependencies

Editor: David K. Hsiao Authors:

Alberto O. Mendelzon,

Yehoshua SagivAuthors Info & Claims

ACM Transactions on Database Systems (TODS), Volume 4, Issue 4

Pages 455 - 469

https://doi.org/10.1145/320107.320115

Published: 01 December 1979 Publication History

Abstract

Presented is a computation method—the chase—for testing implication of data dependencies by a set of data dependencies. The chase operates on tableaux similar to those of Aho, Sagiv, and Ullman. The chase includes previous tableau computation methods as special cases. By interpreting tableaux alternately as mappings or as templates for relations, it is possible to test implication of join dependencies (including multivalued dependencies) and functional dependencies by a set of dependencies.

References

[1]

AHO, A.V., BEERI, C., AND ULLMAN, J.D. The theory of joins in relational databases. Proc. 18th Syrup. on Foundations of Computer Science, Providence, R.I., 1977, pp. 107-113.

[2]

AHO, A,V, SAGIV, Y., AND ULLMA~, J.D. Equivalence of relational expressions. SIAM J. Comping. 8, 2 (May 1979), 218-246.

[3]

ARMSTRONG, W.W. Dependency structures of data base relationships. Proc. IFIP '74, North- Holland Pub. Co., Amsterdam, 1974, pp. 580-583.

[4]

BEERI, C. On the membership problem for multivalued dependencies in relational databases. Tech. Rep. 229, Dept. Elec. Eng. and Comptr. Sci., Princeton U., Princeton, N.J., 1977.

[5]

BEERI, C. On the role of data dependencies in the construction of relational database schemas. Tech. Rep. 43, Dept. Comptr. Sci., The Hebrew University, Jerusalem, Israel, 1979.

[6]

BEERI, C., BERNSTEIN, P., AND GOODMAN, N. A sophisticate's introduction to database normalization theory. Proc. 4th Int. Conf. on Very Large Data Bases, West Berlin, 1978, pp. 113-124.

[7]

BEERI, C., FAt}IN, R., AND HOWARD, J. A complete axiomatization for functional and multivalued dependencies. Proc. ACM-SIGMOD Conf., Toronto, Canada, 1977, pp. 47-61.

Digital Library

[8]

BEERI, C., MENDELZON, A.O., SAGIV, Y., AND ULLMAN, J.D. Equivalence of relational database schemes. Proc. 11th ACM Syrup. on Theory of Computing, Atlanta, Ga., 1979, pp. 319-329. See also Tech. Rep. 252, Dept. Elec. Eng. and Comptr. Sci., Princeton U., Princeton, N.J., 1978.

Digital Library

[9]

BERNSTEIN, P.A. Synthesizing third normal form relations from functional dependencies. ACM Trans. Database Syst. I, 4 (Dec. 1976), 277-298.

Digital Library

[10]

CHANDRA, A.K., AND M~RLIN, P.M. Optimal implementation of conjunctive queries in relational databases. Proc. 9th Ann. ACM Syrup. on Theory of Computing, Boulder, Colo., 1976, pp. 77-90.

Digital Library

[11]

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

Digital Library

[12]

DELOBEL, C. Contributions theoretiques a-la conception et a l'evaluation d'un systeme d'informations applique a la gestion. These d'Etat, U. of Grenoble, Grenoble, France, 1973.

[13]

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

Digital Library

[14]

FAGIN, R. Normal forms and relational database operators. Proc. ACM-SIGMOD Conf., Boston, Mass., 1979, pp. 153-160.

Digital Library

[15]

HAGIHARA, K., Iwo, M., TANIGUCHI, K., AND KASAMI, T. Decision problems for multivalued dependencies in relational databases. SIAM J. Comptng. 8, 2 (May 1979), 247-264.

[16]

MAIER, D., MENDELZON, A.O., SADRI, F., AND ULLMAN, J.D. Adequacy of decompositions of relational databases. Unpub. manuscript.

[17]

RISSANEN, J. Independent components of relations.ACM Trans. Database Syst. 2, 4 (Dec. 1977), 317-325.

Digital Library

[18]

RISSANEN, J. Theory of relations for databases--a tutorial survey. Proc. 7th Syrup. on Mathematical Foundations of Computer Science, Lecture Notes in Computer Science 64, Springer- Verlag, 1978, pp. 536-551.

[19]

SAGIV, Y. An algorithm for inferring multivalued dependencies that works also for a subclass of propositional logic. Rep. UIUCDCS-R-79-954, Dept. Comptr. Sci., U. of Illinois, Urbana-Champaign, Ill., 1979.

[20]

ZANIOLO, C. Analysis and design of relational schemata for database systems. Tech. Rep. UCLA- ENG-7769, Ph.D. Th., Dept. Comptr. Sci., U. of California, Los Angeles, Calif., 1976.

Digital Library

Cited By

Hanisch PKrötzsch M(2024)Chase Termination Beyond Polynomial TimeProceedings of the ACM on Management of Data10.1145/36515942:2(1-17)Online publication date: 14-May-2024
https://dl.acm.org/doi/10.1145/3651594
Kimelfeld BKolaitis P(2024)A Unifying Framework for Incompleteness, Inconsistency, and Uncertainty in DatabasesCommunications of the ACM10.1145/362471767:3(74-83)Online publication date: 22-Feb-2024
https://dl.acm.org/doi/10.1145/3624717
Auge TFeistel SEkaputra FKlettke MJürgensmann SMichels EWaltersdorfer L(2024)Towards an Integrated Provenance Framework: A Scenario for Marine Data2024 IEEE European Symposium on Security and Privacy Workshops (EuroS&PW)10.1109/EuroSPW61312.2024.00071(597-601)Online publication date: 8-Jul-2024
https://doi.org/10.1109/EuroSPW61312.2024.00071
Show More Cited By

Index Terms

Testing implications of data dependencies
1. Information systems
  1. Data management systems
    1. Database design and models
      1. Relational database model
    2. Query languages
      1. Relational database query languages

Recommendations

On improving dependency implication algorithms
Data dependencies for query optimization: a survey
Abstract
Effective query optimization is a core feature of any database management system. While most query optimization techniques make use of simple metadata, such as cardinalities and other basic statistics, other optimization techniques are based on ...
On the design of relational database schemata

The purpose of this paper is to present a new approach to the conceptual design of relational databases based on the complete relatability conditions (CRCs).

It is shown that current database design methodology based upon the elimination of anomalies is ...

Comments

Information & Contributors

Information

Published In

Copyright © 1979 ACM.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 December 1979

Published in TODS Volume 4, Issue 4

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

524
Total Citations
View Citations
1,345
Total Downloads

Downloads (Last 12 months)117
Downloads (Last 6 weeks)19

Reflects downloads up to 06 Oct 2024

Other Metrics

View Author Metrics

Citations

Cited By

Hanisch PKrötzsch M(2024)Chase Termination Beyond Polynomial TimeProceedings of the ACM on Management of Data10.1145/36515942:2(1-17)Online publication date: 14-May-2024
https://dl.acm.org/doi/10.1145/3651594
Kimelfeld BKolaitis P(2024)A Unifying Framework for Incompleteness, Inconsistency, and Uncertainty in DatabasesCommunications of the ACM10.1145/362471767:3(74-83)Online publication date: 22-Feb-2024
https://dl.acm.org/doi/10.1145/3624717
Auge TFeistel SEkaputra FKlettke MJürgensmann SMichels EWaltersdorfer L(2024)Towards an Integrated Provenance Framework: A Scenario for Marine Data2024 IEEE European Symposium on Security and Privacy Workshops (EuroS&PW)10.1109/EuroSPW61312.2024.00071(597-601)Online publication date: 8-Jul-2024
https://doi.org/10.1109/EuroSPW61312.2024.00071
Baldazzi TBellomarini LFavorito MSallinger E(2024)Ontological Reasoning over Shy and Warded Datalog+/– for Streaming-Based ArchitecturesPractical Aspects of Declarative Languages10.1007/978-3-031-52038-9_11(169-185)Online publication date: 15-Jan-2024
https://dl.acm.org/doi/10.1007/978-3-031-52038-9_11
Zykin S(2023)Testing Dependencies and Inference Rules in DatabasesAutomatic Control and Computer Sciences10.3103/S014641162307017957:7(788-802)Online publication date: 1-Dec-2023
https://dl.acm.org/doi/10.3103/S0146411623070179
Calautti MMilani MPieris A(2023)Semi-Oblivious Chase Termination for Linear Existential Rules: An Experimental StudyProceedings of the VLDB Endowment10.14778/3611479.361149316:11(2858-2870)Online publication date: 24-Aug-2023
https://dl.acm.org/doi/10.14778/3611479.3611493
Anwar MWang ALan FCaesar MSchulzrinne HKohler EMaltz DMisra V(2023)Demo: Structural Network Minimization: A Case of Reflective NetworkingProceedings of the ACM SIGCOMM 2023 Conference10.1145/3603269.3610847(1188-1190)Online publication date: 10-Sep-2023
https://dl.acm.org/doi/10.1145/3603269.3610847
Khan ATamani NJaouhari SMroueh L(2023)A Contextual Derivation Algorithm for Cybersecurity in IoT Environments2023 IEEE 22nd International Conference on Trust, Security and Privacy in Computing and Communications (TrustCom)10.1109/TrustCom60117.2023.00195(1430-1435)Online publication date: 1-Nov-2023
https://doi.org/10.1109/TrustCom60117.2023.00195
Wang AAnwar MLan FCaesar M(2023)Structural Semantics Management: an Application of the Chase in Networking2023 31st International Symposium on Modeling, Analysis, and Simulation of Computer and Telecommunication Systems (MASCOTS)10.1109/MASCOTS59514.2023.10387636(1-4)Online publication date: 16-Oct-2023
https://doi.org/10.1109/MASCOTS59514.2023.10387636
Kumar ASoffer PTsoury A(2023)Normalizing object-centric process logs by applying database principlesInformation Systems10.1016/j.is.2023.102196115(102196)Online publication date: May-2023
https://doi.org/10.1016/j.is.2023.102196
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Get Access

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

Media

Figures

Other

Tables

View Issue’s Table of Contents