Bottom-up computation of the Fitting model for general deductive databases

General logic programs are those that contain both positive and negative subgoals in their clause bodies. For such programs Fitting proposed an elegant 3-valued minimum model semantics that avoids some impracticalities of previous approaches. Here we present a method to compute this Fitting model for deductive databases. We introducepartial relations, which are the semantic objects associated with predicate symbols, and define algebraic operators over them. The first step in our model computation method is to convert the database rules into partial relation definitions involving these operators. The second step is to build the minimum model iteratively. We give algorithms for both steps and show their termination and correctness. We also suggest extensions to our method for computing the well-founded model proposed by van Gelder, Ross and Schlipf.     

Ordered model trees: A normal form for disjunctive deductive databases

Model trees were conceived as a structure-sharing approach to represent information in disjunctive deductive databases. In this paper we introduce the concept ofordered minimal model trees as a normal form for disjunctive deductive databases. These are model trees in which an order is imposed on the elements of the Herbrand base. The properties of ordered minimal model trees are investigated as well as their possible utilization for efficient manipulation of disjunctive deductive databases. Algorithms are presented for constructing and performing operations on ordered model trees. The complexity of ordered model tree processing is addressed. Model forests are presented as an approach to reduce the complexity of ordered model tree construction and processing.This research was supported by the National Science Foundation, under the grant Nr. IRI-89-16059, the Air Force Office of Scientific Research, under the grant Nr. AFOSR-91-0350, and the Fulbright Scholar Program.This work was done while visiting at the University of Maryland Institute for Advanced Computer Studies.     

DrawCAD: using deductive object‐relational databases in CAD

Computer‐aided design (CAD) involves the use of computers in the various stages of engineering design. CAD has large volumes of data with complex structures that need to be stored and managed effectively and properly. Database systems provide general purpose programs that can be used to access and manipulate large amounts of data stored in the database. They also provide an independence between the program accessing data and the database. It is therefore important to use database systems to store CAD data in the most efficient and effective manner for easy retrieval and better management. Graphical objects can be created, in CAD, by reusing previously created objects. The data of these objects have references to the other objects they contain. Deductive object‐relational databases not only provide direct support for the effective storage and efficient access to large amounts of data with complex structures on disk, but also perform the inferences and computations to obtain the complete data of graphical objects that reuse other objects. They should be able to play a major role in CAD systems. This is the idea behind the development of the DrawCAD system. DrawCAD is a CAD system built on top of the Relationlog object‐relational deductive database system. It facilitates the creation of graphical objects by reusing previously created objects. The DrawCAD system illustrates how CAD systems can be developed, using database systems to store and manage data and also perform the inferences and computations that are normally performed by the application program. Copyright © 2003 John Wiley & Sons, Ltd.     

ConceptBase — A deductive object base for meta data management

Deductive object bases attempt to combine the advantages of deductive relational databases with those of object-oriented databases. We review modeling and implementation issues encountered during the development of ConceptBase, a prototype deductive object manager supporting the Telos object model. Significant features include: 1) The symmetric treatment of object-oriented, logic-oriented and graph-oriented perspectives, 2) an infinite metaclass hierarchy as a prerequisite for extensibility and schema evolution, 3) a simple yet powerful formal semantics used as the basis for implementation, 4) a client-server architecture supporting collaborative work in a wide-area setting. Several application experiences demonstrate the value of the approach especially in the field of meta data management.     

A framework for object migration in object-oriented databases

This article presents a framework developed for accomodating various object migrations in ‘statically-typed’ object databases. Requirements for supporting object migrations are stipulated, and a conceptual model for describing and facilitating different kinds of migrations is described. Associated issues of controlling such migrations are then addressed, along with an initial investigation on the interence of implied migration paths and the completeness of migration operators. Some guidelines are then given to help users conduct migrations more effectively. An implementation prototype on top of an object-oriented database system was built, which embodies full support of all migration types specified in the migration model.     

Minimal model generation for refined answering of generalized queries in disjunctive deductive databases

Generalized queries are defined as sets of clauses in implication form. They cover several tasks of practical importance for database maintenance such as answering positive queries, computing database completions and integrity constraints checking. We address the issue of answering generalized queries under the minimal model semantics for the class of disjunctive deductive databases (DDDBs). The advanced approach is based on having the query induce an order on the models returned by a sound and complete minimal model generating procedure. We consider answers that are true in all and those that are true in some minimal models of the theory. We address the issue of answering positive queries through the construction of the minimal model state of the DDDB, using a minimal model generating procedure. The refinements allowed by the procedure include isolating a minimal component of a disjunctive answer, the specification of possible updates to the theory to enable the derivability of certain queries and deciding the monotonicity properties of answers to different classes of queries.     

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.     

MPI framework for parallel searching in large biological databases

In this paper, we address the problem of searching huge biological databases on the scale of at least several gigabytes by utilizing parallel processing. Biological databases storing DNA sequences, protein sequences, or mass spectra are growing exponentially. Searches through these databases consume exponentially growing computational resources as well. We demonstrate herein a general use, MPI based, C++ framework for generically splitting databases amongst several computational nodes. The combined RAM of the nodes working in tandem is often sufficient to keep the entire database in memory, and therefore to search it efficiently without paging to disk. The framework runs as a persistent service, processing all submitted queries. This allows for query reordering and better utilization of the memory. Thereby, we achieve superlinear speedups compared to single processor implementations. We demonstrate the utility and speedup of the framework using a real biological database and an actual searching algorithm for mass spectrometry.     

Asynchronous control for two‐dimensional hidden Markovian jump systems with partly known mode observation conditional probabilities

This study focuses on the asynchronous control problem for two‐dimensional discrete‐time hidden Markovian jump systems where the mode observation conditional probability matrix is partly known. Considering the original system modes are invisible, the observed modes emitted from an observer serve as an alternative for stability analysis and controller design where a mode observation conditional probability matrix is constructed to characterize the emission between system modes and observed modes. Specially, only partly known information of the mode observation conditional probability matrix is accessible. With the introduction of the free‐connection weighting matrices, the asymptotic mean square stability criterion is firstly derived based on Lyapunov method. This introduction provides a further degree of relaxation and less conservatism is therefore achieved. Secondly, we present synthesis conditions for asynchronous state feedback controller design given in terms of a set of interconnected linear matrix inequalities. Moreover, cluster concept based on the partitions of observed modes is adopted which helps to decrease the number of controllers and simplify the design complexity. A numerical example, regarding the cases with and without clustering of the observed modes, is presented to illustrate the effectiveness of the proposed method.     

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     

受限真实链的非格子模型Monte Carlo模拟

探讨用高分子链的实际键长、键角、旋转异构态和无扰链时的条件概率,逐链段生成样本高分子链,研究受限真实链分子构象统计的可能性。并就两板间、圆管内真实链的计算结果与标度律的一些理论推导结论比较。结果表明:刚性近似之下,用无扰态时的条件概率生成样本高分子链的Monte Carlo模拟,其样本库能真实地重现平衡态时受限真实链的构象分布,适用于受限真实链的构象统计研究。     

A taxonomy for moving object queries in spatial databases

In the past decade, many works have focused on the development of moving object database indexing and querying. Most of those works have concentrated on the common spatial queries which are used with static objects as well. However, moving objects have different features from static objects which may lead to a variety of queries. Therefore, it is important to understand the full spectrum of moving object queries, even before starting to build an index structure for such objects. The aim of this paper is to provide a complete picture of the capabilities of moving object queries. Thus motivated, in this paper we propose a taxonomy of moving object queries, comprising five perspectives: (i) Location perspective, (ii) Motion perspective, (iii) Object perspective, (vi) Temporal perspective and (v) Patterns perspective. These give an overall view of what moving object queries are about. In this work, each perspective is described and examples are given.     

Coping with indefinite and negative data in deductive databases: A survey

A problem with current database systems is the limitation placed on the type of data which may be represented and manipulated within such systems. In an attempt to broaden this to a wider class of data (i.e. rules as well as facts) and a more powerful set of manipulations, the concept of a deductive database was introduced. However, for the sake of efficiency the type of rule which is allowed in a deductive database is restricted in form. This paper surveys a number of attempts to move towards less restrictive forms of rules in deductive databases which allow indefinite and negative data to be handled.     

A Bayesian model for disclosure control in statistical databases

The paper proposes a novel approach for on-line max and min query auditing, in which a Bayesian network addresses disclosures based on probabilistic inferences that can be drawn from released data. In the literature, on-line max and min auditing has been addressed with some restrictive assumptions, primarily that sensitive values must be all distinct and the sensitive field has a uniform distribution. We remove these limitations and propose a model able to: provide a graphical representation of user knowledge; deal with the implicit delivery of information that derives from denying the answer to a query; and capture user background knowledge. Finally, we discuss the results of experiments aimed at assessing the scalability of the approach, in terms of response time and size of the conditional probability table, and the usefulness of the auditor system, in terms of probability to deny.     

A framework for knowledge discovery and evolution in databases

A concept for knowledge discovery and evolution in databases is described. The key issues include: using a database query to discover new rules; using not only positive examples (answer to a query), but also negative examples to discover new rules; and harmonizing existing rules with the new rules. A tool for characterizing the exceptions in databases and evolving knowledge as a database evolves is developed     

A probabilistic framework for specular shape-from-shading

One of the problems that hinders conventional methods for shape-from-shading is the presence of local specularities which may be misidentified as high curvature surface features. In this paper we address the problem of estimating the proportions of Lambertian and specular reflection components in order to improve the quality of surface normal information recoverable using shape-from-shading. The framework for our study is provided by the iterated conditional modes algorithm. We develop a maximum a posteriori probability (MAP) estimation method for estimating the mixing proportions for Lambertian and specular reflectance, and also, for recovering local surface normals. The MAP estimation scheme has two model ingredients. First, there are separate conditional measurement densities which describe the distributions of surface normal directions for the Lambertian and specular reflectance components. We experimentally compare three different models for the specular component. The second ingredient is a smoothness prior which models the distribution of surface normal directions over local image regions. We demonstrate the utility of method on real-world data. Ground truth data is provided by imagery obtained with crossed polaroid filters. This reveals not only that the method accurately estimates the proportion of specular reflection, but that it also results in good surface normal reconstruction in the proximity of specular highlights.     

一种新的调节交叉和变异概率的自适应算法

提出一种新的基于模糊控制策略的交叉和变异概率自适应调节算法.该算法以相邻两代群体之间平均适应度函数和标准差的差值作为输入,以交叉和变异概率的变化量作为输出.并提出了与输入相对应的自适应归一化算子以及新的基于启发式知识的模糊规则,用于交叉和变异概率的调节.对3种不同测试函数的数值仿真研究表明,与其他2种自适应模糊控制算法相比,该调节算法可使遗传算法具有更快的搜索速度和更高的搜索质量.     

A PROBABILISTIC-PROPOSITIONAL FRAMEWORK FOR THE O-THEORY INTERSECTION RULE

In a previous paper, O-theory (OT), a hybrid uncertainly theory was proposed for dealing with problems of uncertainty in logical inference. The foundations of one of the concepts introduced, the OT intersection operator, are explored in this paper. The developments rely solely on set-theoretic and probability notions which are the distinguishing features of this operator's role in the theory.

The OT intersection rule has as its basis Dempster's rule of combination which ties it closely to Dempster-Shafer theory. In this paper the OT rule will be shown to be based more fundamentally on classical probability theory. To demonstrate this, possibility sets are interpreted in a propositional framework and mass assignments are converted to the probabilistic form originally proposed by Dempster. These changes are used to show that the OT intersection rule can be derived from first principles in a probability theory of propositions. Since this derivation does not require conditional probabilities, it can be used as alternative to Bayes' theorem for combining conjunctive information consistently. Dempster's rule will be shown to be a special case of the OT intersection rule. It too will be derived using probability theory.

The formal connection between mass and probability presented originally by Dempster and used here in a propositional framework, makes distinctions between DST and probability theory less consequential. DST is still seen to be a generalization of the concept of probability, but it is also seen to fit within a probabilistic-propositiona) framework.