Efficient Query Answering in the Representative Instance Approach.

@inproceedings{DBLP:conf/pods/AtzeniC85,
  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        = {http://doi.acm.org/10.1145/325405.325429, db/conf/pods/AtzeniC85.html},
  crossref  = {DBLP:conf/pods/85},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

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.

• 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
• UNIX/LINUX/Mac: use mount point /pods8298/... 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
• UNIX/LINUX/Mac: use mount point /aDVD1/... or /cdrom/...

Printed Edition

Online Edition: ACM Digital Library

References

[ABU]

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

[AP]

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

[C1]

Edward P. F. Chan: Optimal Computation of Total Projections with Unions of Simple Chase Join Expressions. SIGMOD Conference 1984: 149-163 BibTeX

[C2]

...

[CM]

Edward P. F. Chan, Alberto O. Mendelzon: Independent and Separable Database Schemes. PODS 1983: 288-296 BibTeX

[GY]

Marc H. Graham, Mihalis Yannakakis: Independent Database Schemas. J. Comput. Syst. Sci. 28(1): 121-141(1984) BibTeX

[H1]

Peter Honeyman: Extension Joins. VLDB 1980: 239-244 BibTeX

[H2]

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

[Ke]

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

[Ma]

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

[MMS]

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

[MRW]

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

[MUV]

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

[Sa]

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

[SY]

Yehoshua Sagiv, Mihalis Yannakakis: Equivalences Among Relational Expressions with the Union and Difference Operators. J. ACM 27(4): 633-655(1980) BibTeX

[U1]

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

[U2]

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

[U3]

...

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
   Contents
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