On Computing Restricted Projections of Representative Instances.
Yehoshua Sagiv:
On Computing Restricted Projections of Representative Instances.
PODS 1985: 171-180@inproceedings{DBLP:conf/pods/Sagiv85a,
author = {Yehoshua Sagiv},
title = {On Computing Restricted Projections of Representative Instances},
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 = {171-180},
ee = {http://doi.acm.org/10.1145/325405.325427, db/conf/pods/Sagiv85a.html},
crossref = {DBLP:conf/pods/85},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX
Abstract
A lossless database scheme with a set
of full implicational dependencies is considered.
It is shown that the restricted projection of the
representative instance onto the set of all the
attributes is expressed by a first-order formula
only if the following condition holds. The
dependencies of the database scheme are
equivalent to a set consisting of a single join
dependency and several equality generating dependencies.
If the database scheme has only
tuple generating dependencies, then the condition
states that these dependencies are equivalent to a
join dependency, and in this case it is also a
sufficient condition. If there are functional
dependencies and a single join dependency and
the database scheme is independent, then union
of tableaux for restricted projections (and even
for tableau queries) can be constructed in the
worst case in exponential time and in some cases
in polynomial time. A simpler characterization
of independent database schemes is given.
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
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
- [ASU1]
- Alfred V. Aho, Yehoshua Sagiv, Jeffrey D. Ullman:
Equivalences Among Relational Expressions.
SIAM J. Comput. 8(2): 218-246(1979) BibTeX
- [ASU2]
- Alfred V. Aho, Yehoshua Sagiv, Jeffrey D. Ullman:
Efficient Optimization of a Class of Relational Expressions.
ACM Trans. Database Syst. 4(4): 435-454(1979) BibTeX
- [Arm]
- ...
- [AC]
- Paolo Atzeni, Edward P. F. Chan:
Efficient Query Answering in the Representative Instance Approach.
PODS 1985: 181-188 BibTeX
- [BB]
- Catriel Beeri, Philip A. Bernstein:
Computational Problems Related to the Design of Normal Form Relational Schemas.
ACM Trans. Database Syst. 4(1): 30-59(1979) BibTeX
- [BMSU]
- Catriel Beeri, Alberto O. Mendelzon, Yehoshua Sagiv, Jeffrey D. Ullman:
Equivalence of Relational Database Schemes.
SIAM J. Comput. 10(2): 352-370(1981) BibTeX
- [BV1]
- Catriel Beeri, Moshe Y. Vardi:
Formal Systems for Tuple and Equality Generating Dependencies.
SIAM J. Comput. 13(1): 76-98(1984) BibTeX
- [BV2]
- Catriel Beeri, Moshe Y. Vardi:
A Proof Procedure for Data Dependencies.
J. ACM 31(4): 718-741(1984) BibTeX
- [Co]
- E. F. Codd:
A Relational Model of Data for Large Shared Data Banks.
Commun. ACM 13(6): 377-387(1970) BibTeX
- [CM]
- Ashok K. Chandra, Philip M. Merlin:
Optimal Implementation of Conjunctive Queries in Relational Data Bases.
STOC 1977: 77-90 BibTeX
- [Fa]
- Ronald Fagin:
Horn clauses and database dependencies.
J. ACM 29(4): 952-985(1982) BibTeX
- [FMUY]
- Ronald Fagin, David Maier, Jeffrey D. Ullman, Mihalis Yannakakis:
Tools for Template Dependencies.
SIAM J. Comput. 12(1): 36-59(1983) BibTeX
- [GY]
- Marc H. Graham, Mihalis Yannakakis:
Independent Database Schemas.
J. Comput. Syst. Sci. 28(1): 121-141(1984) BibTeX
- [Ho]
- Peter Honeyman:
Testing satisfaction of functional dependencies.
J. ACM 29(3): 668-677(1982) 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
- [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
- [Me]
- Alberto O. Mendelzon:
Database States and Their Tableaux.
ACM Trans. Database Syst. 9(2): 264-282(1984) BibTeX
- [Sa1]
- Yehoshua Sagiv:
Can We Use the Universal Instance Assumption Without Using Nulls?
SIGMOD Conference 1981: 108-120 BibTeX
- [Sa2]
- Yehoshua Sagiv:
Quadratic Algorithms for Minimizing Joins in Restricted Relational Expressions.
SIAM J. Comput. 12(2): 316-328(1983) BibTeX
- [Sa3]
- Yehoshua Sagiv:
A Characterization of Globally Consistent Databases and Their Correct Access Paths.
ACM Trans. Database Syst. 8(2): 266-286(1983) BibTeX
- [Sa4]
- Yehoshua Sagiv:
Evaluation of Queries in Independent Database Schemes.
J. ACM 38(1): 120-161(1991) BibTeX
- [SY]
- Yehoshua Sagiv, Mihalis Yannakakis:
Equivalences Among Relational Expressions with the Union and Difference Operators.
J. ACM 27(4): 633-655(1980) BibTeX
- [Ul]
- Jeffrey D. Ullman:
Principles of Database Systems, 2nd Edition.
Computer Science Press 1982, ISBN 0-914894-36-6
BibTeX
- [Ya]
- Mihalis Yannakakis:
Algorithms for Acyclic Database Schemes.
VLDB 1981: 82-94 BibTeX
- [YP]
- Mihalis Yannakakis, Christos H. Papadimitriou:
Algebraic Dependencies.
J. Comput. Syst. Sci. 25(1): 2-41(1982) BibTeX
Referenced by
- Ke Wang:
Some Positive Results for Boundedness of Multiple Recursive Rules.
ICDT 1995: 383-396
- Ke Wang, Marc H. Graham:
Constant-Time Maintainability: A Generalization of Independence.
ACM Trans. Database Syst. 17(2): 201-246(1992)
- Paolo Atzeni, Riccardo Torlone:
Efficient Updates to Independent Schemes in the Weak Instance Model.
SIGMOD Conference 1990: 84-93
- Irène Guessarian:
Deciding Boundedness for Uniformly Connected Datalog Programs.
ICDT 1990: 395-405
- Moshe Y. Vardi:
Automata Theory for Database Theoreticans.
PODS 1989: 83-92
- Yehoshua Sagiv, Moshe Y. Vardi:
Safety of Datalog Queries over Infinite Databases.
PODS 1989: 160-171
- Gösta Grahne:
Horn Tables - An Efficient Tool for Handling Incomplete Information in Databases.
PODS 1989: 75-82
- Stavros S. Cosmadakis:
On the First-Order Expressibility of Recursive Queries.
PODS 1989: 311-323
- Jeffrey D. Ullman:
Principles of Database and Knowledge-Base Systems, Volume II.
Computer Science Press 1989, ISBN 0-7167-8162-X
Contents - Moshe Y. Vardi:
Decidability and Undecidability Results for Boundedness of Linear Recursive Queries.
PODS 1988: 341-351
- Peter T. Wood, Alberto O. Mendelzon, Paolo Atzeni:
Idempotent Single-Predicate Horn Clauses.
ICDT 1988: 129-143
- Paolo Atzeni, Maria Cristina De Bernardis:
A New Basis for the Weak Instance Model.
PODS 1987: 79-86
- Jeffrey F. Naughton:
Data Independent Recursion in Deductive Databases.
PODS 1986: 267-279
- Marc H. Graham, Ke Wang:
Constant Time Maintenance or The Triumph of the fd.
PODS 1986: 202-216
- Stavros S. Cosmadakis, Paris C. Kanellakis:
Parallel Evaluation of Recursive Rule Queries.
PODS 1986: 280-293
- Paris C. Kanellakis:
Logic Programming and Parallel Complexity.
ICDT 1986: 1-30
- Claudia Bauzer Medeiros, Frank Wm. Tompa:
Understanding the Implications of View Update Policies.
VLDB 1985: 316-323
BibTeX
ACM SIGMOD Anthology - DBLP:
[Home | Search: Author, Title | Conferences | Journals]
ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Sat May 16 23:33:47 2009
