An Object Algebra Approach to Multidatabase Query Decomposition in Donají

This paper presents an approach to query decomposition in a multidatabase environment. The unique aspect of this approach is that it is based on performing transformations over an object algebra that can be used as the basis for a global query language. In the paper, we first present our multidatabase environment and semantic framework, where a global conceptual schema based on the Object Data Management Group standard encompasses the information from heterogeneous data sources that include relational databases as well as object-oriented databases and flat file sources. The meta-data about the global schema is enhanced with information about virtual classes as well as virtual relationships and inheritance hierarchies that exist between multiple sources. The AQUA object algebra is used as the formal foundation for manipulation of the query expression over the multidatabase. AQUA is enhanced with distribution operators for dealing with data distribution issues. During query decomposition we perform an extensive analysis of traversals for path expressions that involve virtual relationships and hierarchies for access to several heterogeneous sources. The distribution operators defined in algebraic terms enhance the global algebra expression with semantic information about the structure, distribution, and localization of the data sources relevant to the solution of the query. By using an object algebra as the basis for query processing, we are able to define algebraic transformations and exploit rewriting techniques during the decomposition phase. Our use of an object algebra also provides a formal and uniform representation for dealing with an object-oriented approach to multidatabase query processing. As part of our query processing discussion, we include an overview of a global object identification approach for relating semantically equivalent objects from diverse data sources, illustrating how knowledge about global object identity is used in the decomposition and assembly processes.     

Classifying schematic and data heterogeneity in multidatabasesystems

A complete framework for enumerating and classifying the types of multidatabase system (MDBS) structural and representational discrepancies is developed. The framework is structured according to a relational database schema and is both practical and complete. It was used to build the UniSQL/M commercial multidatabase system. This MDBS was built over Structured-Query-Language-based relational database systems and a unified relational and object-oriented database system named UniSQL/X. However, the results are substantially applicable to heterogeneous database systems that use a nonrelational data model (for example, an object-oriented data model) as the common data model and allow the formulation of queries directly against the component database schemas     

多数据库系统中的模式映射方法

多数据库系统一般具有四级模式结构，全局用户只能访问全局模式，而最终的数据必须从各局部数据库系统中获得，因此必须建立多数据库系统的模式映射，它表示了局部模式通过输出模式集成为全局模式的相应转换。本文给出了一种多数据库系统中的模式映射方法，并使用 模式映射树来存储和表达这种模式映射。     

Providing views and closure for the object data management group object model

The object data management group (ODMG) object model offers a standard for object-oriented database designers, while attempting to address some issues of interoperability. This research is focused on the viability of using the ODMG data model as a canonical data model in a multidatabase environment, and where weaknesses are identified we have proposed amendments to enable the model to suit the specific needs of this type of distributed database system. This paper describes our efforts to extend its relational style algebra, and to provide query closure and a viewing mechanism for object query language to construct multidatabase schemas.     

基于模式集成语义的查询处理

在采用面向对象模型作为公共数据模型的多数据库系统中，基于模式集成语义的查询处理不仅要实现针对集成模式查询到针对输出模式查询的转换，而且要从语义上尽可能减少回答用户查询所需数据，保证对象引用的正确性.为了达到这个目标,提出了一些新的概念及基于模式集成语义的查询处理规则和路径表达式的查询处理方法.     

Query optimization in multidatabase systems considering schemaconflicts

In a multidatabase system, the participating databases are autonomous. The schemas of these databases may be different in various ways, while the same information is represented. A global query issued against the global database needs to be translated to a proper form before it can be executed in a local database. Since data requested by a query (or a part of a query) is sometimes available in multiple sites, the site (database) that processes the query with the least cost is the desired query processing site. The authors study the effect of differences in schemas on the cost of query processing in a multidatabase environment. They first classify schema conflicts to different types. For each type of conflict, they show how much more or less complex a translated query can become in comparison with the originally user-issued global query. Based on this observation, they propose an analytical method that considers the conflicts between local databases and finds the database(s) that renders the least execution cost in processing a global query. This research introduces a new level of query optimization (termed the schema-level optimization) in multidatabase environments. The results provide a new dimension of enhancement for the capability of a query optimizer in multidatabase systems     

Taxonomy-based relaxation of query answering in relational databases

Traditional information search in which queries are posed against a known and rigid schema over a structured database is shifting toward a Web scenario in which exposed schemas are vague or absent and data come from heterogeneous sources. In this framework, query answering cannot be precise and needs to be relaxed, with the goal of matching user requests with accessible data. In this paper, we propose a logical model and a class of abstract query languages as a foundation for querying relational data sets with vague schemas. Our approach relies on the availability of taxonomies, that is, simple classifications of terms arranged in a hierarchical structure. The model is a natural extension of the relational model in which data domains are organized in hierarchies, according to different levels of generalization between terms. We first propose a conservative extension of the relational algebra for this model in which special operators allow the specification of relaxed queries over vaguely structured information. We also study equivalence and rewriting properties of the algebra that can be used for query optimization. We then illustrate a logic-based query language that can provide a basis for expressing relaxed queries in a declarative way. We finally investigate the expressive power of the proposed query languages and the independence of the taxonomy in this context.     

Foundations for object-oriented query processing

A minimal framework for an object-oriented query language standard should (1) include a formal definition of a high-level data model and the syntax and semantics of associated query languages, (2) provide the functionality of relational query languages, and (3) support proofs of correctness of transformations for logical query optimization. In this paper, a high-level conceptual model for object-oriented query processing is discussed; the model includes widely-used structural abstractions such as the isa relationship, associations (properties) between complex objects and complex objects/values, and inheritance of properties. A formal, algebraic query language for the model, inspired by relational algebra, is presented. Operators of the algebra allow queries based on values, queries that manipulate entire objects, and queries that construct new objects from existing objects/values. All queries retain connections to existing database objects, providing logical access paths to data. Each query result is a class, so the algebra has the closure property. The intensional and extensional results of query operators are summarized. Two forms of logical query optimization supported by the query algebra are outlined: algebraic transformations and classifier-based optimizations (optimizations which employ inclusion and exclusion dependencies between classes).     

Logic-based query optimization for object databases

We present a technique for transferring query optimization techniques, developed for relational databases, into object databases. We demonstrate this technique for ODMG database schemas defined in ODL and object queries expressed in OQL. The object schema is represented using a logical representation (Datalog). Semantic knowledge about the object data model, e.g., class hierarchy information, relationship between objects, etc., as well as semantic knowledge about a particular schema and application domain are expressed as integrity constraints. An OQL object query is represented as a logic query and query optimization is performed in the Datalog representation. We obtain equivalent (optimized) logic queries, and subsequently obtain equivalent (optimized) OQL queries for each equivalent logic query. We present one optimization technique for semantic query optimization (SQO) based on the residue technique of U. Charavarthy et al. (1990; 1986; 1988). We show that our technique generalizes previous research on SQO for object databases. We handle a large class of OQL queries, including queries with constructors and methods. We demonstrate how SQO can be used to eliminate queries which contain contradictions and simplify queries, e.g., by eliminating joins, or by reducing the access scope for evaluating a query to some specific subclass(es). We also demonstrate how the definition of a method or integrity constraints describing the method, can be used in optimizing a query with a method     

Producing Interoperable Queries for Relational and Object-Oriented Databases

In this paper, we develop techniques to produce interoperable queries with object and relational databases. A user poses a local query in a local query language, against a local object or relational schema. We transparently produce appropriate queries with respect to a remote target object or relational schema, corresponding to some remote database which contains data relevant to the user's query. Mapping knowledge to resolve representational heterogeneities in local and remote schemas is expressed in a canonical representation, CRmapping, and is independent of the particular data model. A canonical representation CRquery is also used to resolve heterogeneities of query languages. A set of heterogeneous transformation algorithms define the appropriate transformations from the local queries to the remote queries. The use of canonical representations (CR) allows us to represent queries independent of the particular query language, and to resolve representational conflicts in a uniform manner, independent of models and query languages.     

Query generation for retrieving data from distributed semistructured documents using a metadata interface

We describe a method for generating queries for retrieving data from distributed heterogeneous semistructured documents, and its implementation in the metadata interface DDXMI (distributed document XML metadata interchange). The proposed system generates local queries appropriate to local schemas from a user query over the global schema. The system constructs mappings between global schema and local schemas (extracted from local documents if not given), path substitution, and node identification for resolving the heterogeneity among nodes with the same label that often exist in semistructured data. The system uses Quilt as its XML query language. An experiment is reported over three local semistructured documents: ‘thesis’, ‘reports’, and ‘journal’ documents with ‘article’ global schema. The prototype was developed under Windows system with Java and JavaCC.     

An empirical investigation of factors influencing object-oriented database querying

Object-oriented databases (OODBs) provide an effective means for capturing complex data and semantic relationships underlying many real-world database applications. Because users' interactions with databases have increased significantly in today's era of client–server computing, it is important to examine users' ability to interact with such databases. We investigated a number of factors that potentially affect performance in writing queries on an OODB. First, we evaluated the utility of graphical and textual schemas associated with emerging OODBs from the perspective of database querying. Second, we examined the use of two different strategies (navigation and join) that could be used in writing OODB queries. Third, we examined a number of factors that potentially contribute to the complexity of an OODB query.Our exploratory study examined the performance of 20 graduate students in an experiment in which each participant wrote queries for two problems, one using a graphical OODB schema and the other a textual OODB schema. The participants had no prior exposure to the object-oriented data model. We found that there was no difference in query writing performance (either accuracy or time) using the graphical and textual schemas. Examination of query strategy revealed that a significant number of participants used a join strategy, rather than the navigation strategy that matches the database structure. Use of the join strategy resulted in significantly less accurate and slower query writing than did the navigation strategy. From the viewpoint of complexity, the number of objects referenced in a query, the number of starting points in the from clause, and the presence of special operators influenced both the accuracy and time of query writing.     

一个实现对象查询语言的形式化基础

在基于CORBA(common object request broker)的面向对象多数据库系统SCOPE/CIMS中，作者选择了对象数据库管理组ODMG(object database management group)提出的对象数据库标准ODMG-93的OQL(object query language)作为全局查询语言.为此，提出了一种实现OQL的形式化基础,包括适合建模OQL的一种对象演算和一种对象代数；对象演算的规范化规则和规范化步骤；对象演算与对象代数的等价映射规则及转换策略.     

Semantic query optimization for query plans of heterogeneousmultidatabase systems

New applications of information systems need to integrate a large number of heterogeneous databases over computer networks. Answering a query in these applications usually involves selecting relevant information sources and generating a query plan to combine the data automatically. As significant progress has been made in source selection and plan generation, the critical issue has been shifting to query optimization. This paper presents a semantic query optimization (SQO) approach to optimizing query plans of heterogeneous multidatabase systems. This approach provides global optimization for query plans as well as local optimization for subqueries that retrieve data from individual database sources. An important feature of our local optimization algorithm is that we prove necessary and sufficient conditions to eliminate an unnecessary join in a conjunctive query of arbitrary join topology. This feature allows our optimizer to utilize more expressive relational rules to provide a wider range of possible optimizations than previous work in SQO. The local optimization algorithm also features a new data structure called AND-OR implication graphs to facilitate the search for optimal queries. These features allow the global optimization to effectively use semantic knowledge to reduce the data transmission cost. We have implemented this approach in the PESTO (Plan Enhancement by SemanTic Optimization) query plan optimizer as a part of the SIMS information mediator. Experimental results demonstrate that PESTO can provide significant savings in query execution cost over query plan execution without optimization     

A visual query language for graphical interaction withschema-intensive databases

This paper presents a visual query language called VQL for interacting with an object-oriented schema-intensive data model. VQL allows convenient access to the various types of knowledge captured by the semantic model. It consists of a set of “graphical primitives” along with a combination grammar for creating graphical queries. The visual language is internally supported by a prolog-like predicate based query language. The formal grammar underlying the predicate based language is also presented. Apart from being able to create simple queries that can be specified in SQL or QBE, VQL can be used for making queries on any object-oriented data model including the generalization of the E-R model. VQL also handles complicated, indirect queries, specially those that require a reasoning system for query interpretation and response generation. Further, recursive queries on graph structures such as finding transitive closures of graphs may be easily specified. Perhaps the most powerful feature of VQL is its ability to provide high semantic expressibility (in being able to specify highly complex queries) while maintaining simplicity in the user's query formulation process. VQL is embedded in an object-oriented graphical database interaction environment that supports schema creation and manipulation in addition to database querying and updation. The prototype has been implemented in Smalltalk-80 running on a Sun 3/60 workstation. All the illustrations of visual interaction presented are taken from actual interaction sessions     

基于不确定数据的查询处理综述

不确定数据在一些重要应用领域中是固有存在的,如传感器网络和移动物体追踪。在不确定数据上使用传统的查询方法会使查询结果出现偏差,不能满足用户的需求。因此,基于不确定数据的查询处理受到了越来越多的关注。与在确定数据上查询不同,不确定数据上的研究工作将概率引入到数据模型中来衡量不确定对象成为结果集中元素的可能性。由于问题定义和数据模型的不同,不确定数据上的查询类型也多种多样。从问题定义、数据模型、剪枝策略和算法等角度,对基于不确定数据的范围查询、top-k查询以及skyline查询进行了介绍。     

Enabling Schema-Free XQuery with meaningful query focus

The widespread adoption of XML holds the promise that document structure can be exploited to specify precise database queries. However, users may have only a limited knowledge of the XML structure, and may be unable to produce a correct XQuery expression, especially in the context of a heterogeneous information collection. The default is to use keyword-based search and we are all too familiar with how difficult it is to obtain precise answers by these means. We seek to address these problems by introducing the notion of Meaningful Query Focus (MQF) for finding related nodes within an XML document. MQF enables users to take full advantage of the preciseness and efficiency of XQuery without requiring (perfect) knowledge of the document structure. Such a Schema-Free XQuery is potentially of value not just to casual users with partial knowledge of schema, but also to experts working in data integration or data evolution. In such a context, a schema-free query, once written, can be applied universally to multiple data sources that supply similar content under different schemas, and applied “forever” as these schemas evolve. Our experimental evaluation found that it is possible to express a wide variety of queries in a schema-free manner and efficiently retrieve correct results over a broad diversity of schemas. Furthermore, the evaluation of a schema-free query is not expensive: using a novel stack-based algorithm we developed for computing MQF, the overhead is from 1 to 4 times the execution time of an equivalent schema-aware query. The evaluation cost of schema-free queries can be further reduced by as much as 68% using a selectivity-based algorithm we develop to enable the integration of MQF operation into the query pipeline.     

Hybrid query execution engine for large attributed graphs

Graphs are widely used for modeling complicated data such as social networks, bibliographical networks and knowledge bases. The growing sizes of graph databases motivate the crucial need for developing powerful and scalable graph-based query engines. We propose a SPARQL-like language, G-SPARQL, for querying attributed graphs. The language enables the expression of different types of graph queries that are of large interest in the databases that are modeled as large graph such as pattern matching, reachability and shortest path queries. Each query can combine both structural predicates and value-based predicates (on the attributes of the graph nodes/edges). We describe an algebraic compilation mechanism for our proposed query language which is extended from the relational algebra and based on the basic construct of building SPARQL queries, the Triple Pattern. We describe an efficient hybrid Memory/Disk representation of large attributed graphs where only the topology of the graph is maintained in memory while the data of the graph are stored in a relational database. The execution engine of our proposed query language splits parts of the query plan to be pushed inside the relational database (using SQL) while the execution of other parts of the query plan is processed using memory-based algorithms, as necessary. Experimental results on real and synthetic datasets demonstrate the efficiency and the scalability of our approach and show that our approach outperforms native graph databases by several factors.     

Schema mapping and query translation in heterogeneous P2P XML databases

Peers in a peer-to-peer data management system often have heterogeneous schemas and no mediated global schema. To translate queries across peers, we assume each peer provides correspondences between its schema and a small number of other peer schemas. We focus on query reformulation in the presence of heterogeneous XML schemas, including data–metadata conflicts. We develop an algorithm for inferring precise mapping rules from informal schema correspondences. We define the semantics of query answering in this setting and develop query translation algorithm. Our translation handles an expressive fragment of XQuery and works both along and against the direction of mapping rules. We describe the HePToX heterogeneous P2P XML data management system which incorporates our results. We report the results of extensive experiments on HePToX on both synthetic and real datasets. We demonstrate our system utility and scalability on different P2P distributions.     

基于本体的关系数据集成的查询处理

为实现异构关系数据库的语义集成,针对传统集成技术存在的问题,在对语义网等相关技术进行分析的基础上,研究基于本体的关系数据集成系统中的查询处理问题,提出了一种基于本体的关系数据库集成框架。设计了基于本体的关系数据的描述方法,使用本体作为集成的全局模式来描述关系模式的语义。设计了查询重写算法,该算法可以将基于全局模式的SPARQL查询重写为针对具体关系数据库的查询,从而实现对异构关系数据库的集成。实验表明,该算法具有良好的可扩展性。