Generalizing database relational algebra for the treatment of incomplete or uncertain information and vague queries

This paper deals with relational databases which are extended in the sense that fuzzily known values are allowed for attributes. Precise as well as partial (imprecise, uncertain) knowledge concerning the value of the attributes are represented by means of [0,1]-valued possibility distributions in Zadeh's sense. Thus, we have to manipulate ordinary relations on Cartesian products of sets of fuzzy subsets rather than fuzzy relations. Besides, vague queries whose contents are also represented by possibility distributions can be taken into account. The basic operations of relational algebra, union, intersection, Cartesian product, projection, and selection are extended in order to deal with partial information and vague queries. Approximate equalities and inequalities modeled by fuzzy relations can also be taken into account in the selection operation. Then, the main features of a query language based on the extended relational algebra are presented. An illustrative example is provided. This approach, which enables a very general treatment of relational databases with fuzzy attribute values, makes an extensive use of dual possibility and necessity measures.     

Updating extended possibility‐based fuzzy relational databases

Two kinds of fuzziness in attribute values of the fuzzy relational databases can be distinguished: one is that attribute values are possibility distributions and the other is that there are resemblance relations in attribute domains. The fuzzy relational databases containing these two kinds of fuzziness simultaneously are called extended possibility‐based fuzzy relational databases. In this article, we focus on such fuzzy relational databases and investigate three update operations for the fuzzy relational databases, which are Insertion, Deletion, and Modification, respectively. We develop the strategies and implementation algorithms of these operations. © 2007 Wiley Periodicals, Inc. Int J Int Syst 22: 237–258, 2007.     

Intelligent reasoning using general knowledge to update specific information: A database approach

This paper describes a database framework which is similar to a relational database in style but uses alternative knowledge structures to represent uncertain data. Two knowledge structures are used, the mass assignment to represent probabilistic information and fuzzy sets to hold subjective information. We describe how the query is modified such that the selection criteria is held in the form of specific knowledge which can be updated with the more general knowledge held in the database. The updating procedure has the effect of filling in uncertain or missing information such that a final solution can be found. The operations required to perform a query are generated automatically, optimisation is performed as the operations are determined. The output from the database is in the form of a distribution over a projection of the database domain space. An example is given where a database of sea vessels can be given uncertain or noisy evidence about the characteristics of a vessel and a distribution of the likelihood of each of the vessels can be determined from the evidence.     

Resolving database incompatibility: an approach to performingrelational operations over mismatched domains

A solution to the problem of supporting relational database operations despite domain mismatch is presented. Mismatched domains occur when information must be obtained from databases that were developed independently. Domain differences are resolved by mapping conflicting attributes to common domains by means of a mechanism of virtual attributes and then applying a set of extended relational operations to the resulting values. When one-one mappings cannot be established between domains, the values that result from attribute mappings may be partial. A set of extended relational operators that formalize operations over partial values and thus manipulate the incomplete information that results from resolving domain mismatch is defined     

Efficient representation and algebraic manipulation of infinite relations in paraconsistent databases

Paraconsistent information is information that is incomplete and/or inconsistent. A data model for handling paraconsistent information in relational databases has recently been developed. In this paper, we show that a DBMS based on paraconsistent relations must be capable of handling infinite relations. We also identify classes of infinite paraconsistent relations whose members can be effectively represented and manipulated. We show that the classes of REGULAR and, under different conditions, CONTEXT-SENSITIVE as well as PSPACE paraconsistent relations are such. We also show that the CONTEXT-FREE and R.E. classes do not have the desired properties, while P, NP, LOGSPACE and NLOGSPACE also probably do not. These results help identify the kinds of relational DBMS that can be constructed for handling incomplete and inconsistent information about tuples. We finally show that all operations for the aforementioned PSPACE and CONTEXT-SENSITIVE cases can be carried out efficiently in polynomial time.     

Handling fuzzy information in extended possibility‐based fuzzy relational databases

Two kinds of fuzziness in attribute values of the fuzzy relational databases can be distinguished: One is that attribute values are possibility distributions, and the other is that there are resemblance relations in attribute domains. The fuzzy relational databases containing these two kinds of fuzziness simultaneously are called extended possibility‐based fuzzy relational databases. In this paper, we focus on such fuzzy relational databases. We classify two kinds of fuzzy data redundancies and define their removal. On this basis, we define fuzzy relational operations in relational algebra, which, being similar to the conventional relational databases, are complete and sound. In particular, we investigate fuzzy querying strategies and give the form of fuzzy querying with SQL. © 2002 Wiley Periodicals, Inc.     

Aggregation of imprecise and uncertain information in databases

Information stored in a database is often subject to uncertainty and imprecision. Probability theory provides a well-known and well understood way of representing uncertainty and may thus be used to provide a mechanism for storing uncertain information in a database. We consider the problem of aggregation using an imprecise probability data model that allows us to represent imprecision by partial probabilities and uncertainty using probability distributions. Most work to date has concentrated on providing functionality for extending the relational algebra with a view to executing traditional queries on uncertain or imprecise data. However, for imprecise and uncertain data, we often require aggregation operators that provide information on patterns in the data. Thus, while traditional query processing is tuple-driven, processing of uncertain data is often attribute-driven where we use aggregation operators to discover attribute properties. The aggregation operator that we define uses the Kullback-Leibler information divergence between the aggregated probability distribution and the individual tuple values to provide a probability distribution for the domain values of an attribute or group of attributes. The provision of such aggregation operators is a central requirement in furnishing a database with the capability to perform the operations necessary for knowledge discovery in databases     

Algebraic equivalences of nested relational operators

Algebraic optimisation is both theoretically and practically important for query processing in complex value databases. In this paper, we consider this issue and investigate some algebraic properties concerning the nested relational operators.The join operation is one of the most time-consuming operations in nested relational query processing. We introduce a new join operator, called P-join, which combines the advantages of Roth's extended natural join and Colby's recursive join for efficient data access. We also investigate some algebraic properties concerning the P-join operator and extended relational operators, which can be used for query optimisation in nested relational databases.We then examine the role of the restructuring operators nest and unnest in their interactions with the extended relational operators proposed by Roth et al. Under certain functional and mutual data dependencies, the six nested relational equations will hold.Finally, we outline the steps of a heuristic optimisation algorithm that utilises algebraic transformation rules developed in this paper and previous related work to transform an initial query to an optimised one that is more efficient to execute.     

Extending the relational model to deal with probabilistic data

According to the soundness and completeness of information in databases,the expressive form and the semantics of incomplete information are discussed in this paper.On the basis of the discussion,the current studies on incomplete data in relational databases are reviewed.In order to represent stochastic uncertainty in most general sense in the real world,probabilistic data are introduced into relational databases.An extended relational data model is presented to express and manipulate probabilistic data and the operations in relational algebra based on the extended model are defined in this paper.     

次协调数据库中的域关系演算

次协调数据库的数据模型是用来处理数据库中两类不确定信息,即不完全信息和不一致信息(矛盾信息)。关系演算语言是表达关系数据模型中的数据操作的一种方式。域关系演算是以域为变量进行的关系演算。文中提出了一种4值的域关系演算来查询次协调数据库,它的语法与普通关系上的2值域关系演算相似,但是这种新的4值语义能够有效的查询不完全信息和不一致信息。这为次协调数据库中的类SQL语言及实现提供了理论依据,进而为次协调数据库的应用打下坚实基础。     

非确定性数据库中空值处理

尽管关系数据库有很多优势,但它缺乏一种处理非确定性数据的能力.目前,已经提出了几种将非确定性结合到关系数据库模型的方法,它们对关系数据库模型做了诸多扩展.但空值问题依旧存在,一些模型根本就没有考虑空值因素.这违背了非确定性数据库要更加真实地反应现实世界的初衷.为此,给出了一种非确定性数据库系统中空值处理方法,改进现有非确定性数据库模型中对空值处理不完善的情况.     

Queries on change in an extended relational model

A data model that allows for the storage of detailed change history in so-called backlog relations is described. Its extended relational algebra, in conjunction with the extended data structures, provides a powerful tool for the retrieval of patterns and exceptions in change history. An operator, Σ, based on the notion of compact active domain is introduced. It groups data not in predefined groups but in groups that fit the data. This operator further expands the retrieval capabilities of the algebra. The expressive power of the algebra is demonstrated by examples, some of which show how patterns and exceptions in change history can be detected. Sample applications of this work are statistical and scientific databases, monitoring (of databases, manufacturing plants, power plants, etc.), CAD, and CASE     

An extended algebra for constraint databases

Constraint relational databases use constraints to both model and query data. A constraint relation contains a finite set of generalized tuples. Each generalized tuple is represented by a conjunction of constraints on a given logical theory and, depending on the logical theory and the specific conjunction of constraints, it may possibly represent an infinite set of relational tuples. For their characteristics, constraint databases are well suited to model multidimensional and structured data, like spatial and temporal data. The definition of an algebra for constraint relational databases is important in order to make constraint databases a practical technology. We extend the previously defined constraint algebra (called generalized relational algebra). First, we show that the relational model is not the only possible semantic reference model for constraint relational databases and we show how constraint relations can be interpreted under the nested relational model. Then, we introduce two distinct classes of constraint algebras, one based on the relational algebra, and one based on the nested relational algebra, and we present an algebra of the latter type. The algebra is proved equivalent to the generalized relational algebra when input relations are modified by introducing generalized tuple identifiers. However, from a user point of view, it is more suitable. Thus, the difference existing between such algebras is similar to the difference existing between the relational algebra and the nested relational algebra, dealing with only one level of nesting. We also show how external functions can be added to the proposed algebra     

A Generalized Query-by-Example Data Manipulation Language Based on Database Logic

The purpose of this paper is to introduce a Generalized-Query-By-Example (GQBE) data manipulation language (DML) that can be built on top of most existing databases (ie., relational, hierarchical, and network). The data manipulation language supports retrieval, insertion, deletion, and update operations and has a formal semantics based on database logic. It is also seen that GQBE can by used as a DML on external views of an integrated database. We also show the advantages of GQBE on heterogeneous databases over Zloof's QBE on relational external views.     

多关系数据挖掘方法研究

目前大多数数据挖掘方法是从单关系中发现模式,而多关系数据挖掘（MRDM）则可直接从关系数据库的多表中抽取有效模式。MRDM可以解决原有命题数据挖掘方法不能解决的问题,它不仅有更强的信息表示能力,可以表示和发现更复杂的模式,还可以在挖掘进程中有效地利用背景知识来提高挖掘效率和准确率。近年来,借鉴归纳逻辑程序设计（ILP）技术,已经形成许多多关系数据挖掘方法,如关系关联规则挖掘方法、关系分类聚类方法等。     

Outer joins and filters for instantiating objects from relationaldatabases through views

One of the approaches for integrating object-oriented programs with databases is to instantiate objects from relational databases by evaluating view queries. In that approach, it is often necessary to evaluate some joins of the query by left outer joins to prevent information loss caused by the tuples discarded by inner joins. It is also necessary to filter some relations with selection conditions to prevent the retrieval of unwanted nulls. The system should automatically prescribe joins as inner or left outer joins and generate the filters, rather than letting them be specified manually for every view definition. We develop such a mechanism in this paper. We first develop a rigorous system model to facilitate the mapping between an object-oriented model and the relational model. The system model provides a well-defined context for developing a simple mechanism. The mechanism requires only one piece of information from users: null options on an object attribute. The semantics of these options are mapped to non-null constraints on the query result. Then the system prescribes joins and generates filters accordingly. We also address reducing the number of left outer joins and the filters so that the query can be processed more efficiently     

An algebraic transformation framework for multidatabase queries

Existence of semantic conflicts between component databases severely impacts query processing in a multidatabase system. In this paper, we describe two types of semantic conflicts that have to be dealt with in the integration of databases modeling information about related sets of real-world entities. These are the entityidentification problem and theattribute value conflict problem. While thetwo-way outerjoin operation has been commonly used for resolving entity identification problem between two component relations, outerjoins using regular equality comparisons between component relation keys is shown to produce counter-intuitive entity identification result. We remedy this by defining a newkey-equality comparator in place of regular equality comparator, for outerjoins. For the attribute value conflict problem, we define aGeneralized Attribute Derivation (GAD) operation which allows user-defined attribute derivation functions to be used to compute new attributes from the component relations' attributes. By adding two-way outerjoin andGAD to the set of relational operations, the traditional algebraic transformation framework for relational queries is no longer adequate for multidatabase query processing and optimization. As a result, we introduceconstrained query tree as the multidatabase query representation. We show that some knowledge about query predicates and attribute derivation functions can be used to simplify queries. Such knowledge is modeled as an outerjoin graph attached to every outerjoin operation in the query tree. Based on this, we further extend the traditional algebraic transformation framework to include two-way outerjoins andGAD operations. Our framework demonstrates that properties of selection/join predicates and attribute derivation functions can be used to provide interesting transformation alternatives. This framework also serves as a formal ground for developing optimization strategies for multidatabase queries. Recommended by: Clement Yu     

Querying fuzzy relational databases through fuzzy domain calculus

In this paper we present a definition of a domain relational calculus for fuzzy relational databases using the GEFRED model as a starting point. It is possible to define an equivalent fuzzy tuple relational calculus and consequently we achieve the two query language levels that Codd designed for relational databases but these are extended to fuzzy relational databases: Fuzzy relational algebra (defined in the GEFRED model) and the fuzzy relational calculus which is put forward in this paper. The expressive power of this fuzzy relational calculus is demonstrated through the use of a method to translate any algebraic expression into an equivalent expression in fuzzy domain relational calculus. Furthermore, we include a useful system so that the degree to which each value has satisfied the query condition can be measured. Some examples are also included in order to clarify the definition. ©1999 John Wiley & Sons, Inc.     

Efficient Querying and Animation of Periodic Spatio-Temporal Databases

We propose a representation of spatio-temporal objects with continuous and cyclic or acyclic periodic movements. We also describe an extended relational algebra query language for databases with such objects. We show that the new spatio-temporal databases are closed under the extended relational algebra queries, and each fixed relational algebra query can be evaluated in PTIME in the size of the input database.