A survey of parallel execution strategies for transitive closure and logic programs

An important feature of database technology of the nineties is the use of parallelism for speeding up the execution of complex queries. This technology is being tested in several experimental database architectures and a few commercial systems for conventional select-project-join queries. In particular, hash-based fragmentation is used to distribute data to disks under the control of different processors in order to perform selections and joins in parallel. With the development of new query languages, and in particular with the definition of transitive closure queries and of more general logic programming queries, the new dimension of recursion has been added to query processing. Recursive queries are complex; at the same time, their regular structure is particularly suited for parallel execution, and parallelism may give a high efficiency gain. We survey the approaches to parallel execution of recursive queries that have been presented in the recent literature. We observe that research on parallel execution of recursive queries is separated into two distinct subareas, one focused on the transitive closure of Relational Algebra expressions, the other one focused on optimization of more general Datalog queries. Though the subareas seem radically different because of the approach and formalism used, they have many common features. This is not surprising, because most typical Datalog queries can be solved by means of the transitive closure of simple algebraic expressions. We first analyze the relationship between the transitive closure of expressions in Relational Algebra and Datalog programs. We then review sequential methods for evaluating transitive closure, distinguishing iterative and direct methods. We address the parallelization of these methods, by discussing various forms of parallelization. Data fragmentation plays an important role in obtaining parallel execution; we describe hash-based and semantic fragmentation. Finally, we consider Datalog queries, and present general methods for parallel rule execution; we recognize the similarities between these methods and the methods reviewed previously, when the former are applied to linear Datalog queries. We also provide a quantitative analysis that shows the impact of the initial data distribution on the performance of methods. Recommended by: Patrick Valduriez     

A framework for semantic grouping in P2P databases

Sharing of structured data in decentralized environments is a challenging problem, especially in the absence of a global schema. Social network structures map network links to semantic relations between participants in order to assist in efficient resource discovery and information exchange. In this work, we propose a scheme that automates the process of creating schema synopses from semantic clusters of peers which own autonomous relational databases. The resulting mediated schemas can be used as global interfaces for relevant queries. Active nodes are able to initiate the group schema creation process, which produces a mediated schema representative of nodes with similar semantics. Group schemas are then propagated in the overlay and used as a single interface for relevant queries. This increases both the quality and the quantity of the retrieved answers and allows for fast discovery of interest groups by joining peers. As our experimental evaluations show, this method increases both the quality and the quantity of the retrieved answers and allows for faster discovery of semantic groups by joining peers.     

A semantic modeling approach for image retrieval by content

We introduce a semantic data model to capture the hierarchical, spatial, temporal, and evolutionary semantics of images in pictorial databases. This model mimics the user's conceptual view of the image content, providing the framework and guidelines for preprocessing to extract image features. Based on the model constructs, a spatial evolutionary query language (SEQL), which provides direct image object manipulation capabilities, is presented. With semantic information captured in the model, spatial evolutionary queries are answered efficiently. Using an object-oriented platform, a prototype medical-image management system was implemented at UCLA to demonstrate the feasibility of the proposed approach.     

A semantic approach to ETL technologies

Data warehouse architectures rely on extraction, transformation and loading (ETL) processes for the creation of an updated, consistent and materialized view of a set of data sources. In this paper, we support these processes by proposing a tool that: (1) allows the semi-automatic definition of inter-attribute semantic mappings, by identifying the parts of the data source schemas which are related to the data warehouse schema, thus supporting the extraction process; and (2) groups the attribute values semantically related thus defining a transformation function for populating with homogeneous values the data warehouse.Our proposal couples and extends the functionalities of two previously developed systems: the MOMIS integration system and the RELEVANT data analysis system. The system has been experimented within a real scenario concerning the creation of a data warehouse for enterprises working in the beverage and food logistic area. The results showed that the coupled system supports effectively the extraction and transformation processes.     

Selection propagation in deductive databases from pushing selections to magic sets

This paper discusses the relationship between two optimization methods in deductive databases: the distribution of selections and the magic sets method. The former is a direct generalization of pushing selections in relational databases, and the latter realizes a more general view of selection propagation. The characteristics of the generalized form of the distribution of selections are discussed and compared to other methods. It is shown that the distribution of selections corresponds to one of the least effective variations of the magic sets method. It is also shown that both methods have essentially the same power for non-recursive queries. Hence, the magic sets method can be regarded as a natural generalization of pushing selections in relational databases.     

演绎数据库中的语义查询优化方法

语义查询优化的目的是使用语义知识来进行有效的查询，以提高查询效率，通过语义编译和语义转换，把一个查询转换成一个或多个更为有效的等价查询。本文介绍在演绎数据库中语义查询优化方法。     

IRS-III: A broker-based approach to semantic Web services

A factor limiting the take up of Web services is that all tasks associated with the creation of an application, for example, finding, composing, and resolving mismatches between Web services have to be carried out by a software developer. Semantic Web services is a combination of semantic Web and Web service technologies that promise to alleviate these problems. In this paper we describe IRS-III, a framework for creating and executing semantic Web services, which takes a semantic broker-based approach to mediating between service requesters and service providers. We describe the overall approach and the components of IRS-III from an ontological and architectural viewpoint. We then illustrate our approach through an application in the eGovernment domain.     

Semantic integrity support in SQL:1999 and commercial (object-)relational database management systems

The correctness of the data managed by database systems is vital to any application that utilizes data for business, research, and decision-making purposes. To guard databases against erroneous data not reflecting real-world data or business rules, semantic integrity constraints can be specified during database design. Current commercial database management systems provide various means to implement mechanisms to enforce semantic integrity constraints at database run-time. In this paper, we give an overview of the semantic integrity support in the most recent SQL-standard SQL:1999, and we show to what extent the different concepts and language constructs proposed in this standard can be found in major commercial (object-)relational database management systems. In addition, we discuss general design guidelines that point out how the semantic integrity features provided by these systems should be utilized in order to implement an effective integrity enforcing subsystem for a database. Received: 14 August 2000 / Accepted: 9 March 2001 / Published online: 7 June 2001     

A semantic approach to improve neighborhood formation in collaborative recommender systems

Automatic recommenders are now omnipresent in e-commerce websites, as selecting and offering to users products they may be interested in can considerably increase sales revenue. The most popular recommendation strategy is currently considered to be the collaborative filtering technique, based on offering to the user who will receive the recommendation items that were appealing to other individuals with similar preferences (the so-called neighbors). On the other hand, its principal obstacle is the sparsity problem, related to the difficulty to find overlappings in ratings when there are many items. As the product catalogue of these sites gets more and more diverse, a new problem has arisen that happens when users share likings for lots of products (for which they are reckoned to be neighbors) but they differ in products similar to the one that is being considered for recommendation. They are fake neighbors. Narrowing the range of products on which similarities between users are sought can help to avoid this, but it usually causes a worsening of the sparsity problem because the chances of finding overlappings gets lower. In this paper, a new strategy is proposed based on semantic reasoning that aims to improve the neighborhood formation in order to overcome the aforementioned fake neighborhood problem. Our approach is aimed at making more flexible the search for semantic similarities between different products, and thus not require users to rate the same products in order to be compared.     

A method for computing lexical semantic distance using linear functionals

This paper presents a novel, knowledge-based method for measuring semantic similarity in support of applications aimed at organizing and retrieving relevant textual information. We show how a quantitative context may be established for what is essentially qualitative in nature by effecting a topological transformation of the lexicon into a metric space where distance is well-defined. We illustrate the technique with a simple example and report on promising experimental results with a significant word similarity problem.     

An approach to automatic deductive synthesis of functional programs

The work deals with automatic deductive synthesis of functional programs. Formal specification of a program is taken as a mathematical existence theorem and while proving it, we derive a program and simultaneously prove that this program corresponds to given specification. Several problems have to be resolved for automatic synthesis: the choice of synthesis rules that allows us to derive the basic constructions of a functional program, order of rule application and choice of a particular induction rule. The method proposed here is based on the deductive tableau method. The basic method gives rules for functional program construction. To determine the proof strategy we use some external heuristics, including rippling. And for the induction hypothesis formation the combination of rippling and the deductive tableau method became very useful. The proposed techniques are implemented in the system ALISA (Automatic Lisp Synthesizer) and used for automatic synthesis of several functions in the Lisp language. The work has been partially supported by RFBR grant 05-01-00948a.     

线性递归规则的并行计算方法

本文通过对现有的递归规则的并行计算方法以及并行计算的二分技术的讨论，提出了一种新颖的递归规则并行计算的基本策略，并给出了一种基于线性递归规则的并行计算方法。     

演绎数据库系统dUNIFY的设计与实现

本文探讨与实现一个演绎数据库系统ｄＵＮＩＦＹ，ｄＵＮＩＦＹ以小型，实用为其设计目标，文章提出了一些新的见解与实现技术，从而使ｄＵＮＩＦＹ具有查询速度快，占用空间少的特点，并有一定功能，目前，我们正在用ｄＵＮＩＦＹ开发ＣＡＤ的应用。     

A knowledge-based approach to multiple query processing

The collective processing of multiple queries in a database system has recently received renewed attention due to its capability of improving the overall performance of a database system and its applicability to the design of knowledge-based expert systems and extensible database systems. A new multiple query processing strategy is presented which utilizes semantic knowledge on data integrity and information on predicate conditions of the access paths (plans) of queries. The processing of multiple queries is accomplished by the utilization of subset relationships between intermediate results of query executions, which are inferred employing both semantic and logical information. Given a set of fixed order access plans, the A^* algorithm is used to find the set of reformulated access plans which is optimal for a given collection of semantic knowledge.     

A semantic approach to a framework for business domain software systems

In enterprise firms, enormous amounts of electronic documents are generated by business analysts and other business domain application users. Applications that use these documents are often driven by business logic that is hard-coded together with application logic. One approach to the separation of business logic from applications is to create and maintain business and information extraction rules in an external, user-friendly format. The drawback of such an externalization is that the business rules, usually, do not have machine interpretable semantics. This situation often leads to misinterpretation of domain analysis documents, which can inhibit the productivity of computer-assisted analytical work and the effectiveness of business solutions. This paper proposes an ontology and rule-based framework for the development of business domain applications, which includes semantic processing of externalized business rules and to some extent externalization of application logic. The creation of external information extraction rules by the business analyst is a cumbersome and time consuming task. In order to overcome this problem, the framework also includes a rule learning system to semi-automate the generation of information extraction rules from source documents with the help of manual annotations. The main idea behind the work presented in this paper is to re-engineer very large enterprise information systems to adapt to Semantic Web computing techniques. The work presented in this paper is inspired by an industrial project.     

A new deductive approach to planning

We introduce a new deductive approach to planning which is based on Horn clauses. Plans as well as situations are represented as terms and, thus, are first-class objects. We do neither need frame axioms nor state-literals. The only rule of inference is the SLDE-resolution rule, i.e. SLD-resolution, where the traditional unification algorithm has been replaced by anE-unification procedure. We exemplify the properties of our method such as forward and backward reasoning, plan checking, and the integration of general theories. Finally, we present the calculus and show that it is sound and complete. An earlier version of this paper was presented at the German Workshop on Artificial Intelligence, 1989.     

A novel XML keyword query approach using entity subtree

Keyword query is an important means to find object information in XML document. Most of the existing keyword query approaches adopt the subtrees rooted at the smallest lowest common ancestors of the keyword matching nodes as the basic result units. The structural relationships among XML nodes are excessively emphasized but the semantic relevance is not fully exploited.To change this situation, we propose the concept of entity subtree and emphasis the semantic relevance among different nodes as querying information from XML. In our approach, keyword query cases are improved to a new keyword-based query language, Grouping and Categorization Keyword Expression (GCKE) and the core query algorithm, finding entity subtrees (FEST) is proposed to return high quality results by fully using the keyword semantic meanings exposed by GCKE. We demonstrate the effectiveness and the efficiency of our approach through extensive experiments.