On the Expressive Power of the Logical Data Model (Preliminary Report).

@inproceedings{DBLP:conf/sigmod/KuperV85,
  author    = {Gabriel M. Kuper and
               Moshe Y. Vardi},
  editor    = {Shamkant B. Navathe},
  title     = {On the Expressive Power of the Logical Data Model (Preliminary
               Report)},
  booktitle = {Proceedings of the 1985 ACM SIGMOD International Conference on
               Management of Data, Austin, Texas, May 28-31, 1985},
  publisher = {ACM Press},
  year      = {1985},
  pages     = {180-187},
  ee        = {http://doi.acm.org/10.1145/318898.318915, db/conf/sigmod/KuperV85.html},
  crossref  = {DBLP:conf/sigmod/85},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

In this paper we study the expressive power of the logical data model LDM, introduced in [KV 81]. We show that even though the logical data model is semantically powerful, it is not overly powerful so as to be intractable. We demonstrate it from three asoects. First, we study the complexity of checking integrity constraints, and we show that it is no more diffi cult than checking integrity constraints in the relational model. Secondly, we show that the logic of the model is essentially first-order. That means, for example, that one can use a stan dard theorem-prover other in the database design process or for deductive query answering.

Finally, we prove the surprising result that the ability to define cycles does not, in a certain sense, add any power to the model. Thus, any cyclic schema can be converted to an "equivalent" acyclic schema.

Copyright © 1985 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.

ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 1 Issue 2, SIGMOD '75-'92" and ...

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• Mac: Click here
• UNIX/LINUX: mount the CD and click on the path of your mount point:
  /Anthology/smod7592 or /cdrom

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• Mac: Click here
• UNIX/LINUX: mount the DVD and click on the path of your mount point:
  /Anthology/aDVD1 or /dvd

Printed Edition

Online Edition: ACM Digital Library

References

[BBG78]

Catriel Beeri, Philip A. Bernstein, Nathan Goodman: A Sophisticate's Introduction to Database Normalization Theory. VLDB 1978: 113-124 BibTeX

[Co70]

E. F. Codd: A Relational Model of Data for Large Shared Data Banks. Commun. ACM 13(6): 377-387(1970) BibTeX

[Co79]

E. F. Codd: Extending the Database Relational Model to Capture More Meaning. ACM Trans. Database Syst. 4(4): 397-434(1979) BibTeX

[HM78]

Michael Hammer, Dennis McLeod: Database Description with SDM: A Semantic Database Model. ACM Trans. Database Syst. 6(3): 351-386(1981) BibTeX

[Hu82]

Richard Hull, Chee-Keng Yap: The Format Model: A Theory of Database Organization. PODS 1982: 205-211 BibTeX

[Hu84]

Richard Hull: Relative Information Capacity of Simple Relational Database Schemata. PODS 1984: 97-109 BibTeX

[Ja82]

Barry E. Jacobs: On Database Logic. J. ACM 29(2): 310-332(1982) BibTeX

[Ku85]

...

[KV84]

Gabriel M. Kuper, Moshe Y. Vardi: A New Approach to Database Logic. PODS 1984: 86-96 BibTeX

[MMSU81]

David Maier, Alberto O. Mendelzon, Fereidoon Sadri, Jeffrey D. Ullman: Adequacy of Decompositions of Relational Databases. Advances in Data Base Theory 1979: 101-114 BibTeX

[NG78]

Jean-Marie Nicolas, Hervé Gallaire: Data Base: Theory vs. Interpretation. Logic and Data Bases 1977: 33-54 BibTeX

[Re84]

...

[ScSw75]

Hans Albrecht Schmid, J. Richard Swenson: On the Semantics of the Relational Data Model. SIGMOD Conference 1975: 211-223 BibTeX

[Shi78]

David W. Shipman: The Functional Data Model and the Data Language DAPLEX. ACM Trans. Database Syst. 6(1): 140-173(1981) BibTeX

[SmSm77]

John Miles Smith, Diane C. P. Smith: Database Abstractions: Aggregation. Commun. ACM 20(6): 405-413(1977) BibTeX

[Ul82]

Jeffrey D. Ullman: Principles of Database Systems, 2nd Edition. Computer Science Press 1982, ISBN 0-914894-36-6
BibTeX

[Va82]

Moshe Y. Vardi: The Complexity of Relational Query Languages (Extended Abstract). STOC 1982: 137-146 BibTeX

[Va83]

...

Referenced by

1. Avigdor Gal, Opher Etzion: A Multiagent Update Process in a Database with Temporal Data Dependencies and Schema Versioning. IEEE Trans. Knowl. Data Eng. 10(1): 21-37(1998)
2. Gabriel M. Kuper, Moshe Y. Vardi: The Logical Data Model. ACM Trans. Database Syst. 18(3): 379-413(1993)
3. Stan Danforth, Patrick Valduriez: A FAD for Data Intensive Applications. IEEE Trans. Knowl. Data Eng. 4(1): 34-51(1992)
4. Sanjay Manchanda: "Higher-Order" Logic As a Data Model. DBPL 1989: 330-341
5. Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume II. Computer Science Press 1989, ISBN 0-7167-8162-X
   Contents
6. Gabriel M. Kuper, Moshe Y. Vardi: On the Complexity of Queries in the Logical Data Model (Extended Abstract). ICDT 1988: 267-280
7. Catriel Beeri: Data Models and Languages for Databases. ICDT 1988: 19-40
8. Henryk Rybinski: On First-Order-Logic Databases. ACM Trans. Database Syst. 12(3): 325-349(1987)
9. Richard Hull, Roger King: Semantic Database Modeling: Survey, Applications, and Research Issues. ACM Comput. Surv. 19(3): 201-260(1987)
10. François Bancilhon, Ted Briggs, Setrag Khoshafian, Patrick Valduriez: FAD, a Powerful and Simple Database Language. VLDB 1987: 97-105
11. Jeffrey D. Ullman: Database Theory: Past and Future. PODS 1987: 1-10