Query Optimization for Deductive Databases

A systematic,efficient compilation method for query evaluation of Deductive Databases (DeDB) is proposed in this paper.In order to eliminate redundancy and to minimize the potentially relevant facts,which are two key issues to the efficiency of a DeDB,the compilation process is decomposed into two phases.The first is the pre-compilation phase,which is responsible for the minimization of the potentially relevant facts.The second,which we refer to as the general compilation phase,is responsible for the elimination of redundancy.The rule/goal graph devised by J.D.Ullman is appropriately extended and used as a uniform formalism.Two general algorithms corresponding to the two phases respectively are described intuitively and formally.     

Normalization of Class Hierarchy in Databases

In complex object oriented databases,the purpose of introducing class hierarchy is to express ISA semantics,to realize inheriting and to reuse schema definition codes.The schema defintition and schema evolution,based on the partial order of lattice,often cause the loss o information inheriting and the redundance of schema definition.Based on the fullness of the inheritance shown by class hierarchy,three normal forms of class hierarchy are given in this paper,and a general algorithm of normalization of class hierarchy is presented,following the Boolean algebra model of class hierarchy.The loss of information inheritance can be avoided when they are applied to schema design and schema evolution.     

Towards Restructuring and Normalization of Types in Databases

The equivalence-preserving transformation and normalization of types in object-oriented databases are discussed.Specifically,A normal form of types based on set-theoretic equivalence is proposed,rewrite rules which transform types into normal forms are presented,and the uniqueness of normal form and the completeness of rewrite rules are proved.The emphasis of this work is on normal forms and corresponding rewrite rules.It provides a new formal approach for the study of restructuring of database schema and other manipulations in object-oriented databases.     

An Overview of Data Mining and Knowledge Discovery

With massive amounts of data stored in databases,mining information and knowledge in databases has become an important issue in recent research.Researchers in many different fields have shown great interest in date mining and knowledge discovery in databases.Several emerging applications in information providing services,such as data warehousing and on-line services over the Internet,also call for various data mining and knowledge discovery tchniques to understand used behavior better,to improve the service provided,and to increase the business opportunities.In response to such a demand,this article is to provide a comprehensive survey on the data mining and knowledge discorvery techniques developed recently,and introduce some real application systems as well.In conclusion,this article also lists some problems and challenges for further research.     

Progress in the Development of National Knowledge Infrastructure

This paper presents the recent process in a long-term research project,called National Knowledge Infrastructure(or NKI).Initiated in the early 2000,the project aims to develop a multi-domain shareable knowledge base for knowledge-intensive applications.To develop NKI,we have used domain-specific ontologies as a solid basis,and have built more than 600 ontologies.Using these ontologies and our knowledge acquisition methods,we have extracted about 1.1 millions of domain assertions.For users to access our NKI knowledge,we have developed a uniform multi-modal human-knowledge interface.We have also implemented a knowledge application programming interface for various applications to share the NKI knowledge.     

An Efficient Algorithm for Processing Multi-Relation Queries in Relational Databases

After a relation scheme R is decomposed into the set of schemes ρ={R1，…，Rn},we may pose queries as if Rexisted in the database,taking a join of Ri‘s,when it is necessary to implement the query,Suppos a query involves a set of attributes S R，we want to find the smallest subset of ρ whose union includes.S.We prove that the problem is NP-complete and present a polynomial-bounded approximation algorithm.A subset of ρ whose union includes S and has a decomposition into 3NF with a lossless join and preservation of dependencies in given in the paper.     

Inferring Solids Composed of Linear and Quadratic Surfaces from Incomplete Three Views

This paper introduces an automatically reasoning system for inferring linear and quadratic surface solids from incomplete three views,The method is based on human reasoning .Initially,quadratic surface primitives are fecognized and extracted according to possibility computation.Then ,the data relative only to quadratic surface primitives are femoved from the given three views and polyhedrons are constructed based on the remaining data.The final solid is constructed by assembling all the generated quadratic surface primitives and the polyhedrons.The system has been implemented in C and OpenGL on Windows NT.The constructed solid can be observed at any angle by rotating it using the keyboard.Many examples are tested and the experimental results show that the system is very robust,and can accurately and effectively construct a suitable solid composed of linear and quadratic surfaces from incomplete three views.     

连结算法与不完全信息

本文讨论在小型计算机和工作站环境下，丢失或不完全信息对关系数据库性能的影响，并给出连接算法的三种算法逼近。     

不完全数据库中关联规则的两种求估方法

在关系数据库中,数据丢失现象常常是不可避免的。在不完全数据库中挖掘关联规则的关键问题是如何估算关联规则的支持度和置信度。给出了不完全数据库中关联规则挖掘的两种求估方法,并进行了简单的比较。     

Formalizing visual interaction with historical databases

Recent database applications are typically oriented towards a large set of non-expert users, and therefore, they need to be equipped with suitable interfaces facilitating the interaction with the system. Moreover, the incorporation of the time dimension in database systems is a desirable feature. Indeed, several temporal data models and the corresponding textual query languages have been proposed. However, there is a limited amount of research concerning the investigation of user-oriented languages for querying temporal databases. Our proposal addresses such a need. In particular, we propose a visual query environment, namely Temporal Visual Query Environment (TVQE) which provides an easier interaction of the user with temporal databases. The system adopts a diagrammatic representation of the database schema (including temporal classes and relationships) and a “graphical notebook” as interaction metaphor. In our approach, non-database experts are released from syntactical difficulties which are typical of textual languages, and they can easily express temporal queries by means of elementary graphical operations (e.g. click on a node label). Differently from many proposals in the field of visual query languages, the language underlying TVQE is provided with formal syntax and semantics. It is based on a minimal set of temporal graphical primitives (TGPs), which are defined on a Temporal Graph Model (TGM), with visual syntax and object-based semantics. In this paper we mainly concentrate on the formal aspects of TVQE, and provide some hints on the visual interaction mechanisms and implementation issues.     

Keeping secrets in incomplete databases

Controlled query evaluation (CQE) preserves confidentiality in information systems at runtime. A confidentiality policy specifies the information a certain user is not allowed to know. At each query, a censor checks whether the answer would enable the user to learn any classified information. In that case, the answer is distorted, either by lying or by refusal. We introduce a framework in which CQE can be analyzed wrt. possibly incomplete logic databases. For each distortion method, lying and refusal, a class of confidentiality-preserving mechanisms is presented. Furthermore, we specify a third approach that combines lying and refusal and compensates the disadvantages of the respective uniform methods. The enforcement methods are compared to the existing methods for complete databases. This work was partially funded by the German Research Foundation (DFG) under Grant No. BI-311/12-1. An extended abstract was presented at the LICS’05 Affiliated Workshop on Foundations of Computer Security, and is available from .     

Formalizing planning knowledge for hierarchical planning

A hierarchical planning system achieves efficiency by planning with the most important conditions first, and considering details later in the planning process. Few attempts have been made to formalize the structure of the planning knowledge for hierarchical planning. For a given domain, there is usually more than one way to define its planning knowledge. Some of the definitions can lead to efficient planning, while others may not. In this paper, we provide a set of restrictions which defines the relationships between a non-primitive action and its set of subactions. When satisfied, these restrictions guarantee improved efficiency for hierarchical planning. One important feature of these restrictions is that they are syntactic and therefore do not depend on the particular structure of any plan. Along with these restrictions, we also provide algorithms for preprocessing the planning knowledge of a hierarchical planner. When used during planning, the preprocessed operator hierarchies can enable a planner to significantly reduce its search space.     

Formalizing multiple interpretation of legal knowledge

A representation methodology for knowledge allowing multiple interpretations is described. It is based on the following conception of legal knowledge and its open texture. Since indeterminate, legal knowledge must be adapted to fit the circumstances of the cases to which it is applied. Whether a certain adaptation is lawful or not is measured by metaknowledge. But as this too is indeterminate, its adaptation to the case must be measured by metametaknowledge, etc. This hierarchical model of law is quite well-established and may serve well as a basis for a legal knowledge system. To account for the indeterminacy of law such a system should support the construction of different arguments for and against various interpretations of legal sources. However, automatizing this reasoning fully is unsound since it would imply a restriction to arguments defending interpretations anticipated at programming time. Therefore, the system must be interactive and the user's knowledge be furnished in a principled way. Contrary to the widespread opinion that classical logic is inadequate for representing open-textured knowledge, the framework outlined herein is given a formalization in first order logic.     

Processing skyline queries in incomplete distributed databases

Due to its great benefits over many database applications, skyline queries have received formidable concern in the last decades. Skyline queries attempt to assist users by identifying the set of data items which represents the best results that meet the conditions of a given query. Most of the existing skyline techniques concentrate on identifying skylines over a single relation. However, in distributed databases, the process of skyline queries required accessing multiple relations which might be located at different sites. Consequently, data items from these multiple relations need to be joined and thus transferring these data items from one site to another is unavoidable. Moreover, the previous techniques also assume that the values of dimensions for every data item are presented (complete) which is not always true as some values may be missing. In this paper, we proposed an approach for processing skyline queries in incomplete distributed databases. The approach derives skylines from multiple relations where dominated data items are removed before joining the relations to reduce the processing time and the network cost. The experimental results illustrate that our proposed approach outperforms the previous approaches in terms of processing time and network cost.     

Approximation algorithms for querying incomplete databases

Certain answers are a widely accepted semantics of query answering over incomplete databases. As their computation is a coNP-hard problem, recent research has focused on developing (polynomial time) evaluation algorithms with correctness guarantees, that is, techniques computing a sound but possibly incomplete set of certain answers. The aim is to make the computation of certain answers feasible in practice, settling for under-approximations.In this paper, we present novel evaluation algorithms with correctness guarantees, which provide better approximations than current techniques, while retaining polynomial time data complexity. The central tools of our approach are conditional tables and the conditional evaluation of queries. We propose different strategies to evaluate conditions, leading to different approximation algorithms—more accurate evaluation strategies have higher running times, but they pay off with more certain answers being returned. Thus, our approach offers a suite of approximation algorithms enabling users to choose the technique that best meets their needs in terms of balance between efficiency and quality of the results.     

Revisable knowledge discovery in databases

This article introduces the idea of using nonmonotonic inheritance networks for the storage and maintenance of knowledge discovered in data (revisable knowledge discovery in databases). While existing data mining strategies for knowledge discovery in databases typically involve initial structuring through the use of identification trees and the subsequent extraction of rules from these trees for use in rule-based expert systems, such strategies have difficulty in coping with additional information which may conflict with that already used for the automatic generation of rules. In the worst case, the entire automatic sequence may have to be repeated. If nonmonotonic inheritance networks are used instead of rules for storing knowledge discovered in databases, additional conflicting information can be inserted directly into such structures, thereby bypassing the need for recompilation. © 1996 John Wiley & Sons, Inc.     

Inference control in statistical databases with incomplete information

The paper deals with the problem of inference control in statistical databases. We consider the case when database contains incomplete information and we study consequences of that fact. We propose the interpretation of a query language as ranges to protect confidential information and give a method for protecting statistical databases with incomplete information from a disclosure.     

Parameter estimation in bayesian networks from incomplete databases

Current methods to learn Bayesian Networks from incomplete databases share the common assumption that the unreported data are missing at random. This paper describes a method—called Bound and Collapse (BC)—to learn Bayesian Networks from incomplete databases which allows the analyst to efficiently integrate information provided by the observed data and exogenous knowledge about the pattern of missing data. BC starts by bounding the set of estimates consistent with the available information and then collapses the resulting set to a point estimate via a convex combination of the extreme points, with weights depending on the assumed pattern of missing data. Experiments comparing BC to Gibbs Sampling are provided.     

Systems for knowledge discovery in databases

Knowledge-discovery systems face challenging problems from real-world databases, which tend to be dynamic, incomplete, redundant, noisy, sparse, and very large. These problems are addressed and some techniques for handling them are described. A model of an idealized knowledge-discovery system is presented as a reference for studying and designing new systems. This model is used in the comparison of three systems: CoverStory, EXPLORA, and the Knowledge Discovery Workbench. The deficiencies of existing systems relative to the model reveal several open problems for future research