The objective of this research is to develop a formal semantic model, theoretical framework and methodology to facilitate interoperability among distributed and heterogeneous geographic database systems (GDSs). The primary research question is how to identify and resolve various data- and schematic-level conflicts among such information sources. Set theory is used to formalize the semantic model, which supports explicit modeling of the complex nature of geographic data objects. The semantic model is used as a canonical model for conceptual schema design and integration. The intension (including structure, integrity rules and meta-properties) of the database schema is captured in the semantic model. A comprehensive framework classifying various semantic conflicts is proposed. This framework is then used as a basis for automating the detection and resolution of semantic conflicts among heterogeneous databases. A methodology for conflict detection and resolution is proposed to develop interoperable system environment. The methodology is based on the concept of a "mediator." Several types of semantic mediators are defined and developed to achieve interoperability. An ontology is developed to capture various semantic conflicts. The metadata and ontology are stored in a common repository and manipulated by description logic-based operators. A query processing technique is developed to provide uniform and integrated access to the multiple heterogeneous databases. Logic is employed to formalize our methodology, which provides a unified view of the underlying representational and reasoning formalism for the semantic mediation process. A usable prototype system is implemented to provide proof of the concept underlying this work. The system has been integrated with the Internet and can be accessed through any Java-enabled web browser. Finally, the usefulness of our methodology and the system is evaluated using three different cases that represent different application domains. Various heterogeneous geospatial datasets and non-geographic datasets are used during the evaluation phase. The results of the evaluation suggest that correct identification and construction of both schema and ontology-schema mapping knowledge play very important roles in achieving interoperability at the both data and schema levels. The research adopts a multi-methodological approach that incorporates set theory, logic, prototyping, and case study.

XML has emerged as a new standard for information representation and exchange on the Internet. To efficiently process XML data, we propose the extended preorder numbering scheme, which determines the ancestor-descendant relationship between nodes in the hierarchy of XML data in constant time, and adapts to the dynamics of XML data by allocating extra space. Based on this numbering scheme, we propose sort-merge based algorithms, εA-Join and εε-Join, to process ancestor-descendant path expressions. The experimental results showed an order of magnitude performance improvement over conventional methods. We further propose the partition-based algorithms, which can be chosen by a query optimizer according to the characteristics of the input data. For complex path expressions with branches, we propose the Containment B⁺-tree (CB-tree) index and the IndexTwig algorithm. The CB-tree, which is an extension of the B⁺-tree, supports both the containment query and the reverse containment query. It is an effective indexing scheme for XML documents with or without a small number of recursions. The proposed IndexTwig algorithm works with any index supporting containment and reverse containment queries, such as the CB-tree. We also introduce a simplified output model, which outputs only the necessary result of a path expression. The output model enables the Fast Existence Test (FET) optimization to skip unnecessary data and avoid generating unwanted results. Also in this dissertation, we introduce techniques to process the predicates in XML path expressions using the EVR-tree. The EVR-tree combines the advantages of indexing on values or elements individually using B+-trees. It utilizes the high value selectivity and/or high structural selectivity, and provides ordered element access by using a priority queue. At the end of the dissertation, we introduce the XISS/R system, which is an implementation of the XML Indexing and Storage System (XISS) on top of a relational database. The XISS/R includes a web-based user interface and a XPath query engine to translate XPath queries into efficient SQL statements.

As everything in the real world changes over time, the ability to model thistemporal dimension of the real world is essential to many computerapplications. Almost every database application involves the management oftemporal data. This applies not only to relational data but also to any datathat models the real world including XML data. Expressing queries ontime-varying (relational or XML) data by using standard query language (SQLor XQuery) is more difficult than writing queries on nontemporal data.In this dissertation, we present minimal valid-time extensions to XQueryand SQL/PSM, focusing on the procedural aspect of the two query languagesand efficient evaluation of sequenced queries.For XQuery, we add valid time support to it by minimally extendingthe syntax and semantics of XQuery. We adopt a stratum approach which maps a&tauXQuery query to a conventional XQuery. The first part of the dissertationfocuses on how to performthis mapping, in particular, on mapping sequenced queries, which are byfar the most challenging. The critical issue of supporting sequenced queries(in any query language) is time-slicing the input data while retaining periodtimestamping. Timestamps are distributed throughout anXML document, rather than uniformly in tuples, complicating the temporalslicing while also providing opportunities for optimization. We propose fiveoptimizations of our initial maximally-fragmented time-slicing approach:selected node slicing, copy-based per-expression slicing, in-placeper-expression slicing, and idiomatic slicing, each of which reducesthe number of constant periods over which the query is evaluated.We also extend a conventional XML query benchmark to effect a temporal XMLquery benchmark. Experiments on this benchmark show that in-place slicingis the best. We then apply the approaches used in &tauXQuery to temporal SQL/PSM.The stratum architecture and most of the time-slicing techniques work fortemporal SQL/PSM. Empirical comparison is performed by running a variety of temporalqueries.