On the Foundations of the Universal Relation Model.

@article{DBLP:journals/tods/MaierUV84,
  author    = {David Maier and
               Jeffrey D. Ullman and
               Moshe Y. Vardi},
  title     = {On the Foundations of the Universal Relation Model},
  journal   = {ACM Trans. Database Syst.},
  volume    = {9},
  number    = {2},
  year      = {1984},
  pages     = {283-308},
  ee        = {http://doi.acm.org/10.1145/329.318580, db/journals/tods/MaierUV84.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

The universal relation model aims at achieving complete access-path independence in relational databases by relieving the user of the need for logical navigation among relations. We clarify the assumptions underlying it and explore the approaches suggested for implementing it.

The essential idea of the universal relation model is that access paths are embedded in attribute names. Thus attribute names must play unique "roles." Furthermore, it assumes that for every set of attributes there is a basic relationship that the user has in mind. The user's queries refer to these basic relationships rather than to the underlying database.

Two fundamentally different approaches to the universal relation model have been taken. According to the first approach, the user's view of the database is a universal relation or many universal relations, about which the user poses queries. The second approach sees the model as having query-processing capabilities that relieve the user of the need to specify the logical access path. Thus, while the first approach gives a denotational semantics to query answering, the second approach gives it an operational semantics. We investigate the relationship between these two approaches.

Copyright © 1984 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.

Joint ACM SIGMOD / IEEE Computer Society Anthology

• 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/An3-1 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/aDVD2 or /dvd

Conference Abstract

References

[1]

...

[2]

Alfred V. Aho, Catriel Beeri, Jeffrey D. Ullman: The Theory of Joins in Relational Databases. ACM Trans. Database Syst. 4(3): 297-314(1979) BibTeX

[3]

Alfred V. Aho, Yehoshua Sagiv, Jeffrey D. Ullman: Equivalences Among Relational Expressions. SIAM J. Comput. 8(2): 218-246(1979) BibTeX

[4]

...

[5]

Paolo Atzeni, Douglas Stott Parker Jr.: Assumptions in Relational Database Theory. PODS 1982: 1-9 BibTeX

[6]

Edward Babb: Joined Normal Form: A Storage Encoding for Relational Databases. ACM Trans. Database Syst. 7(4): 588-614(1982) BibTeX

[7]

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

[8]

...

[9]

Catriel Beeri, Moshe Y. Vardi: A Proof Procedure for Data Dependencies. J. ACM 31(4): 718-741(1984) BibTeX

[10]

Philip A. Bernstein: Synthesizing Third Normal Form Relations from Functional Dependencies. ACM Trans. Database Syst. 1(4): 277-298(1976) BibTeX

[11]

C. Robert Carlson, Robert S. Kaplan: A Generalized Access Path Model and its Application to a Relational Data Base System. SIGMOD Conference 1976: 143-154 BibTeX

[12]

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

[13]

E. F. Codd: Relational Database: A Practical Foundation for Productivity. Commun. ACM 25(2): 109-117(1982) BibTeX

[14]

...

[15]

Ronald Fagin: Horn clauses and database dependencies. J. ACM 29(4): 952-985(1982) BibTeX

[16]

Ronald Fagin, Alberto O. Mendelzon, Jeffrey D. Ullman: A Simplified Universal Relation Assumption and Its Properties. ACM Trans. Database Syst. 7(3): 343-360(1982) BibTeX

[17]

Hervé Gallaire, Jack Minker (Eds.): Logic and Data Bases, Symposium on Logic and Data Bases, Centre d'études et de recherches de Toulouse, 1977. Advances in Data Base Theory Plemum Press 1978, ISBN 0-306-40060-X
Contents BibTeX

[18]

Marc H. Graham, Alberto O. Mendelzon: Notions of Dependency Satisfaction. PODS 1982: 177-188 BibTeX

[19]

Marc H. Graham, Moshe Y. Vardi: On the Complexity and Axiomatizability of Consistent Database States. PODS 1984: 281-289 BibTeX

[20]

Peter Honeyman: Testing satisfaction of functional dependencies. J. ACM 29(3): 668-677(1982) BibTeX

[21]

Peter Honeyman, Richard E. Ladner, Mihalis Yannakakis: Testing the Universal Instance Assumption. Inf. Process. Lett. 10(1): 14-19(1980) BibTeX

[22]

Tomasz Imielinski, Witold Lipski Jr.: On Representing Incomplete Information in a Relational Data Base. VLDB 1981: 388-397 BibTeX

[23]

William Kent: Consequences of Assuming a Universal Relation. ACM Trans. Database Syst. 6(4): 539-556(1981) BibTeX

[24]

Henry F. Korth, Gabriel M. Kuper, Joan Feigenbaum, Allen Van Gelder, Jeffrey D. Ullman: System/U: A Database System Based on the Universal Relation Assumption. ACM Trans. Database Syst. 9(3): 331-347(1984) BibTeX

[25]

Robert A. Kowalski: Logic as a Database Language. BNCOD 1984: 103-132 BibTeX

[26]

Sharon McCure Kuck, Yehoshua Sagiv: A Universal Relation Database System Implemented via the Network Model. PODS 1982: 147-157 BibTeX

[27]

Eliezer L. Lozinskii: Construction of Relations in Relational Databases. ACM Trans. Database Syst. 5(2): 208-224(1980) BibTeX

[28]

David Maier: The Theory of Relational Databases. Computer Science Press 1983, ISBN 0-914894-42-0
Contents BibTeX

[29]

...

[30]

David Maier, Alberto O. Mendelzon, Fereidoon Sadri, Jeffrey D. Ullman: Adequacy of Decompositions of Relational Databases. J. Comput. Syst. Sci. 21(3): 368-379(1980) BibTeX

[31]

David Maier, Alberto O. Mendelzon, Yehoshua Sagiv: Testing Implications of Data Dependencies. ACM Trans. Database Syst. 4(4): 455-469(1979) BibTeX

[32]

David Maier, David Rozenshtein, David Scott Warren: Windows on the World. SIGMOD Conference 1983: 68-78 BibTeX

[33]

David Maier, David Rozenshtein, Sharon C. Salveter, Jacob Stein, David Scott Warren: Toward Logical Data Independence: A Relational Query Language Without Relations. SIGMOD Conference 1982: 51-60 BibTeX

[34]

David Maier, Jeffrey D. Ullman: Maximal Objects and the Semantics of Universal Relation Databases. ACM Trans. Database Syst. 8(1): 1-14(1983) BibTeX

[35]

...

[36]

David Maier, David Scott Warren: Specifying Connections for a Universal Relation Scheme Database. SIGMOD Conference 1982: 1-7 BibTeX

[37]

Alberto O. Mendelzon: Database States and Their Tableaux. ACM Trans. Database Syst. 9(2): 264-282(1984) BibTeX

[38]

Jean-Marie Nicolas: First Order Logic Formalization for Functional, Multivalued and Mutual Dependencies. SIGMOD Conference 1978: 40-46 BibTeX

[39]

Sylvia L. Osborn: Towards a Universal Relation Interface. VLDB 1979: 52-60 BibTeX

[40]

Raymond Reiter: Towards a Logical Reconstruction of Relational Database Theory. On Conceptual Modelling (Intervale) 1982: 191-233 BibTeX

[41]

Jorma Rissanen: Independent Components of Relations. ACM Trans. Database Syst. 2(4): 317-325(1977) BibTeX

[42]

Fereidoon Sadri, Jeffrey D. Ullman: Template Dependencies: A Large Class of Dependencies in Relational Databases and Its Complete Axiomatization. J. ACM 29(2): 363-372(1982) BibTeX

[43]

Yehoshua Sagiv: Can We Use the Universal Instance Assumption Without Using Nulls? SIGMOD Conference 1981: 108-120 BibTeX

[44]

Yehoshua Sagiv: A Characterization of Globally Consistent Databases and Their Correct Access Paths. ACM Trans. Database Syst. 8(2): 266-286(1983) BibTeX

[45]

Kathryn L. Schenk, James R. Pinkert: An Algorithm for Servicing Multi-Relational Queries. SIGMOD Conference 1977: 10-20 BibTeX

[46]

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

[47]

Jeffrey D. Ullman: The U. R. Strikes Back. PODS 1982: 10-22 BibTeX

[48]

...

[49]

Moshe Y. Vardi: On Decomposition of Relational Databases. FOCS 1982: 176-185 BibTeX

[50]

...

[51]

Mihalis Yannakakis: Algorithms for Acyclic Database Schemes. VLDB 1981: 82-94 BibTeX

[52]

Mihalis Yannakakis, Christos H. Papadimitriou: Algebraic Dependencies. J. Comput. Syst. Sci. 25(1): 2-41(1982) BibTeX

Referenced by

1. Hasan Davulcu, Juliana Freire, Michael Kifer, I. V. Ramakrishnan: A Layered Architecture for Querying Dynamic Web Content. SIGMOD Conference 1999: 491-502
2. Anand Rajaraman, Jeffrey D. Ullman: Integrating Information by Outerjoins and Full Disjunctions. PODS 1996: 238-248
3. Jean-Marc Petit, Farouk Toumani, Jean-François Boulicaut, Jacques Kouloumdjian: Towards the Reverse Engineering of Denormalized Relational Databases. ICDE 1996: 218-227
4. Mark Levene, George Loizou: A Graph-Based Data Model and its Ramifications. IEEE Trans. Knowl. Data Eng. 7(5): 809-823(1995)
5. Serge Abiteboul, Richard Hull, Victor Vianu: Foundations of Databases. Addison-Wesley 1995, ISBN 0-201-53771-0
   Contents
6. Dominique Laurent, Nicolas Spyratos: A Partition Model Approach to Updating Universal Scheme Interfaces. IEEE Trans. Knowl. Data Eng. 6(2): 316-330(1994)
7. Yannis E. Ioannidis, Yezdi Lashkari: Incomplete Path Expressions and their Disambiguation. SIGMOD Conference 1994: 138-149
8. Surajit Chaudhuri, Phokion G. Kolaitis: Can Datalog be Approximated? PODS 1994: 86-96
9. Mark Levene, George Loizou: Semantics for Null Extended Nested Relations. ACM Trans. Database Syst. 18(3): 414-459(1993)
10. Kazimierz Subieta, Florian Matthes, Joachim W. Schmidt, Andreas Rudloff: Viewers: A Data-World Analogue of Procedure Calls. VLDB 1993: 268-277
11. Ke Wang, Marc H. Graham: Constant-Time Maintainability: A Generalization of Independence. ACM Trans. Database Syst. 17(2): 201-246(1992)
12. Victor M. Markowitz, Arie Shoshani: Representing Extended Entity-Relationship Structures in Relational Databases: A Modular Approach. ACM Trans. Database Syst. 17(3): 423-464(1992)
13. Paolo Atzeni, Riccardo Torlone: Updating Relational Databases Through Weak Instance Interfaces. ACM Trans. Database Syst. 17(4): 718-745(1992)
14. Héctor J. Hernández, Edward P. F. Chan: Constant-Time-Maintainable BCNF Database Schemes. ACM Trans. Database Syst. 16(4): 571-599(1991)
15. José Andany, Michel Léonard, Carole Palisser: Management Of Schema Evolution In Databases. VLDB 1991: 161-170
16. Gerd G. Hillebrand, Paris C. Kanellakis, Harry G. Mairson, Moshe Y. Vardi: Tools for Datalog Boundedness. PODS 1991: 1-12
17. Heikki Hyötyniemi, Aarno Lehtola: A Universal Relation Database Interface for Knowledge Based Systems. DASFAA 1991: 84-88
18. Rom Langerak: View Updates in Relational Databases with an Independent Scheme. ACM Trans. Database Syst. 15(1): 40-66(1990)
19. Carl S. Hartzman, Carolyn R. Watters: A Relational Approach to Querying Streams. IEEE Trans. Knowl. Data Eng. 2(4): 401-409(1990)
20. Victor M. Markowitz: Referential Integrity Revisited: An Object-Oriented Perspective. VLDB 1990: 578-589
21. Ke Wang: Polynomial Time Designs toward Both BCNF and Efficient Data Manipulation. SIGMOD Conference 1990: 74-83
22. Paolo Atzeni, Riccardo Torlone: Efficient Updates to Independent Schemes in the Weak Instance Model. SIGMOD Conference 1990: 84-93
23. David W. Embley: NFQL: The Natural Forms Query Language. ACM Trans. Database Syst. 14(2): 168-211(1989)
24. Paolo Atzeni, Edward P. F. Chan: Efficient Optimization of Simple Chase Join Expressions. ACM Trans. Database Syst. 14(2): 212-230(1989)
25. Victor M. Markowitz, Arie Shoshani: On the Correctness of Representing Extended Entity-Relationship Structures in the Relational Model. SIGMOD Conference 1989: 430-439
26. Ke Wang: Can Constant-time Maintainability Be More Practical? PODS 1989: 120-127
27. Yehoshua Sagiv, Moshe Y. Vardi: Safety of Datalog Queries over Infinite Databases. PODS 1989: 160-171
28. Stavros S. Cosmadakis: On the First-Order Expressibility of Recursive Queries. PODS 1989: 311-323
29. Paolo Atzeni, Riccardo Torlone: Updating Databases in the Weak Instance Model. PODS 1989: 101-109
30. Margareta Dina Draghici: An Extended View on Data Base Conceptual Design. MFDBS 1989: 148-171
31. Paolo Atzeni, Riccardo Torlone: Approaches to Updates over Weak Instances. MFDBS 1989: 12-23
32. Dekang Lin: Automatic Logical Navigation Among Relations Using Steiner Trees. ICDE 1989: 582-588
33. Victor M. Markowitz, Arie Shoshani: Abbreviated Query Interpretation in Extended Entity-Relationship Oriented Databases. ER 1989: 325-343
34. Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume II. Computer Science Press 1989, ISBN 0-7167-8162-X
    Contents
35. Volkert Brosda, Gottfried Vossen: Update and Retrieval in a Relational Database Through a Universal Schema Interface. ACM Trans. Database Syst. 13(4): 449-485(1988)
36. Christophe Lécluse, Nicolas Spyratos: Implementing Queries and Updates on Universal Scheme Interfaces. VLDB 1988: 62-75
37. Héctor J. Hernández, Edward P. F. Chan: A Characterization of Constant-time-mainteinability for BCNF Database Schemes. SIGMOD Conference 1988: 209-217
38. Moshe Y. Vardi: Decidability and Undecidability Results for Boundedness of Linear Recursive Queries. PODS 1988: 341-351
39. Ashok K. Chandra: Theory of Database Queries. PODS 1988: 1-9
40. Edward P. F. Chan, Héctor J. Hernández: Independence-reducible Database Schemes. PODS 1988: 163-173
41. Mark Levene, George Loizou: A Universal Relation Model for Nested Relations. EDBT 1988: 294-308
42. Paolo Atzeni, Edward P. F. Chan: Independent Database Schemes under Functional and Inclusion Dependencies. VLDB 1987: 159-166
43. Edward P. F. Chan, Héctor J. Hernández: On Designing Database Schemes Bounded or Constant-time-maintainable with respect to Functional Dependencies. PODS 1987: 48-57
44. Paolo Atzeni, Maria Cristina De Bernardis: A New Basis for the Weak Instance Model. PODS 1987: 79-86
45. Hans Janssens: A Theory of Reference Graphs in Relational Databases. MFDBS 1987: 159-180
46. Alessandro D'Atri, Paolino Di Felice, V. S. Lakshmanan, Marina Moscarini: On Global Context Dependencies and their Properties. MFDBS 1987: 71-79
47. Joachim Biskup, Hans Hermann Brüggemann: Data Manipulation Languages for the Universal Relation View DURST. MFDBS 1987: 20-41
48. Tomasz Imielinski: Query Processing in Deductive Databases with Incomplete Information. SIGMOD Conference 1986: 268-280
49. Moshe Y. Vardi: On the Integrity of Databases with Incomplete Information. PODS 1986: 252-266
50. Stavros S. Cosmadakis, Paris C. Kanellakis: Parallel Evaluation of Recursive Rule Queries. PODS 1986: 280-293
51. Edward P. F. Chan, Paolo Atzeni: On the Properties and Characterization of Connection-tap-free Schemes. PODS 1986: 140-147
52. Joachim Biskup, Hans Hermann Brüggemann, L. Schnetgöke, M. Kramer: One Flavor Assumption and Gamma-Acyclicity for Universal Relation Views. PODS 1986: 148-159
53. Peter Thanisch, George Loizou: A Polynomial-Time Join Dependency Implication Algorithm for Multi-Valued Dependencies. ICDT 1986: 397-408
54. Edward P. F. Chan, Héctor J. Hernández: On the Desirability of gamma-Acyclic BCNF Database Schemes. ICDT 1986: 105-122
55. Lynette I. Brady, Christopher N. G. Dampney: The Semantics of Relational Database Functions. ER 1986: 287-302
56. Gottfried Vossen, Volkert Brosda: A High-Level User Interface for Update and Retrieval in Relational Databases - Language Aspects. SIGMOD Conference 1985: 343-353
57. Jacob Stein, David Maier: Relaxing the Universal Relation Scheme Assumption. PODS 1985: 76-84
58. Yehoshua Sagiv: On Computing Restricted Projections of Representative Instances. PODS 1985: 171-180
59. Shashi K. Gadia, Jay H. Vaishnav: A Query Language for a Homogeneous Temporal Database. PODS 1985: 51-56
60. Volkert Brosda, Gottfried Vossen: Updating a Relational Database through a Universal Schema Interface. PODS 1985: 66-75
61. Paolo Atzeni, Edward P. F. Chan: Efficient Query Answering in the Representative Instance Approach. PODS 1985: 181-188
62. Lynette I. Brady: A Universal Relation Assumption Based on Entities and Relationships. ER 1985: 208-215
63. Mihalis Yannakakis: Querying Weak Instances. PODS 1984: 275-280
64. Witold Lipski Jr.: On Relational Algebra with Marked Nulls. PODS 1984: 201-203