Fuzzy relational algebra for possibility-distribution-fuzzy-relational model of fuzzy data

In the real world, there exist a lot of fuzzy data which cannot or need not be precisely defined. We distinguish two types of fuzziness: one in an attribute value itself and the other in an association of them. For such fuzzy data, we propose a possibility-distribution-fuzzy-relational model, in which fuzzy data are represented by fuzzy relations whose grades of membership and attribute values are possibility distributions. In this model, the former fuzziness is represented by a possibility distribution and the latter by a grade of membership. Relational algebra for the ordinary relational database as defined by Codd includes the traditional set operations and the special relational operations. These operations are classified into the primitive operations, namely, union, difference, extended Cartesian product, selection and projection, and the additional operations, namely, intersection, join, and division. We define the relational algebra for the possibility-distribution-fuzzy-relational model of fuzzy databases.     

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.     

On the primitivity of the division of fuzzy relations

 Allowing for flexible queries enables database users to express preferences inside elementary conditions and priorities between conditions. The division is one of the algebraic operators defined in order to query regular databases. This operation aims at the selection of A-elements which are connected with (at least) a given subset of B-elements, e.g., the stores which ordered all the items supplied by a given manufacturer. It is mainly used in the framework of the relational model of data, although it makes sense in object-oriented databases as well. In the relational context, the division is a non-primitive operation which may be expressed in terms of other operations, namely projection, Cartesian product and set difference. When fuzzy predicates appear, this operator needs to be extended to fuzzy relations and this requires the replacement of the usual implication by a fuzzy one. This paper proposes two types of meaning of the extended division and it investigates the issue of the primitivity of the extended operation (i.e., if the division of fuzzy relations is expressible in terms of other operations). The final objective is to decide whether this operator is necessary or not for the purpose of flexible querying and to help the design of a query language supporting flexible queries, among which those conveying a division of fuzzy relations.     

Efficient processing of nested Fuzzy SQL queries in a fuzzydatabase

In a fuzzy relational database where a relation is a fuzzy set of tuples and ill-known data are represented by possibility distributions, nested fuzzy queries can be expressed in the Fuzzy SQL language. Although it provides a very convenient way for users to express complex queries, a nested fuzzy query may be very inefficient to process with the naive evaluation method based on its semantics. In conventional databases, nested queries are unnested to improve the efficiency of their evaluation. In this paper, we extend the unnesting techniques to process several types of nested fuzzy queries. An extended merge-join is used to evaluate the unnested fuzzy queries. As shown by both theoretical analysis and experimental results, the unnesting techniques with the extended merge-join significantly improve the performance of evaluating nested fuzzy queries     

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.     

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.     

Generalization of strategies for fuzzy query translation in classical relational databases

Users of information systems would like to express flexible queries over the data possibly retrieving imperfect items when the perfect ones, which exactly match the selection conditions, are not available. Most commercial DBMSs are still based on the SQL for querying. Therefore, providing some flexibility to SQL can help users to improve their interaction with the systems without requiring them to learn a completely novel language. Based on the fuzzy set theory and the α-cut operation of fuzzy number, this paper presents the generic fuzzy queries against classical relational databases and develops the translation of the fuzzy queries. The generic fuzzy queries mean that the query condition consists of complex fuzzy terms as the operands and complex fuzzy relations as the operators in a fuzzy query. With different thresholds that the user chooses for the fuzzy query, the user’s fuzzy queries can be translated into precise queries for classical relational databases.     

Data dependencies in extended possibility‐based fuzzy relational databases

Based on the semantic equivalence degree the formal definitions of fuzzy functional dependencies (FFDs) and fuzzy multivalued dependencies (FMVDs) are first introduced to the fuzzy relational databases, where fuzziness of data appears in attribute values in the form of possibility attributions, as well as resemblance relations in attribute domain elements, called extended possibility‐based fuzzy relational databases. A set of inference rules for FFDs and FMVDs is then proposed. It is shown that FFDs and FMVDs are consistent and the inference rules are sound and complete, just as Armstrong's axioms for classic cases. © 2002 Wiley Periodicals, Inc.     

关系数据库中基于EPTV的模糊查询

关系数据库中空值存在不同的语义,并且会影响模糊查询结果。针对该问题,提出用标号来区分空值的语义,并且在EPTV逻辑的基础上,对关系运算和一些复杂的嵌套查询进行扩展,给出相关定义和计算方法。通过实例说明,与常规模糊查询相比,该方法能较好地反映空值对模糊查询结果的影响。     

Association algebra: a mathematical foundation for object-orienteddatabases

The application of the object-oriented (O-O) paradigm in the database management field has gained much attention in recent years. Several experimental and commercial O-O database management systems have become available. However, the existing O-O DBMSs still lack a solid mathematical foundation for the manipulation of O-O databases, the optimization of queries, and the design and selection of storage structures for supporting O-O database manipulations. This paper presents an association algebra (A-algebra) to serve as a mathematical foundation for processing O-O databases, which is analogous to the relational algebra used for processing relational databases. In this algebra, objects and their associations in an O-O database are uniformly represented by association patterns which are manipulated by a number of operators to produce other association patterns. Different from the relational algebra, in which set operations operate on relations with union-compatible structures, the A-algebra operators can operate on association patterns of homogeneous and heterogeneous structures. Different from the traditional record-based relational processing, the A-algebra allows very complex patterns of object associations to be directly manipulated. The pattern-based query formulation and the A-algebra operators are described. Some mathematical properties of the algebraic operators are presented together with their application in query decomposition and optimization. The completeness of the A-algebra is also defined and proven. The A-algebra has been used as the basis for the design and implementation of an object-oriented query language, OQL, which is the query language used in a prototype Knowledge Base Management System OSAM*.KBMS     

Null values in fuzzy databases

Since in the real world, it often occurs that information is missing, database systems clearly need some facilities to deal with missing data. With respect to traditional database systems, the most commonly adopted approach to this problem is based on null values and three valued logic. This paper deals with the semantics and the use of null values in fuzzy databases. In dealing with missing information a distinction is made between incompleteness due to unavailability and incompleteness due to inapplicability. Both the database modelling and database querying aspects are described. With respect to attribute values, incompleteness due to unavailability is modelled by possibility distributions, which is a commonly used technique in the fuzzy databases. Domain specific null values, represented by a bottom symbol, are used to model incompleteness due to inapplicability. Extended possibilistic truth values are used to formalize the impact of data manipulation and (flexible) querying operations in the presence of these null values. The different cases of appearances of null values in the handling of selection conditions of flexible database queries are described in detail.     

Fuzzy database query languages and their relational completenesstheorem

Two fuzzy database query languages are proposed. They are used to query fuzzy databases that are enhanced from relational databases in such a way that fuzzy sets are allowed in both attribute values and truth values. A fuzzy calculus query language is constructed based on the relational calculus, and a fuzzy algebra query language is also constructed based on the relational algebra. In addition, a fuzzy relational completeness theorem such that the languages have equivalent expressive power is proved     

A data model and algebra for probabilistic complex values

We present a probabilistic data model for complex values. More precisely, we introduce probabilistic complex value relations, which combine the concept of probabilistic relations with the idea of complex values in a uniform framework. We elaborate a model-theoretic definition of probabilistic combination strategies, which has a rigorous foundation on probability theory. We then define an algebra for querying database instances, which comprises the operations of selection, projection, renaming, join, Cartesian product, union, intersection, and difference. We prove that our data model and algebra for probabilistic complex values generalizes the classical relational data model and algebra. Moreover, we show that under certain assumptions, all our algebraic operations are tractable. We finally show that most of the query equivalences of classical relational algebra carry over to our algebra on probabilistic complex value relations. Hence, query optimization techniques for classical relational algebra can easily be applied to optimize queries on probabilistic complex value relations.     

An evidential reasoning approach to attribute value conflictresolution in database integration

Resolving domain incompatibility among independently developed databases often involves uncertain information. DeMichiel (1989) showed that uncertain information can be generated by the mapping of conflicting attributes to a common domain, based on some domain knowledge. We show that uncertain information can also arise when the database integration process requires information not directly represented in the component databases, but can be obtained through some summary of data. We therefore propose an extended relational model based on Dempster-Shafer theory of evidence to incorporate such uncertain knowledge about the source databases. The extended relation uses evidence sets to represent uncertainty in information, which allow probabilities to be attached to subsets of possible domain values. We also develop a full set of extended relational operations over the extended relations. In particular, an extended union operation has been formalized to combine two extended relations using Dempster's rule of combination. The closure and boundedness properties of our proposed extended operations are formulated. We also illustrate the use of extended operations by some query examples     

基于Vague关系数据模型的除操作研究

基于Vague集理论的Vague关系数据库由于其所含信息的模糊性,对应于现实世界的多种状态。为此,基于扩展的Vague关系数据模型,研究一种条件受限的Vague除操作实现方法,并给出相应的操作步骤和算法。实例分析结果表明,该实现方法可直接作用于整个Vague关系数据库,无需对Vague关系数据库对应的所有状态逐一进行扫描即可获得正确的操作结果,具有较高的执行效率。     

About quotient and division of crisp and fuzzy relations

The role and properties of the division are very well known in the context of queries addressed to regular relational databases. However, Boolean queries whose result is expressed in terms of all or nothing may turn out to be too limited to answer certain user needs and it is desirable to envisage extended queries by introducing preferences in the conditions. In this paper, two lines of extension of the division operator are studied: (i) operand relations of the division are fuzzy relations (i.e., they are made of weighted tuples) and (ii) the universal quantifier underlying the division is weakened. Various approaches to these extensions can be considered and one of our goals is to point out those which ensure that the resulting relation is a quotient (in reference to the characterization of the quotient of two integers). So doing, a sound semantics for the extended division is guaranteed.     

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     

Selection of indexes to memory-resident entities for semantic datamodels

A variation of the index selection problem for an extended relational model when all encoding of information is memory resident is discussed. The data model is the relational model extended in two ways that are common with semantic data models. One consequence of memory residence is that the search space of possible indexes is enlarged to the extent that previous methods requiring some consideration of each possibility are no longer possible. An instance of the index selection problem that includes a set of partial match queries in addition to the input schema is given. It is assumed that the set is determined by an initial phase of query optimization when applied to a fixed set of more general forms of queries that characterize the way in which information is accessed for an application. An initial choice of indexes is made, only considering their suitability for answering the partial match queries     

Converting SQL queries into relational algebra

We present an algorithm for converting a semantically meaningful SQL query into an equivalent algebraic expression. The relational algebra we employ consists of the following operators: union, intersection, difference, Cartesian product, selection, and projection. The SQL queries we consider can have an arbitrary level of nesting but are restricted in three ways. We assume that they do not contain an ORDER BY or a GROUP BY clause, all SELECTs are in fact SELECT DISTINCTs, and that no aggregate functions are used. The first two assumptions are made in order to remain faithful to the definition of a relation as a set of rows. The last assumption is needed since there is no standard for incorporating aggregate functions into a relational algebra. The research results in this paper will be useful in implementing an SQL user interface for database management systems that internally employ relational algebra. They can also be used in optimizing the evaluation of SQL queries.