[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ skip to main content
10.1145/567752.567763acmconferencesArticle/Chapter ViewAbstractPublication PagespoplConference Proceedingsconference-collections
Article
Free access

Universality of data retrieval languages

Published: 01 January 1979 Publication History

Abstract

We consider the question of how powerful a relational query language should be and state two principles that we feel any query language should satisfy. We show that although relational algebra and relational calculus satisfy these principles, there are certain queries involving least fixed points that cannot be expressed by these languages, yet that also satisfy the principles. We then consider various extensions of relational algebra to enable it to answer such queries. Finally, we discuss our extensions to relational algebra in terms of a new programming language oriented model for queries.

References

[1]
{AHU} A. V. Aho, J. E. Hopcroft, and J. D. Ullman, The Design and Analysis of Computer Algorithms, Addison-Wesley, Reading, Mass., 1974.
[2]
{ASU} A. V. Aho, Y. Sagiv, and J. D. Ullman, "Equivalences Among Relational Expressions," SIAM J. Computing, 1978.
[3]
{B} F. Bancilhon, "On the completeness of query languages for relational expressions," Rapport de Recherche No. 297, IRIA, Rocquencourt, France, May, 1978.
[4]
{C1} E. F. Codd, "A Relational Model for Large Shared Data Banks," Comm. ACM13:6 (June, 1970), 377-387.
[5]
{C2} E. F. Codd, "Relational Completeness of Data Base Sublanguages," in Data Base Systems (R. Rustin, ed.), Prentice-Hall, Englewood Cliffs, N. J., 1972, pp. 65-98.
[6]
{Ch} A. Church, Introduction to Mathematical Logic, Vol. 1, Princeton University Press, 1956.
[7]
{CM} A. K. Chandra and P. M. Merlin, "Optimal Implementation of Conjunctive Queries in Relational Data Bases," Proc. Ninth Annual ACM Symposium on Theory of Computing, May 1976, pp. 77-90.
[8]
{D} C. J. Date, An Introduction to Database Systems, Addison-Wesley, Reading, Mass., 1975.
[9]
{HU} J. E. Hopcroft and J. D. Ullman, Formal Languages and their Relation to Automata, Addison-Wesley, Reading, Mass., 1969.
[10]
{P} J. Paredaena, Information Processing Letters 7:2, 1978.
[11]
{S} C. P. Schnorr, "An Algorithm for Transitive Closure with Linear Expected Time," SIAM J. Computing7:2 (May, 1978), 127-133.
[12]
{SC} J. M. Smith and P. Y.-T. Chang, "Optimizing the Performance of a Relational Algebra Database Interface," Comm. ACM18:10 (Oct., 1975), 568-579.
[13]
{SY} Y. Sagiv and M. Yannikakis, "Equivalence Among Relational Expressions with the Union and Difference Operations," Proc. ACM International Conference on Very Large Data Bases, Sept., 1978.
[14]
{T} A. Tarski, "A Lattice-Theoretical Fixpoint Theorem and its Applications," Pacific J. Mathematics5:2 (June, 1955), 285-309.
[15]
{Z} M. M. Zloof, "Query-by-Example: a Database Language," IBM Syst. J.,16:4 (1977), pp. 324-343.

Cited By

View all
  • (2024)On Undecidability of Unary Nonnested PFP Operators for One Successor Function TheoryRussian Mathematics10.3103/S1066369X2470030068:4(79-82)Online publication date: 6-Aug-2024
  • (2024)On undecidability of unary non-nested PFP-operators for one successor function theoryIzvestiya Vysshikh Uchebnykh Zavedenii. Matematika10.26907/0021-3446-2024-4-89-93(89-93)Online publication date: 24-Apr-2024
  • (2024)Efficient Enumeration of Recursive Plans in Transformation-Based Query OptimizersProceedings of the VLDB Endowment10.14778/3681954.368198617:11(3095-3108)Online publication date: 1-Jul-2024
  • Show More Cited By
  1. Universality of data retrieval languages

      Recommendations

      Comments

      Please enable JavaScript to view thecomments powered by Disqus.

      Information & Contributors

      Information

      Published In

      cover image ACM Conferences
      POPL '79: Proceedings of the 6th ACM SIGACT-SIGPLAN symposium on Principles of programming languages
      January 1979
      290 pages
      ISBN:9781450373579
      DOI:10.1145/567752
      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: 01 January 1979

      Permissions

      Request permissions for this article.

      Check for updates

      Qualifiers

      • Article

      Acceptance Rates

      POPL '79 Paper Acceptance Rate 27 of 146 submissions, 18%;
      Overall Acceptance Rate 824 of 4,130 submissions, 20%

      Upcoming Conference

      POPL '25

      Contributors

      Other Metrics

      Bibliometrics & Citations

      Bibliometrics

      Article Metrics

      • Downloads (Last 12 months)273
      • Downloads (Last 6 weeks)19
      Reflects downloads up to 11 Dec 2024

      Other Metrics

      Citations

      Cited By

      View all
      • (2024)On Undecidability of Unary Nonnested PFP Operators for One Successor Function TheoryRussian Mathematics10.3103/S1066369X2470030068:4(79-82)Online publication date: 6-Aug-2024
      • (2024)On undecidability of unary non-nested PFP-operators for one successor function theoryIzvestiya Vysshikh Uchebnykh Zavedenii. Matematika10.26907/0021-3446-2024-4-89-93(89-93)Online publication date: 24-Apr-2024
      • (2024)Efficient Enumeration of Recursive Plans in Transformation-Based Query OptimizersProceedings of the VLDB Endowment10.14778/3681954.368198617:11(3095-3108)Online publication date: 1-Jul-2024
      • (2024)A Fast Plan Enumerator for Recursive Queries2024 IEEE 40th International Conference on Data Engineering (ICDE)10.1109/ICDE60146.2024.00425(5449-5452)Online publication date: 13-May-2024
      • (2024)Definitions and Computational Properties of OCL: A Systematic ReviewIEEE Access10.1109/ACCESS.2024.342886512(99704-99738)Online publication date: 2024
      • (2024)Evaluating regular path queries on compressed adjacency matricesThe VLDB Journal10.1007/s00778-024-00885-634:1Online publication date: 26-Nov-2024
      • (2023)Accelerating Deformable Convolution Networks with Dynamic and Irregular Memory AccessesACM Transactions on Design Automation of Electronic Systems10.1145/359743128:4(1-23)Online publication date: 18-Jul-2023
      • (2023)What-is and How-to for Fairness in Machine Learning: A Survey, Reflection, and PerspectiveACM Computing Surveys10.1145/359719955:13s(1-37)Online publication date: 13-Jul-2023
      • (2023)Affective Corners as a Problematic for Design InteractionsACM Transactions on Human-Robot Interaction10.1145/359645212:4(1-9)Online publication date: 23-Jun-2023
      • (2023)A Derivative-based Parser Generator for Visibly Pushdown GrammarsACM Transactions on Programming Languages and Systems10.1145/359147245:2(1-68)Online publication date: 15-May-2023
      • Show More Cited By

      View Options

      View options

      PDF

      View or Download as a PDF file.

      PDF

      eReader

      View online with eReader.

      eReader

      Login options

      Media

      Figures

      Other

      Tables

      Share

      Share

      Share this Publication link

      Share on social media