Querying Heterogeneous Information Sources Using Source Descriptions

Alon Y. LevyAnand RajaramanJoann J. Ordille

article1996VLDB1,437 citationsVLDB 10-Year Best Paper Award

Presents the Information Manifold system, establishing scalable algorithms that use declarative descriptions of web source contents and query capabilities to prune irrelevant databases and generate executable query plans across hundreds of heterogeneous online sources.

Listen

Online platforms host an expanding volume of structured databases covering products, stock markets, entertainment, and enterprise directories. Standard search engines rely on keyword indexing over unstructured text and cannot execute complex, relational queries across structured web forms. Consequently, users must manually locate individual databases, submit separate queries, and stitch the results together by hand. The article evaluates and demonstrates the Information Manifold, a deployed system designed to provide a unified query interface across more than 100 heterogeneous, structured web sources without requiring users to navigate individual databases.

The evaluated approach uses a global relational and object-oriented world view against which users formulate queries. Crucially, external sources are described declaratively as queries over this world view rather than as rigid schemas. The system also introduces capability records that explicitly define the specific input-output parameter requirements and query restrictions of external systems. Using these descriptions, the architecture executes a two-stage query generation process: it first groups relevant databases into target buckets to prune irrelevant sources, and then applies a polynomial-time algorithm to order subgoals into valid, executable execution plans.

The findings show that this approach prevents exponential computational bottlenecks during query planning. Pruning based on declarative descriptions reduced candidate plan evaluations by several orders of magnitude; for instance, in a 100-source scenario where unpruned generation would evaluate over 1,000,000 combinations, the bucket algorithm evaluated only 26. Across empirical tests scaling from 20 to 100 information sources, the average generation time per plan remained below one second. The authors prove that finding an executable order for a plan operates in polynomial time when restricted to single capability records, whereas permitting multiple capability records per source causes the ordering problem to become NP-complete.

These results indicate that enterprises can scale federated query systems across hundreds of online data sources without suffering steep planning latency or rebuilding integration pipelines whenever databases are added or modified. Pipelining plans to stream initial results to users substantially lowers perceived waiting times compared to standard batch execution. For organizations managing distributed structured assets, the article demonstrates that declarative source modeling provides a practical and cost-effective alternative to hand-coded data integration wrappers.

Organizations pursuing large-scale data integration should implement declarative content modeling and explicit input-output capability constraints to streamline multi-source querying. However, decision-makers should note key operational boundaries: the system provides read-only query capabilities and intentionally omits transaction processing or data update mechanisms. Furthermore, source descriptions in the evaluated system were generated manually, and the framework relies on single capability records per source. Future operational initiatives will require automated tooling to generate source descriptions and probabilistic modeling to handle partially relevant sources.

AT&T Labs—Research Bell Laboratories Stanford University complex queries keyword queries stock market heterogeneous information sources source descriptions query planning

Levy et al (1996).pdf

Paper: KQML as an agent communication language, Tim Finin et al. (1994). Introduces foundational agent communication protocols and mediator architectures for runtime information exchange across heterogeneous distributed sources.

Paper: Web mining research: a survey, Raymond Kosala et al. (2000). Surveys the evolution of web content and structure mining, providing broader taxonomy for database and information retrieval perspectives on web data integration.
Paper: Knowledge Graphs, Aidan Hogan et al. (2020). Extends the principles of integrating and querying heterogeneous structured web sources into the modern framework of knowledge graphs and federated graph querying.

Cover for Querying Heterogeneous Information Sources Using Source Descriptions

Abstract

We witness a rapid increase in the number of structured information sources that are available online, especially on the World-Wide Web. These sources store interrelated data on topics such as product information, stock market information, entertainment, etc. We would like to use the data stored in these databases to answer complex queries that go beyond keyword searches. We describe the Information Manifold, an implemented system that provides uniform access to a heterogeneous collection of more than 100 information sources on the WWW. IM contains declarative descriptions of the contents and capabilities of the information sources. We describe algorithms that use the source descriptions to prune efficiently the set of information sources for a given query and practical algorithms to generate executable query plans. We also present experimental studies indicating that the architecture and algorithms used in the Information Manifold scale up well to several hundred information sources.

Topics

complex queries keyword queries stock market structured queries user information

Keywords

heterogeneous information sources source descriptions query planning query capabilities capability descriptions content descriptions multidatabase systems source relations conjunctive query query template

1 Introduction
2 Data Model
3 Describing Information Sources
3.1 Contents of Information Sources
3.2 Capabilities of Information Sources
3.3 Query Plans
4 Algorithms for Answering Queries
4.1 Finding an Executable Ordering
5 Implementation and Experiments
6 Related Work
7 Conclusions and Future Work
Acknowledgments
References

Knowls

Knowl 1 — Information Manifold World View and Relational-Object Data Model
model/method
The Information Manifold system models heterogeneous information sources using a global virtual schema called the world view. The data model combines the relational model with object-oriented constructs, consisting of:
1. Relations of arbitrary arity.
2. Classes organized into a class hierarchy defined by a partial order $\prec$ , where $C \prec D$ denotes that class $C$ is a subclass of class $D$ . Disjointness declarations $C \cap D = \emptyset$ can be placed on pairs of classes to specify that no object can belong to both.
3. Attributes associated with classes, which can be single-valued or multi-valued, and are inherited along the subclass hierarchy.
Classes and attributes are mapped to relations to allow uniform relational query reasoning:
- A unary relation $C(x)$ corresponds to class $C$ , where $x$ is an object identifier.
- A binary relation $A(x, y)$ corresponds to attribute $A$ on class $C$ , where $x$ is an object identifier in $C$ and $y$ is the attribute value ( $A$ -filler).
Integrity constraints enforce the object semantics over these relations:
- Inclusion dependencies: For every subclass relation $C \prec D$ , the relational inclusion dependency $C \subseteq D$ holds.
- Functional dependencies: For each auxiliary relation $A(x, y)$ representing a single-valued attribute $A$ , the functional dependency $A : X \to Y$ holds.
- Disjointness constraints: For disjoint classes $C$ and $D$ , $C \cap D = \emptyset$ holds.
User queries are range-restricted conjunctive queries over the virtual world-view relations and comparison predicates ( $<, \le, >, \ge, =, \neq$ ).
Knowl 2 — Local-as-View Source Content and Capability Descriptions
definition
In the Information Manifold, external information sources are integrated using a Local-as-View (LAV) paradigm that separately specifies their contents and their query capabilities.

Content Descriptions

The contents of a source relation $V$ (whose name is disjoint from the world-view relations) are defined as a conjunctive query over the virtual relations and comparison predicates of the world view: $V(\bar{X}) \subseteq Q_V(\bar{X})$ The containment operator $\subseteq$ explicitly formalizes source incompleteness under the open-world assumption, meaning the source contains a subset of the tuples that satisfy the condition $Q_V$ .

Capability Records

Because Web sources often impose query restrictions (such as Web form input requirements), each source relation $V$ is assigned exactly one capability record: $(S_{in}, S_{out}, S_{sel}, \min, \max)$ where:
- $S_{in}$ is a set of allowed input parameters (either variables $x \in \bar{X}$ or attribute expressions $A(x)$ ).
- $S_{out}$ is the set of parameters that the source can return as output. Every variable in $ar{X}$ must appear in $S_{in} \cup S_{out}$ .
- $S_{sel} \subseteq S_{in} \cup S_{out}$ is the set of parameters on which the source can apply comparison selections of the form $p \text{ op } c$ , where $c$ is a constant and $\text{op} \in \{<, \le, >, \ge, =, \neq\}$ .
- $\min$ and $\max$ are integers specifying the minimum and maximum number of bound input parameters from $S_{in}$ required to query the source.
An input/output instantiation produces the augmented description of $V$ , and the canonical augmented description is the one providing all inputs in $S_{in}$ , requesting all outputs in $S_{out}$ , and applying no selections.
Knowl 3 — Conjunctive Query Plans and Semantic Correctness
definition
Given a world-view conjunctive query $Q$ : $Q(\bar{X}) \leftarrow R_1(\bar{Z}_1), \dots, R_n(\bar{Z}_n), C_Q$ where $R_i$ are world-view relations and $C_Q$ is a conjunction of comparison subgoals, a plan to answer $Q$ consists of a set of executable conjunctive plans.

An executable conjunctive plan $P$ has the form: $P: Q(\bar{X}) \leftarrow V_1(\bar{U}_1)(in_1, out_1, sel_1), \dots, V_m(\bar{U}_m)(in_m, out_m, sel_m), C_P$ where:
- Each $V_i$ is a source relation.
- $in_i$ maps required input parameters in $S_{in}$ of $V_i$ to constants from the query or variables in $\bigcup_{j=1}^{i-1} out_j$ .
- $out_i \subseteq S_{out}$ specifies parameters returned by $V_i$ .
- $sel_i$ is a set of selections passed directly to source $V_i$ .
- The cardinalities of $in_i$ , $out_i$ , and $sel_i$ conform to the capability record of $V_i$ .
- $C_P$ is a set of filter selections applied locally by the query execution engine.
Plan Expansion and Semantic Correctness

The expansion $P'$ of plan $P$ is obtained by replacing each subgoal $V_i(\bar{U}_i)$ with the body of its canonical augmented definition query $Q_{V_i}$ , unifying the head variables of $Q_{V_i}$ with $\bar{U}_i$ . A plan $P$ is semantically correct if $P'$ is contained in $Q$ ( $P' \subseteq Q$ ) for every database instance of the world view that satisfies the schema integrity constraints (inclusion dependencies, functional dependencies, and class disjointness).

The set of answers to query $Q$ is defined as the union of all tuples produced by executing every semantically correct, executable conjunctive plan for $Q$ .
Knowl 4 — CreateBuckets Algorithm for Source Pruning
algorithm
The CreateBuckets algorithm prunes the combinatorial search space of information sources by associating a bucket with each query subgoal. Each bucket contains only those source relations that can contribute tuples to that specific subgoal while remaining consistent with query constraints and schema integrity dependencies.
Algorithm CreateBuckets(V, Q)
Inputs: V is a set of source content descriptions in canonical augmented form; Q is a conjunctive query of the form Q(X) <- R_1(X_1), ..., R_m(X_m), C_Q.
Output: Buckets Bucket_1, ..., Bucket_m of relevant source views for each subgoal.
for i = 1 to m do
    Bucket_i <- empty_set
    for each V in V do
        Let V have definition V(Y) <= S_1(Y_1), ..., S_n(Y_n), C_V
        for j = 1 to n do
            if R_i = S_j or (R_i and S_j are nondisjoint classes) then
                Let psi be the variable mapping on V defined as:
                    if y is the k-th variable in Y_j and y in Y then
                        psi(y) = x_k, where x_k is the k-th variable in X_i
                    else
                        psi(y) is a fresh variable not appearing in Q or V
                Let Q' be the 0-ary test query:
                    Q' <- R_1(X_1), ..., R_m(X_m), C_Q, S_1(psi(Y_1)), ..., S_n(psi(Y_n)), psi(C_V)
                if Satisfiable(Q') then
                    Bucket_i <- Bucket_i union {psi(V)}
                end if
            end if
        end for
    end for
end for
return Bucket_1, ..., Bucket_m
The procedure Satisfiable(Q') evaluates whether the conjunction of comparison predicates is mathematically satisfiable and verifies that no object variable $x$ is simultaneously assigned to two disjoint classes ( $C(x) \wedge D(x)$ where $C \cap D = \emptyset$ ).
Knowl 5 — create-executable-plan Algorithm for Ordering Subgoals under Binding Constraints
algorithm
The create-executable-plan procedure determines whether an ordering of the subgoals of a semantically correct conjunctive plan exists that satisfies the input parameter binding constraints of all involved information sources, and constructs the corresponding executable plan.
procedure create-executable-plan(Q')
Input: Q' is a semantically correct conjunctive plan with non-interpreted subgoals U_1, ..., U_n, where each U_i has capability record (in_i, out_i, sel_i, min_i, max_i). Bindings in Q' are given explicitly via equality conjuncts.
Output: An executable plan P' with ordered subgoals V_1, ..., V_n, input/output/selection triplets (V_in^i, V_out^i, V_sel^i), and local selections C_P'.
QueryBindings <- set of variables in Q' bound by values in the query
Q_out <- head variables of Q'
QuerySelections <- set of variables in Q' for which the query contains a selection
BindAvail_0 <- QueryBindings
for i = 1 to n do
    Let V_i be any subgoal U_j of Q' not chosen earlier such that at least min_j parameters in in_j are in BindAvail_{i-1}
    if no such subgoal exists then
        return plan not executable
    end if
    BindAvail_i <- BindAvail_{i-1} union out_j
    V_in^i <- minimal set of parameters in BindAvail_{i-1} that satisfied the input requirement of U_j
    V_out^i <- all parameters in out_j
end for
if Q_out is not a subset of BindAvail_n then
    return plan not executable
end if
for i = 1 to n do
    Remove any element from V_out^i that is not needed as input to a subsequent subgoal or for Q_out
    Add to V_in^i as many parameters as possible from QuerySelections union BindAvail_{i-1}, and selections using these parameters to V_sel^i, such that |V_in^i union V_sel^i| <= max_i
end for
C_P' <- all built-in atoms in Q' that are not in any V_sel^i
return (V_1, ..., V_n), {(V_in^i, V_out^i, V_sel^i)}_{i=1}^n, C_P'
Knowl 6 — Polynomial-Time Tractability of Executable Plan Ordering with Single Capability Records
theoretical result
Let $Q'$ be a semantically correct conjunctive plan. If each source relation in the content descriptions is restricted to exactly one capability record of the form $(S_{in}, S_{out}, S_{sel}, \min, \max)$ , and if there exists an ordering of the subgoals of $Q'$ that results in an executable plan satisfying the input binding constraints, then the greedy algorithm create-executable-plan is guaranteed to find an executable ordering.

The running time of create-executable-plan is polynomial in the size of $Q'$ .
Knowl 7 — NP-Completeness of Plan Ordering under Multiple Capability Records
theoretical result
If source relations in the content descriptions are permitted to have more than one capability record of the form $(S_{in}, S_{out}, S_{sel}, \min, \max)$ —such that the set of obtainable output parameters depends on which specific set of input parameters is provided—then the decision problem of determining whether a semantically correct conjunctive plan admits an executable ordering is NP-complete.
Knowl 8 — Architecture and Incremental Stream Execution in Information Manifold
model/method
The Information Manifold architecture integrates distributed heterogeneous Web sources via four primary tiers:
1. User Interface: Accepts high-level declarative conjunctive queries formulated against the virtual world view.
2. Plan Generator: Operates in three stages:
  - Relevance Reasoning: Executes CreateBuckets to prune irrelevant sources using schema constraints, class disjointness, and query predicates.
  - Logical Planner: Constructs candidate plans from the Cartesian product of the buckets, eliminates redundancies, and verifies semantic correctness via view containment ( $P' \subseteq Q$ ).
  - Execution Planner: Executes create-executable-plan to enforce input/output binding capabilities and push selections to sources.
3. Execution Engine: Executes relational algebra operators (select, project, join, union). Rather than waiting to generate all plans before execution, the engine executes each query plan as soon as it is generated in parallel with ongoing planning, providing an incremental stream of answer tuples to the user to minimize time to early results.
4. Interface Programs (Wrappers): Protocol-level adapters for structured files, Web forms, and relational/OO databases. They bind query parameters, submit remote requests, and parse hierarchically structured documents (such as HTML pages) into relational tuples using outerjoin-based normalization techniques.

Knowl 9 — Scalability and Pruning Performance Across Information Sources

data/table

The query planning performance of the Information Manifold was evaluated on an SGI Challenge 150 MHz computer using three benchmark queries across source collections scaling from 20 to 100 information sources:

Query 1: Find titles and years of movies featuring Tom Hanks.
Query 2: Find titles and reviews of movies featuring Tom Hanks.
Query 3: Find telephone number(s) for Alaska Airlines.

Query	Number of sources	Max. bucket size	Plans enumerated	Plans generated	Time per plan (sec.)	Total time (sec.)
	20	1	1	1	0.55	0.55
	40	1	1	1	0.56	0.56
1	60	2	26	2	0.85	1.70
	80	2	26	2	0.85	1.70
	100	2	26	2	0.85	1.70
	20	2	7	1	0.57	0.57
	40	3	11	2	0.48	0.96
2	60	5	35	6	0.49	2.95
	80	6	44	8	0.40	3.20
	100	7	72	8	0.75	6.00
	20	2	8	2	0.28	0.56
	40	2	8	2	0.28	0.56
3	60	2	8	2	0.28	0.56
	80	6	49	6	0.22	1.32
	100	10	120	10	0.22	2.20

Key Findings

Pruning Effectiveness: Without bucket pruning, generating plans by checking all combinations requires exploring $O(n^{|Q|})$ plans (exceeding $10^6$ candidate plans for Query 1 at 100 sources). The CreateBuckets algorithm reduces the number of enumerated candidate plans to at most 120.
Fine-Grained Semantic Pruning: At 100 sources, Query 2 generates 8 plans from 72 candidates (bucket size 7) while Query 1 generates 2 plans from 26 candidates (bucket size 2). Declarative content descriptions allow the planner to prune movie databases lacking review capabilities for Query 1 while retaining them for Query 2.
Sub-Second Latency per Plan: The average time to generate an individual plan remains between $0.22$ and $0.85$ seconds across all configurations. Because plans are executed concurrently as they are produced, the user experiences sub-second response times for initial answer streams.

Coverage note — Deliberately omitted detailed descriptions of entity correspondence heuristic functions and outerjoin wrapper parsing techniques, as they are cited from prior work rather than being original contributions of this paper.

References

1.Yigal Arens, Chin Y. Chee, Chun-Nan Hsu, and Craig A. Knoblock. Retrieving and integrating data from multiple information sources. International Journal on Intelligent and Cooperative Information Systems, 1994.
2.S. Adali, K. Candan, Y. Papakonstantinou, and V.S. Subrahmanian. Query caching and optimization in distributed mediator systems. In Proceedings of SIGMOD-96, 1996.
3.C. Collet, M. N. Huhns, and W. Shen. Resource integration using a large knowledge base in carnot. IEEE Computer, 1991.
4.S. Chaudhuri, R. Krishnamurthy, S. Potamianos, and K. Shim. Optimizing queries with materialized views. In Proceedings of ICDE-95, 1995.
5.Oren Etzioni and Dan Weld. A softbot-based interface to the internet. CACM, 37(7), 1994.
6.D. Fang, J. Hammer, and D. McLeod. The identification and resolution of semantic heterogeneity in multidatabase systems. In Multidatabase Systems: An Advanced Solution for Global Information Sharing. 1994.
7.Daniela Florescu, Louiqa Rashid, and Patrick Valduriez. Using heterogeneous equivalences for query rewriting in multidatabase systems. In COOPIS '95, 1995.
8.David Konopnicki and Oded Shmueli. W3QS: A query system for the WWW. In Proceedings VLDB, 1995.
9.A. Y. Levy, A. O. Mendelzon, Y. Sagiv, and D. Srivastava. Answering queries using views. In Proceedings of ACM PODS, 1995.
10.A. Y. Levy, A. Rajaraman, and J. J. Ordille. Query answering algorithms for information agents. In Proceedings of AAAI-96, 1996.
11.A. Y. Levy, A. Rajaraman, and J. D. Ullman. Answering queries using limited external processors. In Proceedings of ACM PODS, 1996.
12.A. Y. Levy, D. Srivastava, and T. Kirk. Data model and query evaluation in global information systems. Journal of Intelligent Information Systems, 5 (2), September 1995.
13.K. A. Morris. An algorithm for ordering subgoals in NAIL! In Proceedings ACM PODS, 1988.
14.J. J. Ordille and B. P. Miller. Distributed active catalogs and meta-data caching in descriptive name services. In Proceedings of the 13th International IEEE Conference on Distributed Computing Systems, 1993.
15.Y. Papakonstantinou, A. Gupta, H. Garcia-Molina, and J. Ullman. A query translation scheme for rapid implementation of wrappers. In In proceedings of DOOD-95, 1995.
16.Anand Rajaraman, Yehoshua Sagiv, and Jeffrey D. Ullman. Answering queries using templates with binding patterns. In Proceedings of ACM PODS 1995, 1995.
17.Anand Rajaraman and Jeffrey D. Ullman. Integrating information by outerjoins and full disjunctions. In In Proceedings of ACM PODS, 1996.
18.D. Srivastava, S. Dar, H. V. Jagadish, and A. Y. Levy. Answering queries with aggregation using views. In Proceedings of VLDB, 1996.
19.H. Z. Yang and P. A. Larson. Query transformation for PSJ-queries. In Proceedings of the 13th International VLDB Conference, pages 245-254, 1987.

Citation

MLA

Levy, A. Y., et al. “Querying Heterogeneous Information Sources Using Source Descriptions”. Very Large Data Bases, 1996, pp. 251–62, http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.38.7636.

APA

Levy, A. Y., Rajaraman, A., & Ordille, J. J. (1996). Querying Heterogeneous Information Sources Using Source Descriptions. Very Large Data Bases, 251–262. http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.38.7636

Chicago

Levy, A. Y., A. Rajaraman, and J. J. Ordille. 1996. “Querying Heterogeneous Information Sources Using Source Descriptions”. Very Large Data Bases, 251–62. http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.38.7636.

Harvard

Levy, A.Y., Rajaraman, A. and Ordille, J.J. (1996) “Querying Heterogeneous Information Sources Using Source Descriptions”, Very Large Data Bases, pp. 251–262. Available at: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.38.7636.

Vancouver

1. Levy AY, Rajaraman A, Ordille JJ (1996) Querying Heterogeneous Information Sources Using Source Descriptions. Very Large Data Bases 251–262

BibTeX

@article{levy1996querying,
  title = {Querying Heterogeneous Information Sources Using Source Descriptions},
  author = {Levy, Alon Y. and Rajaraman, Anand and Ordille, Joann J.},
  year = {1996},
  journal = {Very Large Data Bases},
  pages = {251-262},
  url = {http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.38.7636}
}

Metadata:DOI registry

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF

Querying Heterogeneous Information Sources Using Source Descriptions

Abstract

Topics

Keywords

Table of Contents

Knowls

Knowl 1 — Information Manifold World View and Relational-Object Data Model

Knowl 2 — Local-as-View Source Content and Capability Descriptions

Content Descriptions

Capability Records

Knowl 3 — Conjunctive Query Plans and Semantic Correctness

Plan Expansion and Semantic Correctness

Knowl 4 — CreateBuckets Algorithm for Source Pruning

Knowl 5 — create-executable-plan Algorithm for Ordering Subgoals under Binding Constraints

Knowl 6 — Polynomial-Time Tractability of Executable Plan Ordering with Single Capability Records

Knowl 7 — NP-Completeness of Plan Ordering under Multiple Capability Records