Stanford InfoLab Publication Server

Integrating Information by Outerjoins and Full Disjunctions

Rajaraman, A. and Ullman, J. (1996) Integrating Information by Outerjoins and Full Disjunctions. Technical Report. Stanford InfoLab. (Publication Note: Fifteenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, June 3-5, 1996, Montreal, Canada (PODS'96))




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 fl-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, fl-acyclic hypergraph.

Item Type:Techreport (Technical Report)
Subjects:Computer Science > Data Integration and Mediation
Projects:Information Integration
Related URLs:Project Homepage
ID Code:187
Deposited By:Import Account
Deposited On:25 Feb 2000 16:00
Last Modified:09 Dec 2008 09:29

Download statistics

Repository Staff Only: item control page