Abstract
Global information systems involve a large number of information sources distributed over computer networks. The variety of information sources and disparity of interfaces makes the task of easily locating and efficiently accessing information over the network very cumbersome. We describe an architecture for global information systems that is especially tailored to address the challenges raised in such an environment, and distinguish our architecture from architectures of multidatabase and distributed database systems. Our architecture is based on presenting a conceptually unified view of the information space to a user, specifying rich descriptions of the contents of the information sources, and using these descriptions for optimizing queries posed in the unified view. The contributions of this paper include: (1) we identify aspects of site descriptions that are useful in query optimization; (2) we describe query optimization techniques that minimize the number of information sources accessed; and (3) we demonstrate the need for interleaving planning and query execution in such a system, and present an algorithm for this purpose.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Andreesen, M., and Bina, E. (1994). NCSA Mosaic: A global hypermedia system.Internet Research.
Arens, Y., Chee, C. Y., Hsu, C. nan, and Knoblock, C. A. (1994). Retrieving and integrating data from multiple information sources.International Journal on Intelligent and Cooperative Information Systems.
Borgida, A. (1992). Description logics are not just for the FLIGHTLESS-BIRDS: A new look at the utility and foundations of description logics. Technical Report DCS-TR-295, Department of Computer Science, Rutgers University.
Borgida, A., Brachman, R. J., McGuinness, D. L., and Resnick, L. A. (1989). Classic: A structural data model for objects. InProceedings of the 1989 ACM SIGMOD International Conference on Management of Data, pages 59–67.
Borgida, A., and Patel-Schneider, P. F. (1994). A semantics and complete algorithm for subsumption in the Classic description logic.Journal of Artificial Intelligence Research, 1:277–308.
Brachman, R. J., Borgida, A., McGuinness, D. L., Patel-Schneider, P. F., and Resnick, L. A. (1991). Living with Classic: When and how to use a Kl-one-like language. In J. Sowa, editor,Principles of Semantic Networks, pages 401–456. Morgan Kaufmann, San Mateo, CA.
Chawathe, S., Garcia-Molina, H., Hammer, H., Ireland, K., Papakonstantinon, Y., Ullman, J. D., and Widom, J. (1994). The TSIMMIS project: Integration of heterogeneous information sources. InProceedings of IPSJ, Tokyo, Japan.
Chaudhuri, S., Krishnamurthy, R., Potamianos, S., and Shim, K. (1995). Optimizing queries with materialized views. InProceedings of International Conference on Data Engineering.
Collet, C., Huhns, M. N., and Shen, W.-M. (1991). Resource integration using a large knowledge base in Carnot.IEEE Computer, pages 55–62.
Etzioni, O., Golden, K., and Weld, D. (1994). Tractable closed world reasoning with updates. InProceedings of KR-94.
Genesereth, M. R. (1992). An agent-based framework for software interoperability. InProceedings of the Software Technology Conference, Los Angeles, CA.
Kifer, M., Kim, W., and Sagiv, Y. (1992). Querying object-oriented databases. InProceedings of the ACM SIGMOD Conference on Management of Data, pages 393–402, San Diego, California.
Kirk, T., Levy, A. Y., Sagiv, Y., and Srivastava, D. (1995). The Information Manifold. InWorking Notes of the AAAI Spring Symposium on Information Gathering from Heterogeneous, Distributed Environments, Stanford, CA.
Knoblock, C. A., and Levy, A. Y. (1995). Exploiting run-time information to locate relevant data sources. InWorking Notes of the AAAI Spring Symposium on Information Gathering from Heterogeneous, Distributed Environments, Stanford, CA.
Levy, A. Y., Mendelzon, A. O., Sagiv, Y., and Srivastava, D. (1995). Answering queries using views. InProceedings of the ACM Symposium on Principles of Database Systems, San Jose, CA.
Levy, A. Y, Mumick, I. S., and Sagiv, Y. (1994). Query optimization by predicate move-around. InProceedings of the International Conference on Very Large Databases, Santiago, Chile.
Levy, A. Y, Mumick, I. S., Sagiv, Y., and Shmueli, O. (1993). Equivalence, query-reachability and satisfiability in Datalog extensions. InProceedings of the ACM Symposium on Principles of Database Systems, Washington, D.C.
Levy, A. Y., and Rousset, M. C. (1995). CARIN — A language combining Horn rules and description logics. InWorking notes of the International Workshop on Description Logics, Rome, Italy.
Levy, A. Y., and Sagiv, Y. (1992). Constraints and redundancy in Datalog. InProceedings of the Eleventh ACM Symposium on Principles of Database Systems, San Diego, CA.
Litwin, W., Mark, L., and Roussopoulos, N. (1990). Interoperability of multiple autonomous databases.ACM Computing Surveys, 22(3):267–293.
MacGregor, R. M. (1987). A deductive pattern matcher. InProceedings of the Sixth National Conference on Artificial Intelligence, pages 403–408.
Morris, K. A. (1988). An algorithm for ordering subgoals in NAIL! InProceedings of the ACM Symposium on Principles of Database Systems, pages 82–88.
Rajaraman, A., Sagiv, Y., and Ullman, J. D. (1995). Answering queries using templates with binding patterns. InProceedings of the ACM Symposium on Principles of Database Systems, San Jose, CA.
Sheth, A. P., and Larson, J. A. (1990). Federated database systems for managing distributed, heterogeneous, and autonomous databases.ACM Computing Surveys, 22(3): 183–236.
Srivastava, D., and Ramakrishnan, R. (1993). Pushing constraint selections.Journal of Logic Programming, 16(3–4):361–414.
Srivastava, D., Ramakrishnan, R., Seshadri, P., and Sudarshan, S. (1993). Coral++: Adding object-orientation to a logic database language. InProceedings of the International Conference on Very Large Databases, Dublin, Ireland.
Subrahmanian, V. S., Adali, S., Brink, A., Emery, R., Lu, J., Rajput, A., Rogers, T., Ross, R., and Ward, C. HERMES: A heterogeneous reasoning and mediator system. University of Maryland Technical Report.
Ullman, J. D. (1989).Principles of Database and Knowledge-Base Systems, Volumes I and II. Computer Science Press.
Wright, J. R., Weixelbaum, E. S., Brown, K., Vesonder, G. T., Palmer, S. R., Berman, J. I., and Moore, H. H. (1993). A knowledge-based configurator that supports sales, engineering, and manufacturing at AT&T network systems. InProceedings of the Innovative Applications of Artificial Intelligence Conference, pages 183–193.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Levy, A.Y., Srivastava, D. & Kirk, T. Data model and query evaluation in global information systems. J Intell Inf Syst 5, 121–143 (1995). https://doi.org/10.1007/BF00962627
Issue Date:
DOI: https://doi.org/10.1007/BF00962627