Towards a semantic view of an extended entity-relationship model

ACM Transactions on Database Systems - Tập 16 Số 3 - Trang 369-416 - 1991
Martin Gogolla1, Uwe Hohenstein2
1Technische Univ. Braunschweig, Brunswick, Germany
2Siemens AG, Munich, Germany

Tóm tắt

Nearly all query languages discussed recently for the Entity-Relationship (ER) model do not possess a formal semantics. Languages are often defined by means of examples only. The reason for this phenomenon is the essential gap between features of query languages and theoretical foundations like algebras and calculi. Known languages offer arithmetic capabilities and allow for aggregates, but algebras and calculi defined for ER models do not. This paper introduces an extended ER model concentrating nearly all concepts of known so-called semantic data models in a few syntactical constructs. Moreover, we provide our extended ER model with a formal mathematical semantics. On this basis a well-founded calculus is developed taking into account data operations on arbitrary user-defined data types and aggregate functions. We pay special attention to arithmetic operations, as well as multivalued terms allowing nested queries, in a uniform and consistent manner. We prove our calculus only allows the formulation of safe terms and queries yielding a finite result, and to be (at least) as expressive as the relational calculi.

Từ khóa


Tài liệu tham khảo

ATZENI P. BATINI C. LENZERINI M. VILLANELLI F. INCOD: A system for conceptual design of data and transactions in the entity-relationship model In Proceedings of the 2nd Internatwnal Conference on Entiy-Relationship Approach to Information Modelling and Analysis (Los Angeles Calif. Oct. 1981) pp. 375-410. ATZENI P. BATINI C. LENZERINI M. VILLANELLI F. INCOD: A system for conceptual design of data and transactions in the entity-relationship model In Proceedings of the 2nd Internatwnal Conference on Entiy-Relationship Approach to Information Modelling and Analysis (Los Angeles Calif. Oct. 1981) pp. 375-410.

ATZEN~ , P. , AN n C~ EN, P . P Completeness of query languages for the entity-relationship model . In Proceedings of the 2nd International Conference on Entity-Relationship Approach to Information Modelling and Analysis ( Los Angeles, Calif. , Oct 1981 ), pp. 109 - 122 ATZEN~, P., ANn C~EN, P. P Completeness of query languages for the entity-relationship model. In Proceedings of the 2nd International Conference on Entity-Relationship Approach to Information Modelling and Analysis (Los Angeles, Calif., Oct 1981), pp. 109-122

10.1145/32204.32205

BraD, R. S. An introduction to the theory of lists . In Logic of Programming and Calculi of D~screte Design. Nato ASI Series, vol F36, M Broy , Ed Springer-Verlag , Berlin , 1987 , pp. 5 - 42 . BraD, R.S. An introduction to the theory of lists. In Logic of Programming and Calculi of D~screte Design. Nato ASI Series, vol F36, M Broy, Ed Springer-Verlag, Berlin, 1987, pp. 5-42.

On Conceptual Modelling- Perspectwes from Artificial Intelligence, Databases, and Programm~ng Languages. M. L. Brodle, J. Mylopoulos, J. W Schmidt , Eds. Springer-Verlag , Berlin , 1984 . On Conceptual Modelling- Perspectwes from Artificial Intelligence, Databases, and Programm~ng Languages. M. L. Brodle, J. Mylopoulos, J. W Schmidt, Eds. Springer-Verlag, Berlin, 1984.

BRODIE , M L , AND RIDJANOVIC , D. On the design and specification of database transactions . In On Conceptual Modelling- Perspectwes from Artzficial Intelligence, Databases, and Programming Languages . Springer-Verlag , Berlin , 1984 , pp. 277 - 306 . BRODIE, M L, AND RIDJANOVIC, D. On the design and specification of database transactions. In On Conceptual Modelling- Perspectwes from Artzficial Intelligence, Databases, and Programming Languages. Springer-Verlag, Berlin, 1984, pp. 277-306.

Bf JLTZINGSLOEWEN , G. v. Translating and optimizing SQL queries having aggregates . In Proceedings of the 13th International Conference on VLDB, P. M. Stocker, W. Kent, Eds. Brighton , 1987 , pp. 235 - 243 . BfJLTZINGSLOEWEN, G. v. Translating and optimizing SQL queries having aggregates. In Proceedings of the 13th International Conference on VLDB, P. M. Stocker, W. Kent, Eds. Brighton, 1987, pp. 235-243.

Methodology and Tools for Database Design. S. Ceri , Ed. North~Holland , Amsterdam , 1983 Methodology and Tools for Database Design. S. Ceri, Ed. North~Holland, Amsterdam, 1983

CAMPBELL , D. M. , EMBLEY , D. W. , AN n CZ EJDO , B A relationally complete query language for an entity-relationship model . In Proceedings of the 4th Internatmnal Conference on Entzty-Relationship Approach ( Chicago, Ill. , Oct. 1985 ), pp. 90 - 97 CAMPBELL, D. M., EMBLEY, D. W., ANn CZEJDO, B A relationally complete query language for an entity-relationship model. In Proceedings of the 4th Internatmnal Conference on Entzty-Relationship Approach (Chicago, Ill., Oct. 1985), pp. 90-97

10.1145/320434.320440

C~EN , P.P. An algebra for a directional binary enity-relationship model . In Proceedings of the International Conference on Data Engineering ( Los Angeles, Cahf. April 1984 ), pp. 37 - 40 . C~EN, P.P. An algebra for a directional binary enity-relationship model. In Proceedings of the International Conference on Data Engineering (Los Angeles, Cahf. April 1984), pp. 37 -40.

DEMO , B. , DILE v A, A ., AND GIOLITO , P. An entity-relationship query language. In Proceed~ ings IFIP Workshop Conference on TFAIS (Sitges, Spain, Aprfi 1985), A. Sernadas, J. Bubenlko, and A. Olive , Eds. North-Holland , Amsterdam , 1985 , pp. 19 - 32 . DEMO, B., DILEvA, A., AND GIOLITO, P. An entity-relationship query language. In Proceed~ ings IFIP Workshop Conference on TFAIS (Sitges, Spain, Aprfi 1985), A. Sernadas, J. Bubenlko, and A. Olive, Eds. North-Holland, Amsterdam, 1985, pp. 19-32.

Dos SANTOS , C. S. , NEUHOLD , E. J. , AND FURTADO , A. L. A data type approach to the entity-relationship approach . In Proceedings of the 1st International Conference on Entity-Relationship Approach to Software Engineering ( Los Angeles, Calif. , Dec. 1979 ). P. P. Chen, Ed. North-Holland, Amsterdam, 1980, pp. 103-119 Dos SANTOS, C. S., NEUHOLD, E. J., AND FURTADO, A. L. A data type approach to the entity-relationship approach. In Proceedings of the 1st International Conference on Entity-Relationship Approach to Software Engineering (Los Angeles, Calif., Dec. 1979). P. P. Chen, Ed. North-Holland, Amsterdam, 1980, pp. 103-119

E~R ic~, H.-D., D~ os~ E~, K ., AND GOGOLLA , M. Towards an algebraic semantics for database specification . In Proceedings IFIP TC2 Working Conference on Knowledge & Data "DS-2" ( Albufeira, Portugal , Nov. 1986 ), pp. 119 - 135 . E~Ric~, H.-D., D~os~E~, K., AND GOGOLLA, M. Towards an algebraic semantics for database specification. In Proceedings IFIP TC2 Working Conference on Knowledge & Data "DS-2" (Albufeira, Portugal, Nov. 1986), pp. 119-135.

10.5555/20081.20104

EDER , J. , KAPPEL , G. , TJOA , A. M. , AND WAGNER , R. R. BIER : The behavior integrated entity relationship approact~. In Proceed;ngs of the 5th International ConfereT~ce on Ent~ty-Relatwnsh~p Approach ( Dijon, France , Nov. 1986 ), pp. 147 - 166 . EDER, J., KAPPEL, G., TJOA, A. M., AND WAGNER, R. R. BIER: The behavior integrated entity relationship approact~. In Proceed;ngs of the 5th International ConfereT~ce on Ent~ty-Relatwnsh~p Approach (Dijon, France, Nov. 1986), pp. 147-166.

ELMASRI , R. A. , AND LARSEN , J. A. A graphical query facility for ER databases . In Proceedings of the 4th Internatwnal Conference on Entity-Relatwnship Approach ( Chicago, Ill. , Oct. 1985 ), pp. 236 - 245 . ELMASRI, R. A., AND LARSEN, J. A. A graphical query facility for ER databases. In Proceedings of the 4th Internatwnal Conference on Entity-Relatwnship Approach (Chicago, Ill., Oct. 1985), pp. 236-245.

EHRIO , H. , AND MAHR , B. Fundamentals of Algebraic Specification I . Springer-Verlag , Berlin , 1985 . EHRIO, H., AND MAHR, B. Fundamentals of Algebraic Specification I. Springer-Verlag, Berlin, 1985.

IN Proceedings of the 1st International Conference on Entity-Relationship Approach to Systems Analys~s and Design ( Los Angeles, Calif. , Dec. 1979 ), P. P. Chen, Ed. North- Holland, Amsterdam, 1980. IN Proceedings of the 1st International Conference on Entity-Relationship Approach to Systems Analys~s and Design (Los Angeles, Calif., Dec. 1979), P. P. Chen, Ed. North- Holland, Amsterdam, 1980.

IN Proceedings of the 2nd International Conference on Entity Relatwnship Approach to Information Modelling and Analysis (Los Angeles Calif. , Oct. 1981 ), P. P. Chen, Ed. North-Holland, Amsterdam , 1983. IN Proceedings of the 2nd International Conference on Entity Relatwnship Approach to Information Modelling and Analysis (Los Angeles Calif., Oct. 1981), P. P. Chen, Ed. North-Holland, Amsterdam, 1983.

IN Proceedings of the 3rd International Conference On Entity-Relationship Approach to '~oftware Engineering (Anaheim, Calif. , Oct. 1983 ), C. G. Davis, S. Jajodia, P. A. Ng, and R. T. Yeh, Eds. North-Holland, Amsterdam , 1983. IN Proceedings of the 3rd International Conference On Entity-Relationship Approach to '~oftware Engineering (Anaheim, Calif., Oct. 1983), C. G. Davis, S. Jajodia, P. A. Ng, and R. T. Yeh, Eds. North-Holland, Amsterdam, 1983.

IN Proceedings of the 4th International Conference On Entity-Relationship Approach (Chicago Ill. , Oct. 1985 ). IN Proceedings of the 4th International Conference On Entity-Relationship Approach (Chicago Ill., Oct. 1985).

IN Proceedings of the 5th International Conference On Entity-Relationshzp Approach ( Dijon, France , Nov. 1986 ). IN Proceedings of the 5th International Conference On Entity-Relationshzp Approach (Dijon, France, Nov. 1986).

1N Proceedings of the 6th International Conference On Entity-Relationship Approach ( New York , 1987 ), S. March, Ed. 1N Proceedings of the 6th International Conference On Entity-Relationship Approach (New York, 1987), S. March, Ed.

1~ Proceedings of the 7th International Conference On Entity-Relatwnsh~p Approach ( Rome , 1988 ). 1~ Proceedings of the 7th International Conference On Entity-Relatwnsh~p Approach (Rome, 1988).

IN Proceedings of the 8th International Conference On Entity-Relationship Approach ( Toronto, Canada , 1989 ). IN Proceedings of the 8th International Conference On Entity-Relationship Approach (Toronto, Canada, 1989).

ELMASRI , R. , AND WmOER HOLD , G. GORDAS : A formal high-level query language for the entity-relationship model . In Proceedings of the 2nd International Conference On Entity- Relationship Approach to Information Modelling and Analysis ( Los Angeles, Calif. , Oct. 1981 ), P. P. Chen, Ed. North-Holland, Amsterdam, 1983, pp. 49-72. ELMASRI, R., AND WmOERHOLD, G. GORDAS: A formal high-level query language for the entity-relationship model. In Proceedings of the 2nd International Conference On Entity- Relationship Approach to Information Modelling and Analysis (Los Angeles, Calif., Oct. 1981), P. P. Chen, Ed. North-Holland, Amsterdam, 1983, pp. 49-72.

10.1016/0169-023X(85)90027-8

10.5555/646624.698175

10.21236/ADA458082

10.1145/45072.45073

10.1145/319587.319588

HOBE~STEIN , U. Automatic transformation of an entity-relationship query language into SQL . In Proceedings of the 8th International Conference on Entity-Relatwnship Approach ( Toronto, Canada 1989 ), F. Lodeovsky, Ed., pp. 129-148. HOBE~STEIN, U. Automatic transformation of an entity-relationship query language into SQL. In Proceedings of the 8th International Conference on Entity-Relatwnship Approach (Toronto, Canada 1989), F. Lodeovsky, Ed., pp. 129-148.

I-{ OHENSTE~N , U. , NEUGEBAUER , L. , SAAKE , G. , AND EHR~CH , H. -D. Three-level specification using an extended entity-relationship Model . In Informatwnsbedarfsermittlung und -analyse fiir den Entwurf von Informationssystemen (Informatik-Fachberichte Band 143 , Springer , 1987 ), R. R. Wagner, R. Traunmiiller, H. C. Mayr, Eds. pp. 58 - 88 . I-{OHENSTE~N, U., NEUGEBAUER, L., SAAKE, G., AND EHR~CH, H. -D. Three-level specification using an extended entity-relationship Model. In Informatwnsbedarfsermittlung und -analyse fiir den Entwurf von Informationssystemen (Informatik-Fachberichte Band 143, Springer, 1987), R. R. Wagner, R. Traunmiiller, H. C. Mayr, Eds. pp. 58-88.

10.1145/588111.588133

10.1145/322326.322332

Lm ECK , U W ., AN n NEUM AX~ , K. Modelling and manipulating objects in geoscientific databases . In Proceedings of the 5th Internatwnal Conference On Ent~ty-Relatwnship Approach ( Dijon, France , Nov. 1986 ), pp. 67 - 86 . LmECK, U W., ANn NEUMAX~, K. Modelling and manipulating objects in geoscientific databases. In Proceedings of the 5th Internatwnal Conference On Ent~ty-Relatwnship Approach (Dijon, France, Nov. 1986), pp. 67-86.

LENZERIM , M. , AN n SANTUC CL G . Cardinality constraints the entity-relationship model . In Proceedings of the 3rd International Conference On Entity-Relationship Approach to Software Engineering (Anaheim, Calif. , Oct. 1983 ), C. G. Davis, S. Jajodia, P. A. Ng, and R. T. Yeh, Eds. North-Holland, Amsterdam , 1983, pp. 529 - 549 . LENZERIM, M., ANn SANTUCCL G. Cardinality constraints the entity-relationship model. In Proceedings of the 3rd International Conference On Entity-Relationship Approach to Software Engineering (Anaheim, Calif., Oct. 1983), C. G. Davis, S. Jajodia, P. A. Ng, and R. T. Yeh, Eds. North-Holland, Amsterdam, 1983, pp. 529-549.

MA m R, D . The Theory of Databases . Computer Science Press , Rockville, MD , 1983 . MAmR, D. The Theory of Databases. Computer Science Press, Rockville, MD, 1983.

MARKOWITZ , V. M. , AND RAZ , Y. A modified algebra and its use in an entity-relationship environment . In Proceedings of the 3rd International Conference On Ent~ty-Relatwnship -Approach to Software Engineering (Anaheim. Calif. , Oct. 1983 ), C. G. Davis, S Jajodia, P A. Ng, and R. T. Yeh, Eds. North-Holland, Amsterdam , 1983, pp. 315 - 328 . MARKOWITZ, V. M., AND RAZ, Y. A modified algebra and its use in an entity-relationship environment. In Proceedings of the 3rd International Conference On Ent~ty-Relatwnship -Approach to Software Engineering (Anaheim. Calif., Oct. 1983), C. G. Davis, S Jajodia, P A. Ng, and R. T. Yeh, Eds. North-Holland, Amsterdam, 1983, pp. 315-328.

MARKOWITZ , V. M. , AND RAZ , Y. ERROL : An entity-relationship, role oriented query language . In Proceedings of the 3rd International Conference On Entity-Relationship Approach to Software Engineering (Anaheim, Calif. , Oct. 1983 ), C. G. Davis, S. Jajodia, P A. Ng, and R. T. Yeh, Eds. North-Holland, Amsterdam , 1983, pp. 329 - 345 . MARKOWITZ, V. M., AND RAZ, Y. ERROL: An entity-relationship, role oriented query language. In Proceedings of the 3rd International Conference On Entity-Relationship Approach to Software Engineering (Anaheim, Calif., Oct. 1983), C. G. Davis, S. Jajodia, P A. Ng, and R. T. Yeh, Eds. North-Holland, Amsterdam, 1983, pp. 329-345.

MYOPOULOS , J. , AND WONG , H. K T Some features of the TAXIS data model. In Proceed- ~ngs of the 6th International Conference On VLDB (Montreal , Canada , Oct. 1980 ), pp 399 - 410 . MYOPOULOS, J., AND WONG, H. K T Some features of the TAXIS data model. In Proceed- ~ngs of the 6th International Conference On VLDB (Montreal, Canada, Oct. 1980), pp 399-410.

10.1145/32204.32219

Pm OTTE , A. High level data base query languages In Logzc and Databases . H. Gallaire, J. Minker, Eds. Plenum Press , New York , 1979 , pp 409 - 436 PmOTTE, A. High level data base query languages In Logzc and Databases. H. Gallaire, J. Minker, Eds. Plenum Press, New York, 1979, pp 409-436

POONEN , G CLEAR: A conceptual language for entities and relationships. In Centraltzed and Dzstr~buted Systems. IEEE Computer Society. W. Chu, P. P. Chen, Eds. Silver Springs , Md. , 1980 , pp. 194 - 215 . POONEN, G CLEAR: A conceptual language for entities and relationships. In Centraltzed and Dzstr~buted Systems. IEEE Computer Society. W. Chu, P. P. Chen, Eds. Silver Springs, Md., 1980, pp. 194-215.

10.5555/645470.655080

PARENT , C. , AND SPACCAPIETRA , S An algebra for a general entity-relationship model. IEEE Trans. Softw. Eng 11 , 7 ( July 1985 ), 634-643. PARENT, C., AND SPACCAPIETRA, S An algebra for a general entity-relationship model. IEEE Trans. Softw. Eng 11, 7 (July 1985), 634-643.

ROESNER , W DES PATH : An ER mampulation language . In Proceedings of the 4th International Conference On Entity-Relationship Approach ( Chicago, Ill. , Oct 1985 ), pp. 72 - 81 . ROESNER, W DESPATH: An ER mampulation language. In Proceedings of the 4th International Conference On Entity-Relationship Approach (Chicago, Ill., Oct 1985), pp. 72-81.

RAMM , I. , NEUMANN , K. , LIPECK , U W , AND EHRICH . H. ~D Eine Benutzerschnittstelle fur geowissenschaftliche Datenbanken. Informatik-Berlcht Nr 85 08 , TU Braunschwelg, 1985 . RAMM, I., NEUMANN, K., LIPECK, U W , AND EHRICH. H.~D Eine Benutzerschnittstelle fur geowissenschaftliche Datenbanken. Informatik-Berlcht Nr 85 08, TU Braunschwelg, 1985.

SHOSHANI , A. CABLE: A language based on the entity-relationship model. Rep. UCID-8005, Computer Science and Applied Mathematics Dept ., Lawrence Berkeley Laboratory , Berkeley, Calif ., 1979 . SHOSHANI, A. CABLE: A language based on the entity-relationship model. Rep. UCID-8005, Computer Science and Applied Mathematics Dept., Lawrence Berkeley Laboratory, Berkeley, Calif., 1979.

10.1145/319540.319561

SUBIETA , K. , AND MISSALA , M. Semantics of query languages for the entity-relationship model . In Proceedings of the 5th International Conference On Entzty-Relatzonsh~p Approach ( Dijon, France , Nov. 1986 ), S. Spaccapietra, Ed., pp. 197-216. SUBIETA, K., AND MISSALA, M. Semantics of query languages for the entity-relationship model. In Proceedings of the 5th International Conference On Entzty-Relatzonsh~p Approach (Dijon, France, Nov. 1986), S. Spaccapietra, Ed., pp. 197-216.

10.1016/0306-4379(87)90019-6

10.1145/320544.320546

10.1016/0306-4379(86)90003-7

SERNADAS , A. , SERNADAS , C. , AND EHRICH , H. -D Object-oriented specification of databases- An algebraic Approach . In Proceedings of the 13th Internatzonal Conference on VLDB (Brighton , 1987 ), P. M. Stocker, W. Kent, Eds. pp. 107 - 116 . SERNADAS, A., SERNADAS, C., AND EHRICH, H.-D Object-oriented specification of databases- An algebraic Approach. In Proceedings of the 13th Internatzonal Conference on VLDB (Brighton, 1987), P. M. Stocker, W. Kent, Eds. pp. 107-116.

SCH~EFL , M. , TJOA , A. M. , AND WAGNER , R. R. Comparison criteria for semantic data models . In Proceedings International Conference On Data Engineering ( Los Angeles, Calif. , 1984 ), pp. 120 - 125 . SCH~EFL, M., TJOA, A. M., AND WAGNER, R. R. Comparison criteria for semantic data models. In Proceedings International Conference On Data Engineering (Los Angeles, Calif., 1984), pp. 120-125.

TEOREY , F. J. , AND FRY , J. P. Design of Database Structures Prentice-Hall , Englewood Cliffs , N. J. , 1982 . TEOREY, F. J., AND FRY, J. P. Design of Database Structures Prentice-Hall, Englewood Cliffs, N. J., 1982.

10.1093/comjnl/28.2.162

10.1145/7474.7475

URSPRUNG , P. , AND ZEHNDER , C.A. HIQUEL : An interactive query language to define and use hierarchies. In Proceed~ng~ of the $rd International ConfereF~ce On Entity-Relationship Approach to Software Engineering (Anaheim , Calif. , Oct 1983 ), C. G. Davis, S. Jajodia, P. A. Ng, and R. T. Yeh, Eds. North-Holland, Amsterdam , 1983, pp 299 - 314 . URSPRUNG, P., AND ZEHNDER, C.A. HIQUEL: An interactive query language to define and use hierarchies. In Proceed~ng~ of the $rd International ConfereF~ce On Entity-Relationship Approach to Software Engineering (Anaheim, Calif., Oct 1983), C. G. Davis, S. Jajodia, P. A. Ng, and R. T. Yeh, Eds. North-Holland, Amsterdam, 1983, pp 299-314.

V~LEZ , F. LAMBDA : An entity-relationship based query language for the retrieval of structured documents . In Proceedings of the 4th Internatzonal Conference On Entity- Relat~onshzp Approach ( Chicago, Ill. , Oct. 1985 ), pp. 82 - 89 . V~LEZ, F. LAMBDA: An entity-relationship based query language for the retrieval of structured documents. In Proceedings of the 4th Internatzonal Conference On Entity- Relat~onshzp Approach (Chicago, Ill., Oct. 1985), pp. 82-89.

ZHAN 6, Z. Q., AND MENDELZON , A. 0 A graphical query language for entity relationship databases. In Proceedz~gs of the 3rd International Con{erence On Entity-Relationship Approach to Software Engineering (Anaheim, Cahf , Oct. 1983 ), C. G. Davis, S. Jajodia, P A Ng, and R. T. Yeh Eds. North-Holland, Amsterdam , 1983, pp. 441 - 448 . ZHAN6, Z. Q., AND MENDELZON, A. 0 A graphical query language for entity relationship databases. In Proceedz~gs of the 3rd International Con{erence On Entity-Relationship Approach to Software Engineering (Anaheim, Cahf, Oct. 1983), C. G. Davis, S. Jajodia, P A Ng, and R. T. Yeh Eds. North-Holland, Amsterdam, 1983, pp. 441-448.