Efficient Query Answering in the Representative Instance Approach.

Paolo Atzeni, Edward P. F. Chan: Efficient Query Answering in the Representative Instance Approach. PODS 1985: 181-188
  author    = {Paolo Atzeni and
               Edward P. F. Chan},
  title     = {Efficient Query Answering in the Representative Instance Approach},
  booktitle = {Proceedings of the Fourth ACM SIGACT-SIGMOD Symposium on Principles
               of Database Systems, March 25-27, 1985, Portland, Oregon},
  publisher = {ACM},
  year      = {1985},
  isbn      = {0-89791-153-9},
  pages     = {181-188},
  ee        = {, db/conf/pods/AtzeniC85.html},
  crossref  = {DBLP:conf/pods/85},
  bibsource = {DBLP,}


Given a database state, the representative instance is a relation over the universe of attributes, possibly containing nulls, satisfying the given constraints. The representative instance approach is one of the most popular for query answering in universal relation interfaces for database systems. Also, it can be used, for each relation in the database, when the relations are stored in some decomposed way, for example for the sake of normalization.

In both cases, when answering a query involving a set of attributes X, the computation of the X-total projection of the representative instance is needed. A brute force computation of the X-total projections is not feasible in general, because it would involve the whole database. We propose a class of project-join expressions, called simple chase join expressions, as an efficient means to compute the total projections when functional dependencies over an independent scheme are given as constraints. In fact, we show that for any X, the X-total projection can be computed as a union of simple chase join expressions, and that this union can be generated efficiently. Also, we study the optimization process for unions of chase join expressions, finding a simple and efficient algorithm that minimizes the number of join operations in them.

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.

Load The ACM SIGMOD Anthology, CDROM Edition, Volume 1-3, PODS '82-'98. and ... Load The ACM SIGMOD Anthology, Silver Edition, DVD 1, Proceedings. and ... BibTeX

Printed Edition

Proceedings of the Fourth ACM SIGACT-SIGMOD Symposium on Principles of Database Systems, March 25-27, 1985, Portland, Oregon. ACM 1985, ISBN 0-89791-153-9
Contents BibTeX

Online Edition: ACM Digital Library


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
Paolo Atzeni, Douglas Stott Parker Jr.: Assumptions in Relational Database Theory. PODS 1982: 1-9 BibTeX
Edward P. F. Chan: Optimal Computation of Total Projections with Unions of Simple Chase Join Expressions. SIGMOD Conference 1984: 149-163 BibTeX
Edward P. F. Chan, Alberto O. Mendelzon: Independent and Separable Database Schemes. PODS 1983: 288-296 BibTeX
Marc H. Graham, Mihalis Yannakakis: Independent Database Schemas. J. Comput. Syst. Sci. 28(1): 121-141(1984) BibTeX
Peter Honeyman: Extension Joins. VLDB 1980: 239-244 BibTeX
Peter Honeyman: Testing satisfaction of functional dependencies. J. ACM 29(3): 668-677(1982) BibTeX
William Kent: Consequences of Assuming a Universal Relation. ACM Trans. Database Syst. 6(4): 539-556(1981) BibTeX
David Maier: The Theory of Relational Databases. Computer Science Press 1983, ISBN 0-914894-42-0
Contents BibTeX
David Maier, Alberto O. Mendelzon, Yehoshua Sagiv: Testing Implications of Data Dependencies. ACM Trans. Database Syst. 4(4): 455-469(1979) BibTeX
David Maier, David Rozenshtein, David Scott Warren: Windows on the World. SIGMOD Conference 1983: 68-78 BibTeX
David Maier, Jeffrey D. Ullman, Moshe Y. Vardi: On the Foundations of the Universal Relation Model. ACM Trans. Database Syst. 9(2): 283-308(1984) BibTeX
Yehoshua Sagiv: A Characterization of Globally Consistent Databases and Their Correct Access Paths. ACM Trans. Database Syst. 8(2): 266-286(1983) BibTeX
Yehoshua Sagiv, Mihalis Yannakakis: Equivalences Among Relational Expressions with the Union and Difference Operators. J. ACM 27(4): 633-655(1980) BibTeX
Jeffrey D. Ullman: The U. R. Strikes Back. PODS 1982: 10-22 BibTeX
Jeffrey D. Ullman: Principles of Database Systems, 2nd Edition. Computer Science Press 1982, ISBN 0-914894-36-6

Referenced by

  1. Ke Wang, Marc H. Graham: Constant-Time Maintainability: A Generalization of Independence. ACM Trans. Database Syst. 17(2): 201-246(1992)
  2. Héctor J. Hernández, Edward P. F. Chan: Constant-Time-Maintainable BCNF Database Schemes. ACM Trans. Database Syst. 16(4): 571-599(1991)
  3. Ke Wang: Polynomial Time Designs toward Both BCNF and Efficient Data Manipulation. SIGMOD Conference 1990: 74-83
  4. Paolo Atzeni, Riccardo Torlone: Efficient Updates to Independent Schemes in the Weak Instance Model. SIGMOD Conference 1990: 84-93
  5. Paolo Atzeni, Edward P. F. Chan: Efficient Optimization of Simple Chase Join Expressions. ACM Trans. Database Syst. 14(2): 212-230(1989)
  6. Paolo Atzeni, Riccardo Torlone: Updating Databases in the Weak Instance Model. PODS 1989: 101-109
  7. Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume II. Computer Science Press 1989, ISBN 0-7167-8162-X
  8. Héctor J. Hernández, Edward P. F. Chan: A Characterization of Constant-time-mainteinability for BCNF Database Schemes. SIGMOD Conference 1988: 209-217
  9. Edward P. F. Chan, Héctor J. Hernández: Independence-reducible Database Schemes. PODS 1988: 163-173
  10. Paolo Atzeni, Edward P. F. Chan: Independent Database Schemes under Functional and Inclusion Dependencies. VLDB 1987: 159-166
  11. 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
  12. Paolo Atzeni, Maria Cristina De Bernardis: A New Basis for the Weak Instance Model. PODS 1987: 79-86
  13. Marc H. Graham, Ke Wang: Constant Time Maintenance or The Triumph of the fd. PODS 1986: 202-216
  14. Edward P. F. Chan, Paolo Atzeni: On the Properties and Characterization of Connection-tap-free Schemes. PODS 1986: 140-147
  15. Edward P. F. Chan, Héctor J. Hernández: On the Desirability of gamma-Acyclic BCNF Database Schemes. ICDT 1986: 105-122
  16. Yehoshua Sagiv: On Computing Restricted Projections of Representative Instances. PODS 1985: 171-180
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
ACM SIGMOD Anthology: Copyright © by ACM (, Corrections:
DBLP: Copyright © by Michael Ley (, last change: Sat May 16 23:33:47 2009