Mining frequent conjunctive queries in relational databases through dependency discovery

We present an approach for mining frequent conjunctive in arbitrary relational databases. Our pattern class is the simple, but appealing subclass of simple conjunctive queries. Our algorithm, called Conqueror $^+$ , is capable of detecting previously unknown functional and inclusion dependencies that hold on the database relations as well as on joins of relations. These newly detected dependencies are then used to prune redundant queries. We propose an efficient database-oriented implementation of our algorithm using SQL and provide several promising experimental results.     

Efficiently instantiating view-objects from remote relational databases

View-objects are complex objects that are instantiated by delivering a query to a database and converting the query result into a nested structure. In relational databases, query results are conventionally retrieved as a single flat relation, which contains duplicate subtuples in its composite tuples. These duplicate subtuples increase the amount of data to be handled and thus degrade performance. In this article, we describe two new methods that retrieve a query result in structures other than a single flat relation. One method retrieves a set of relation fragments, and the other retrieves a single-nested relation. We first describe their algorithms and cost models, and then present the cost comparison results in a client-server architecture with a relational main memory database residing on a server.     

XML数据库和关系数据库之比较

XML已经成为数据表示和交换的数据格式标准。随着大量XML文档的出现,应用数据库技术实现对XML数据的管理引起了越来越多研究者的兴趣。作为研究XML数据库技术的一个开始点,通过与关系数据库比较,可以深刻理解XML数据库与关系数据库的异同,进而为解决XML数据库所面临的问题,如为数据冗余控制、并发访问控制等提供必要的基础。两种数据库的比较是从数据模型、查询路径、完整性约束和规范化5个方面进行的,由于数据模型是数据库的基石,二者的数据模型从构造机制、名字的惟一性、空值、实体标识、实体问关系、文档顺序、数据结构的规则性、递归、数据自描述性等9个方面进行了详细讨论。     

Object databases as generalizations of relational databases

One attractive approach to object databases is to see them as potentially an evolutionary development from relational databases. This paper concentrates on substantiating the technical basis for this claim, and illustrates it in some detail with an upwards-compatible extension of ANSI SQL2 for conventional objects. This could serve as a foundation for the development of higher-level facilities for more complex objects.     

从关系数据库学习OWL本体的方法

提出了一种从关系数据库半自动学习OWL本体的方法.该方法在形式化表示关系数据库模式和OWL本体的基础上,遵循从关系数据库模式到OWL本体的一组通用映射方法和规则,并基于Java 2平台实现了原型工具OntoLeamer.利用OntoLeamer进行的典型案例研究表明了该方法的有效性.     

An interface between object-oriented databases and relational databases

Currently relational databases are widely used, while object-oriented databases are emerging as a new generation of database technology. This paper presents a methodology to provide effective sharing of information in object-oriented databases and relational databases. The object-oriented data model is selected as a common data model to build an integrated view of the diverse databases. An object-oriented query language is used as a standard query language. A method is developed to transform a relational data definition to an equivalent object-oriented data definition and to integrate local data definitions. Two distributed query processing methods are derived. One is for general queries and the other for a special class of restricted queries. Using the methods developed, it is possible to access distributed object-oriented databases and relational databases such that the locations and the structural differences of the databases are transparent to users.     

Keyword search in relational databases

This paper surveys research on enabling keyword search in relational databases. We present fundamental characteristics and discuss research dimensions, including data representation, ranking, efficient processing, query representation, and result presentation. Various approaches for developing the search system are described and compared within a common framework. We discuss the evolution of new research strategies to resolve the issues associated with probabilistic models, efficient top-k query processing, and schema analysis in relational databases.     

Inferring negative information from disjunctive databases

We propose criteria that any rule for inferring negative information from disjunctive databases should satisfy, and examine existing rules from this viewpoint. We then present a new inference rule, the ‘disjunctive database rule’ (DDR), and compare it to the existing rules with respect to the criteria. In particular, the DDR is equivalent to the CWA for definite databases, it infers no more negative information than the GCWA, and it interprets disjunction inclusively rather than exclusively. We generalize the DDR to a class of layered databases, describe an implementation of the DDR, ‘negation as positive failure’, and study its soundness and completeness properties.     

Mining sequential patterns from probabilistic databases

Knowledge and Information Systems - This paper considers the problem of sequential pattern mining (SPM) in probabilistic databases. Specifically, we consider SPM in situations where there is...     

Mining itemset utilities from transaction databases

The rationale behind mining frequent itemsets is that only itemsets with high frequency are of interest to users. However, the practical usefulness of frequent itemsets is limited by the significance of the discovered itemsets. A frequent itemset only reflects the statistical correlation between items, and it does not reflect the semantic significance of the items. In this paper, we propose a utility based itemset mining approach to overcome this limitation. The proposed approach permits users to quantify their preferences concerning the usefulness of itemsets using utility values. The usefulness of an itemset is characterized as a utility constraint. That is, an itemset is interesting to the user only if it satisfies a given utility constraint. We show that the pruning strategies used in previous itemset mining approaches cannot be applied to utility constraints. In response, we identify several mathematical properties of utility constraints. Then, two novel pruning strategies are designed. Two algorithms for utility based itemset mining are developed by incorporating these pruning strategies. The algorithms are evaluated by applying them to synthetic and real world databases. Experimental results show that the proposed algorithms are effective on the databases tested.     

Mining interesting association rules from customer databases and transaction databases

In this paper, we examine a new data mining issue of mining association rules from customer databases and transaction databases. The problem is decomposed into two subproblems: identifying all the large itemsets from the transaction database and mining association rules from the customer database and the large itemsets identified. For the first subproblem, we propose an efficient algorithm to discover all the large itemsets from the transaction database. Experimental results show that by our approach, the total execution time can be reduced significantly. For the second subproblem, a relationship graph is constructed according to the identified large itemsets from the transaction database and the priorities of condition attributes from the customer database. Based on the relationship graph, we present an efficient graph-based algorithm to discover interesting association rules embedded in the transaction database and the customer database.     

Discovering causal rules in relational databases

This article explores the combined application of inductive learning algorithms and causal inference techniques to the problem of discovering causal rules among the attributes of a relational database. Given some relational data each field can be considered as a random variable and a hybrid graph can be built by detecting conditional independencies among variables. The induced graph represents genuine and potential causal relations as well as spurious associations. When the variables are discrete or have been discretized to test condi tional independencies supervised induction algorithms can be used to learn causal rules that is conditional statements in which causes appear as antecedents and effects as consequences. The approach is illustrated by means of some experiments conducted on different data sets.     

Statistical relational databases: normal forms

Problems associated with defining normal forms of relational tables relevant to statistical processing are discussed. The concepts of derived identifier, class identifier, derived class-counts, count domains, compact domains, and uniform domains for statistical relational tables are introduced. The structures of the first and the second statistical-normal forms and the relational decompositions needed to achieve them are also discussed. It is shown that the statistical-normal form can be an important method to determine whether the usual statistical analysis techniques are valid. Some suggestions are presented for extending the structured query language (SQL) statements to achieve these operations on statistical relational tables. Some results linking Codd's normal forms with statistical normal forms are discussed. Relational statistical abnormalities, called outlyers, are also discussed     

Unacceptable components in fuzzy relational databases

The existence of unacceptable components, which consist of unacceptable tuples and elements in attribute values, is shown in fuzzy relational databases. The unacceptable components are created by update operations, insertion, deletion, and modification. An unacceptable tuple in a relation is a tuple such that the degree of its not belonging to that relation is greater than that of its belonging to. The unacceptable tuple can be easily eliminated from relations. There are three kinds of unacceptable elements. One case of unacceptable elements is a redundant element created by insertion and modification. Another is an element created by a possible tuple value not at all or partially satisfying integrity constraints in insertion and modification. The other is an element created by a possible tuple value completely or partially satisfying update conditions in deletion. The unacceptable elements can be eliminated from relations without loss of information. As a result, we can obtain fuzzy relational databases without unacceptable components by a reasonable way. © 1996 John Wiley & Sons, Inc.     

Set-oriented data mining in relational databases

Data mining is an important real-life application for businesses. It is critical to find efficient ways of mining large data sets. In order to benefit from the experience with relational databases, a set-oriented approach to mining data is needed. In such an approach, the data mining operations are expressed in terms of relational or set-oriented operations. Query optimization technology can then be used for efficient processing.

In this paper, we describe set-oriented algorithms for mining association rules. Such algorithms imply performing multiple joins and thus may appear to be inherently less efficient than special-purpose algorithms. We develop new algorithms that can be expressed as SQL queries, and discuss optimization of these algorithms. After analytical evaluation, an algorithm named SETM emerges as the algorithm of choice. Algorithm SETM uses only simple database primitives, viz., sorting and merge-scan join. Algorithm SETM is simple, fast, and stable over the range of parameter values. It is easily parallelized and we suggest several additional optimizations. The set-oriented nature of Algorithm SETM makes it possible to develop extensions easily and its performance makes it feasible to build interactive data mining tools for large databases.     

Adequacy of decompositions of relational databases

We consider conditions that have appeared in the literature with the purpose of defining a “good” decomposition of a relation scheme. We show that these notions are equivalent in the case that all constraints in the database are functional dependencies. This result solves an open problem of Rissanen. However, for arbitrary constraints the notions are shown to differ.     

Fuzzy relations and fuzzy relational databases

This paper deals with the connections existing between fuzzy set theory and fuzzy relational databases. Our new result dealing with fuzzy relations is how to calculate the greatest lower bound (glb) of two similarity relations. Our main contributions in fuzzy relational databases are establishing from fuzzy set theory what a fuzzy relational database should be (the result is both surprising and elegant), and making fuzzy relational databases even more robust.Our work in fuzzy relations and in fuzzy databases had led us into other interesting problems—two of which we mention in this paper. The first is primarily mathematical, and the second provides yet another connection between fuzzy set theory and artificial intelligence. In understanding similarity relations in terms of other fuzzy relations and in making fuzzy databases more robust, we work with closure and interior operators; we present some important properties of these operators. In establishing the connection between fuzzy set theory and artificial intelligence, we show that an abstraction on a set is in fact a partition on the set; that is, an abstraction defines an equivalence relation on the underlying set.