article

Free access

On the completeness of object-creating database transformation languages

Authors:

Jan Van Den Bussche,

Dirk Van Gucht,

Marc GyssensAuthors Info & Claims

Journal of the ACM (JACM), Volume 44, Issue 2

Pages 272 - 319

https://doi.org/10.1145/256303.256311

Published: 01 March 1997 Publication History

Abstract

Object-oriented applications of database systems require database transformations involoving nonstandard functionalities such as set manipulation and object creation, that is, the introduction of new domain elements. To deal with thse functionalities, Abiteboul and Kanellakis [1989] introduced the “determinate” transformations as a generalization of the standard domain-preserving transformations. The obvious extensions of complete standard database programming languages, however, are not complete for the determinate transformations. To remedy this mismatch, the “constructive” transformations are proposed. It is shown that the constructive transformations are precisely the transformations that can be expressed in said extensions of complete standard languages. Thereto, a close correspondence between object creation and the construction of hereditarily finite sets is established.

A restricted version of the main completeness result for the case where only list manipulations are involved is also presented.

References

[1]

ABITEBOUL, S., HULL, R., AND VIANU, V. 1994. Foundations of Databases. Addison-Wesley, Reading, Mass.

[2]

ABITEBOUL, S., AND KANELLAKIS, P. 1989. Object identity as a query language primitive. In Proceedings of the 1989 A CM SIGMOD International Conference on the Management of Data, J. Clifford, B. Lindsay, and D. Maier, eds. (Portland, Ore., May 31-June 2). SIGMOD Record, vol. 18, No. 2. ACM Press, New York, pp. 159-173. Also INRIA Rapport de Recherche 1022, 1989.

[3]

ABITEBOUL, S., AND VIANU, V. 1990. Procedural languages for database queries and updates. J. Comput. Syst. Sci. 41, 2, 181-229.

[4]

ABITEBOUL, S., AND VIANU, g. 1991. Datalog extensions for database queries and updates. J. Comput. Syst. Sci. 43, 1, 62-124.

[5]

AHO, A. V., AND ULLMAN, J.D. 1979. Universality of data retrieval languages. In Proceedings of the 6th Annual ACM Symposium on Principles of Programming Languages. ACM, New York, pp. 110-120.

[6]

ANDRIES, M., AND PAREDAENS, J. 1996. On instance-completeness of database query languages involving object creation. J. Comput. Syst. Sci. 52, 2, 357-373.

[7]

BANCILHON, F. 1978. On the completeness of query languages for relational data bases. In Proceedings of the 7th Symposium on Mathematical Foundations of Computer Science. Lecture Notes in Computer Science, vol. 64. Springer-Verlag, New York, pp. 112-123.

[8]

BARWISE, J. 1975. Admissible Sets and Structures. Springer-Verlag, New York.

[9]

BEERI, C. 1990. A formal approach to object-oriented databases. Data Knowl. Eng. 5, 4, 353-382.

[10]

CHANDRA, A., AND HAREL, D. 1980. Computable queries for relational database systems. J. Comput. Syst. Sci. 21, 2, 156-178.

[11]

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

[12]

CODD, E. 1972a. Further normalization of the data base relational model. In Data Base Systems, R. Rustin, ed. Prentice-Hall, Englewood Cliffs, N.J., pp. 33-64.

[13]

CODD, E. 1972b. Relational completeness of data base sublanguages. In Data Base Systems, R. Rustin, ed. Prentice-Hall, Englewood Cliffs, N. J., pp. 65-98.

[14]

DAHLHAUS, E., AND MAKOWSKY, J.A. 1986. The choice of programming primitives for SETL-like programming languages. In Proceedings ESOP'86, B. Robinet and R. Wilhelm, eds. Lecture Notes in Computer Science, vol. 213. Springer-Verlag, New York, pp. 162-172.

[15]

DAHLHAUS, E., AND MAKOWSKY, J. A. 1992. Query languages for hierarchic databases. Inf. Comput. 101, 1, 1-32.

[16]

DENNINGHOFF, K., AND VIANU, V. 1993. Database method schemas and object creation. In Proceedings 12th ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (Washington, D.C., May 25-28). ACM Press, New York, pp. 265-275.

[17]

GAIFMAN, H., AND VARDI, M. Y. 1985. A simple proof that connectivity is not first-order definable. Bull EATCS, 26, 43-45.

[18]

GYSSENS, M., PAREDAENS, J., VAN DEN BUSSCHE, J., AND VAN GUCHT, D. 1994. A graph-oriented object database model. IEEE Trans. Knowl. Data Eng. 6, 4, 572-586.

[19]

GYSSENS, M., PAREDAENS, J., AND VAN GUCHT, D. 1990. A graph-oriented object database model. In Proceedings of the 9th ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (Nashville, Tenn., April 2-4). ACM, New York, pp. 417-424.

[20]

FAGIN, R. 1975. Monadic generalized spectra. Z. Mathe. Logik Grund. Math. 21, 89-96.

[21]

HULL, R., AND SU, J. 1993. Algebraic and calculus query languages for recursively typed complex objects. J. Comput. Syst. Sci. 47, 1, 121-156.

[22]

HULL, R., AND YAP, C.K. 1984. The format model: A theory of database organization. J. ACM, 31, 3 (July), 518-537.

[23]

HULL, R., AND YOSHIKAWA, M. 1992. ILOG: Declarative creation and manipulation of object identifiers. In Proceedings of the 16th International Conference on Very Large Data Bases, D. McLeod, R. Sacks-Davis, and H. Schek, eds. Morgan-Kaufmann, San Mateo, Calif.

[24]

KIFER, M., AND WU, J. 1993. A logic for programming with complex objects. J. Comput. Syst. Sci. 47, 1, 77-120.

[25]

KUPER, G., AND VARDI, M. 1993. The logical data model. ACM Trans. Datab. Syst. 18, 3 (Sept.), 379-413.

[26]

PAREDAENS, J. 1978. On the expressive power of the relational algebra. Inf. Proc. Lett. 7, 2.

[27]

STERLING, L., AND SHAPIRO, E. 1986. The Art of Prolog: Advanced Programming Techniques. HIT Press, Cambridge, Mass.

[28]

TARSKI, A. 1986. What are logical notions? Hist. Phil. Logic 7, 143-154, J. Corcoran, ed.

[29]

VAN DEN BUSSCHE, J., AND PAREDAENS, J. 1995. The expressive power of complex values in object-based data models. Inf. Comput. 120, 220-236.

[30]

VAN DEN BUSSCHE, J., AND VAN GUCHT, D. 1997. A semi-deterministic approach to object creation and non-determinism in database queries. J. Comput. Syst. Sci. 54, 1 (Feb.), 34-47.

[31]

VAN ROSSUM, J. 1992. Master's dissertation. Technical University of Eindhoven, Eindhoven, The Netherlands, (in Dutch).

Cited By

Vianu VVan Gucht D(2018)Computationally Complete Relational Query LanguagesEncyclopedia of Database Systems10.1007/978-1-4614-8265-9_1243(547-553)Online publication date: 7-Dec-2018
https://doi.org/10.1007/978-1-4614-8265-9_1243
Hidders JParedaens JVan den Bussche JSallinger EVan den Bussche JGeerts F(2017)J-LogicProceedings of the 36th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems10.1145/3034786.3056106(137-149)Online publication date: 9-May-2017
https://dl.acm.org/doi/10.1145/3034786.3056106
Ferrarotti FSchewe KTec LWang Q(2017)A complete logic for Database Abstract State Machines1Logic Journal of the IGPL10.1093/jigpal/jzx02125:5(700-740)Online publication date: 6-Jul-2017
https://doi.org/10.1093/jigpal/jzx021
Show More Cited By

Index Terms

On the completeness of object-creating database transformation languages
1. Theory of computation
  1. Logic
  2. Models of computation
    1. Computability

Recommendations

Soundness and Completeness Proofs by Coinductive Methods

We show how codatatypes can be employed to produce compact, high-level proofs of key results in logic: the soundness and completeness of proof systems for variations of first-order logic. For the classical completeness result, we first establish an ...
An object-oriented prototype for a geophysical database
SSST '95: Proceedings of the 27th Southeastern Symposium on System Theory (SSST'95)

Database management systems (DBMSs) are being used in a wide variety of domains to handle many types of data. Scientific data pose a special challenge to DBMSs due to their volume and complex nature. The object-oriented model has many additional ...
A framework for deductive object-oriented database systems
ICYCS'93: Proceedings of the third international conference on Young computer scientists

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Journal of the ACM

Journal of the ACM Volume 44, Issue 2

March 1997

161 pages

ISSN:0004-5411

EISSN:1557-735X

DOI:10.1145/256303

Issue’s Table of Contents

Copyright © 1997 ACM.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 March 1997

Published in JACM Volume 44, Issue 2

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

27
Total Citations
View Citations
588
Total Downloads

Downloads (Last 12 months)43
Downloads (Last 6 weeks)7

Reflects downloads up to 23 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Vianu VVan Gucht D(2018)Computationally Complete Relational Query LanguagesEncyclopedia of Database Systems10.1007/978-1-4614-8265-9_1243(547-553)Online publication date: 7-Dec-2018
https://doi.org/10.1007/978-1-4614-8265-9_1243
Hidders JParedaens JVan den Bussche JSallinger EVan den Bussche JGeerts F(2017)J-LogicProceedings of the 36th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems10.1145/3034786.3056106(137-149)Online publication date: 9-May-2017
https://dl.acm.org/doi/10.1145/3034786.3056106
Ferrarotti FSchewe KTec LWang Q(2017)A complete logic for Database Abstract State Machines1Logic Journal of the IGPL10.1093/jigpal/jzx02125:5(700-740)Online publication date: 6-Jul-2017
https://doi.org/10.1093/jigpal/jzx021
Vianu VVan Gucht D(2017)Computationally Complete Relational Query LanguagesEncyclopedia of Database Systems10.1007/978-1-4899-7993-3_1243-2(1-7)Online publication date: 17-Apr-2017
https://doi.org/10.1007/978-1-4899-7993-3_1243-2
Bonifati ANutt WTorlone RVan Den Bussche J(2016)Mapping-equivalence and oid-equivalence of single-function object-creating conjunctive queriesThe VLDB Journal — The International Journal on Very Large Data Bases10.1007/s00778-016-0421-x25:3(381-397)Online publication date: 1-Jun-2016
https://dl.acm.org/doi/10.1007/s00778-016-0421-x
Ameloot TVan den Bussche JWaller EHull RFan W(2013)On the expressive power of update primitivesProceedings of the 32nd ACM SIGMOD-SIGACT-SIGAI symposium on Principles of database systems10.1145/2463664.2465218(139-150)Online publication date: 22-Jun-2013
https://dl.acm.org/doi/10.1145/2463664.2465218
Van den Bussche J(2010)Database theory, Yuri, and meFields of logic and computation10.5555/1983702.1983705(49-60)Online publication date: 1-Jan-2010
https://dl.acm.org/doi/10.5555/1983702.1983705
Schewe KWang Q(2010)A customised ASM thesis for database transformationsActa Cybernetica10.5555/1945572.194557919:4(765-805)Online publication date: 1-Jan-2010
https://dl.acm.org/doi/10.5555/1945572.1945579
Schweikardt NSchwentick TSegoufin L(2010)Database theoryAlgorithms and theory of computation handbook10.5555/1882723.1882742(19-19)Online publication date: 1-Jan-2010
https://dl.acm.org/doi/10.5555/1882723.1882742
Wang QSchewe KThalheim B(2010)A Fixed-Point Query Language for XMLProceedings of the 2010 conference on Information Modelling and Knowledge Bases XXI10.5555/1745318.1745331(226-246)Online publication date: 26-Jul-2010
https://dl.acm.org/doi/10.5555/1745318.1745331
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