ACM SIGMOD Anthology ACM SIGMOD dblp.uni-trier.de

Integrating Information by Outerjoins and Full Disjunctions.

Anand Rajaraman, Jeffrey D. Ullman: Integrating Information by Outerjoins and Full Disjunctions. PODS 1996: 238-248
@inproceedings{DBLP:conf/pods/RajaramanU96,
  author    = {Anand Rajaraman and
               Jeffrey D. Ullman},
  title     = {Integrating Information by Outerjoins and Full Disjunctions},
  booktitle = {Proceedings of the Fifteenth ACM SIGACT-SIGMOD-SIGART Symposium
               on Principles of Database Systems, June 3-5, 1996, Montreal,
               Canada},
  publisher = {ACM Press},
  year      = {1996},
  isbn      = {0-89791-781-2},
  pages     = {238-248},
  ee        = {http://doi.acm.org/10.1145/237661.237717, db/conf/pods/RajaramanU96.html},
  crossref  = {DBLP:conf/pods/96},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

Our motivation is the piecing together of tidbits of information found on the "web" into a usable information structure. The problem is related to that of computing the natural outerjoin of many relations in a way that preserves all possible connections among facts. Such a computation has been termed a "full disjunction" by Galindo-Legaria. We are thus led to ask the question of when a full disjunction can be computed by some sequence of natural outerjoins. The answer involves a concept of from Fagin [1983] called "gamma-acyclic hypergraphs". We prove that there is a natural outerjoin sequence producing the full disjunction if and only if the set of relation schemes forms a connected, gamma-acyclic hypergraph.

Copyright © 1996 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 Fifteenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, June 3-5, 1996, Montreal, Canada. ACM Press 1996, ISBN 0-89791-781-2
Contents BibTeX

Online Edition: ACM Digital Library

[Index Terms]
[Full Text in PDF Format, 1068 KB]

References

[ANSI 1992]
...
[Bernstein, Goodman 1981]
Philip A. Bernstein, Nathan Goodman: Power of Natural Semijoins. SIAM J. Comput. 10(4): 751-771(1981) BibTeX
[Fagin 1983]
Ronald Fagin: Degrees of Acyclicity for Hypergraphs and Relational Database Schemes. J. ACM 30(3): 514-550(1983) BibTeX
[Fagin, Mendelzon, Ullman 1982]
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
[Galindo-Legaria 1994]
César A. Galindo-Legaria: Outerjoins as Disjunctions. SIGMOD Conference 1994: 348-358 BibTeX
[Graham 1979]
...
[Levy Rajaraman Ordille 1996]
Alon Y. Levy, Anand Rajaraman, Joann J. Ordille: Querying Heterogeneous Information Sources Using Source Descriptions. VLDB 1996: 251-262 BibTeX
[Lien 1982]
Y. Edmund Lien: On the Equivalence of Database Models. J. ACM 29(2): 333-362(1982) BibTeX
[Maier, Rozenshtein, Warren 1986]
...
[Maier Ullman Vardi 1984]
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
[Papakonstantinou, Garcia-Molina, Widom 1995]
Yannis Papakonstantinou, Hector Garcia-Molina, Jennifer Widom: Object Exchange Across Heterogeneous Information Sources. ICDE 1995: 251-260 BibTeX
[Rajaraman, Ullman 1995]
...
[Ullman 1989]
Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume II. Computer Science Press 1989, ISBN 0-7167-8162-X
Contents BibTeX
[Yannakakis 1982]
Mihalis Yannakakis: Algorithms for Acyclic Database Schemes. VLDB 1981: 82-94 BibTeX
[Yu, Ozsoyoglu 1979]
...

Referenced by

  1. Renée J. Miller, Laura M. Haas, Mauricio A. Hernández: Schema Mapping as Query Discovery. VLDB 2000: 77-88
  2. Yaron Kanza, Werner Nutt, Yehoshua Sagiv: Queries with Incomplete Answers over Semistructured Data. PODS 1999: 227-236
  3. Alon Y. Levy, Anand Rajaraman, Joann J. Ordille: Querying Heterogeneous Information Sources Using Source Descriptions. VLDB 1996: 251-262
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:34:16 2009