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.     

On three classes of division queries involving ordinal preferences

In this paper, we are interested in taking preferences into account for a family of queries inspired by the relational division. A division query aims at retrieving the elements associated with a specified set of values and usually the results remain not discriminated. So, we suggest the introduction of preferences inside such queries with the following specificities: (i) the user gives his/her preferences in an ordinal way and (ii) the preferences apply to the divisor which is defined as a hierarchy of sets. Different uses of the hierarchy are investigated, which leads to queries conveying different semantics and the property of the result in terms of a quotient is studied. Special attention is paid to the implementation of such extended division queries using a regular database management system along which some experiments to support the feasibility of the approach. Moreover, the issue of empty or overabundant answers is dealt with.     

动态商空间模型及其基本性质

为解决动态环境下的问题求解,在原有的商空间模型公式研究在这种情况下构成商空间链的充分必要条件,建立相应的商逼近原理,并讨论其基本性质。最后举一个利用动态商空间模型进行问题求解的应用例子。     

Extended interval Newton method based on the precise quotient set

The interval Newton method can be used for computing an enclosure of a single simple zero of a smooth function in an interval domain. It can practically be extended to allow computing enclosures of all zeros in a given interval. This paper deals with the extended interval Newton method. An essential operation of the method is division by an interval that contains zero (extended interval division). This operation has been studied by many researchers in recent decades, but inconsistency in the research has occurred again and again. This paper adopts the definition of extended interval division redefined in recent documents (Kulisch in Arithmetic operations for floating-point intervals, 2009; Pryce in P1788: IEEE standard for interval arithmetic version 02.2, 2010). The result of the division is called the precise quotient set. Earlier definitions differ in the overestimation of the quotient set in particular cases, causing inefficiency in Newton’s method and even leading to redundant enclosures of a zero. The paper reviews and compares some extended interval quotient sets defined during the last few decades. As a central theorem, we present the fundamental properties of the extended interval Newton method based on the precise quotient set. On this basis, we develop an algorithm and a convenient program package for the extended interval Newton method. Statements on its convergence are also given. We then demonstrate the performance of the algorithm through nine carefully selected very sensitive numerical examples and show that it can compute correct enclosures of all zeros of the functions with high efficiency, particularly in cases where earlier methods are less effective.     

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.     

QSVD approach to on- and off-line state-space identification

Moonen et al. (1989 a), presented an SVD-based identification scheme for computing state-space models for multivariable linear time-invariant systems. In the present paper, this identification procedure is reformulated making use of the quotient singular value decomposition (QSVD). Here the input-output error co-variance matrix can be taken into account explicitly, thus extending the applicability of the identification scheme to the case were the input and output data are corrupted by coloured noise. It turns out that in practice, due to the use of various pre-filtering techniques (anti-aliasing, etc.), this latter case is most often encountered. The extended identification scheme explicitly compensates for the filter characteristics and the consistency of the identification results follows from the consistency results for the QSVD. The usefulness of this generalization is demonstrated. The development is largely inspired by recent progress in total least-squares solution techniques (Van Huffel 1989) for the identification of static linear relations. The present identification scheme can therefore be viewed as the analogous counterpart for identifying dynamic linear relations.     

扩展的锥形方向关系查询处理方法

通过加入距离约束,扩展锥形方向关系的描述方式,提出新的查询处理方法——扩展锥形方向二叉树,该方法能处理方向空间连接的查询过滤,通过组合方向和距离关系,提高定性推理的准确性。与传统基于索引的方法相比,该方法能够有效处理大数据集中任意对象间方向关系的查询和定性推理,实现简单、查询效率和推理准确性较高。     

Equivalence and Normal Forms for the Restricted and Bounded Fixpoint in the Nested Algebra

The nested model is an extension of the traditional, “flat” relational model in which relations can also have relation-valued entries. Its “default” query language, the nested algebra, is rather weak, unfortunately, since it is only a conservative extension of the traditional, flat relational algebra, and thus can express only a small fraction of the polynomial-time queries. Therefore, it was proposed to extend the nested algebra with a fixpoint construct, but the resulting language turned out to be too powerful: many inherently exponential queries could also be expressed. Two polynomial-time restrictions of the fixpoint closure of the nested algebra were proposed: the restricted fixpoint closure (by Gyssens and Van Gucht) and the bounded fixpoint closure (by Suciu). Here, we prove two results. First we show that both restrictions are equivalent in expressive power. The proof technique relies on known encodings of nested relations into flat ones, and on a novel technique, called type substitution, by which we reduce the equivalence of the two restrictions to its obvious counterpart in the flat relational model. Second we prove that both the bounded fixpoint queries and the restricted fixpoint queries admit normal forms, in which the fixpoint occurs exactly once. The proof technique relies on a novel encoding method of nested relations into flat ones.     

Temporal Constraints: A Survey

Temporal Constraint Satisfaction is an information technology useful for representing and answering queries about temporal occurrences and temporal relations between them. Information is represented as a Constraint Satisfaction Problem (CSP) where variables denote event times and constraints represent the possible temporal relations between them. The main tasks are two: (i) deciding consistency, and (ii) answering queries about scenarios that satisfy all constraints. This paper overviews results on several classes of Temporal CSPs: qualitative interval, qualitative point, metric point, and some of their combinations. Research has progressed along three lines: (i) identifying tractable subclasses, (ii) developing exact search algorithms, and (iii) developing polynomial-time approximation algorithms. Most available techniques are based on two principles: (i) enforcing local consistency (e.g. path-consistency) and (ii) enhancing naive backtracking search.     

一种保持语义的压缩数据立方体结构

通常数据立方体体积较大,语义关系复杂,完整的语义立方体很难实现。基于商立方体,该文提出了语义数据立方体结构(SDC),将单元格中的单元以其上界替代,并保存下界,简化了单元格的表示,保持单元格的全部语义,并可以实现单元的上卷和下钻操作。把语义关系应用到数据立方体的查询、增量更新中,使查询响应时间及更新代价大大降低。实验结果表明,SDC是有效的。     

基于等腰归一化距离的模糊粒度空间研究

本文将等腰归一化距离引入到模糊商空间中,提出了基于等腰归一化距离的模糊粒度空间理论.研究了它的结构和性质,并得到了四个重要结论.首先,下面3个叙述是等价的(定理3.2): (1) 给定X上的一个模糊等价关系;(2)给定X上的一个等腰归一化距离;(3)给定X上的一个分层递阶结构(或有序的粒度空间).其次,讨论了等腰归一化距离与Fuzzy等价关系间相互确定的对应关系,且都是一对多的关系(定理2.2,定理2.3).最后,给出了通过X上的模糊等价关系R诱导的等腰归一化距离d确定其引导的粒度上的度量dλ,且dλ正好是d在粒度X(λ)上压缩的等腰归一化距离(定理4.1), 同时给出了确定粒度空间上等腰归一化距离的方法.这些研究结论为模糊粒度计算的理论研究和应用提供了强有力的数字模型和工具, 同时表明模糊商空间的粒度计算可以在等腰归一化距离的范畴内进行,为模糊粒度计算提供了更为直观的几何解释.     

Fuzzy reasoning model under quotient space structure

In this paper, we present a theoretical framework of fuzzy reasoning model under quotient space structure. It consists of (1) introducing quotient space structure into fuzzy sets, i.e., constructing fuzzy set representations of different grain-size spaces and their relationships; (2) introducing the concept of fuzzy sets into quotient space theory, i.e., introducing fuzzy equivalence relation and discussing its corresponding reasoning in different grain-size spaces; and (3) discussing the relationship and transformation among different granular computing methodologies. The framework proposed is aimed to combine two powerful abilities in order to enhance the efficiency of fuzzy reasoning: one is the ability of computing with words based on fuzzy set methodology, the other is the ability of hierarchical problem solving based on quotient space approach.     

A new approach for fuzzy information retrieval based on weighted power-mean averaging operators

An information retrieval system can help users to retrieve documents relevant to the users’ queries. In recent years, some researchers used averaging operators (i.e., Infinite–One operators, Waller–Kraft operators, P-Norm operators and GMA operators) to handle “AND” and “OR” operations of users’ fuzzy queries for fuzzy information retrieval, but they still have some drawbacks, e.g., sometimes query results do not coincide with the intuition of the human being. In this paper, we present new averaging operators, called weighted power-mean averaging (WPMA) operators, based on the weighted power mean for dealing with fuzzy information retrieval to overcome the drawbacks of the existing methods. Furthermore, we also extend the proposed WPMA operators into the extended WPMA operators to handle weighted fuzzy queries for fuzzy information retrieval. The proposed WPMA operators are more flexible and more intelligent than the existing averaging operators to handle users’ fuzzy queries for fuzzy information retrieval.     

An efficient division algorithm for polynomial matrices

A new algorithm for carrying out the division of two polynomial matrices is presented. The quotient and remainder are directly computed in a way similar to scalar polynomial division. This method is much simpler than earlier algorithms.     

Domain-independent queries on databases with external functions

We study queries over databases with external functions, from a language-independent perspective. The input and output types of the external functions can be atomic values, flat relations, nested relations, etc. We propose a new notion of data-independence for queries on databases with external functions, which extends naturally the notion of generic queries on relational databases without external functions. In contrast to previous such notions, ours can also be applied to queries expressed in query languages with iterations. Next, we propose two natural notions of computability for queries over databases with external functions, and prove that they are equivalent, under reasonable assumptions. Thus, our definition of computability is robust. Finally, based on this equivalence result, we give examples of complete query languages with external functions. A byproduct of the equivalence result is the fact that Relational Machines (Abiteboul and V. Vianu, 1991; Abiteboul et al., 1992) are complete on nested relations: they are known not to be complete on flat relations.     

An empirical analysis of ontology-based query expansion for learning resource searches using MERLOT and the Gene ontology

This paper proposes an expansion of queries based on formal domain ontologies in the context of the search for learning resources in repositories. The expansion process uses the relation types that are represented in these models; common ontological relations, and ontological relations specific to domain and traditional terminology relations, typical of thesauri. The tests were conducted using Gene ontology as the knowledge base and MERLOT is used as the test repository. The results of this study case indicate that, at similar levels of precision, expanded queries improve levels of novelty and coverage compared to the original query (without expansion), i.e. expanded queries allow the user to retrieve relevant objects, which might not be obtained without expansion.     

模糊相容商空间与模糊子集

本文利用商空间理论中的粒度和层次概念来讨论模糊子集的结构和性质.首先将基于等价关系的商空间理论推广到基于模糊相容关系,接着讨论模糊相容关系的同构性及同构性的判别问题,最后利用模糊相容关系定义模糊子集,并讨论其性质.主要给出以下结果:(1)模糊相容关系的几种等价表示形式;(2)模糊相容关系的同构定义;(3)模糊相容关系同构的判别准则;(4)模糊相容关系下的模糊子集的定义及其相关性质;以及(5)模糊子集同构的充分必要条件.这些结果加深了我们对模糊相容关系和模糊集的理解.     

直觉模糊集的商空间

把商空间理论推广到直觉模糊集理论中,建立直觉模糊商空间。定义直觉模糊等价关系和直觉模糊距离。建立基于直觉模糊等价关系的商空间基本定理。证明由有序的直觉模糊等价关系簇诱导的直觉模糊商空间构成一个完备半序格。     

User profiles and fuzzy logic for web retrieval issues

 We present a study of the role of user profiles using fuzzy logic in web retrieval processes. Flexibility for user interaction and for adaptation in profile construction becomes an important issue. We focus our study on user profiles, including creation, modification, storage, clustering and interpretation. We also consider the role of fuzzy logic and other soft computing techniques to improve user profiles. Extended profiles contain additional information related to the user that can be used to personalize and customize the retrieval process as well as the web site. Web mining processes can be carried out by means of fuzzy clustering of these extended profiles and fuzzy rule construction. Fuzzy inference can be used in order to modify queries and extract knowledge from profiles with marketing purposes within a web framework. An architecture of a portal that could support web mining technology is also presented.     

Computing complete answers to queries in the presence of limited access patterns

In data applications such as information integration, there can be limited access patterns to relations, i.e., binding patterns require values to be specified for certain attributes in order to retrieve data from a relation. As a consequence, we cannot retrieve all tuples from these relations. In this article we study the problem of computing the complete answer to a query, i.e., the answer that could be computed if all the tuples could be retrieved. A query is stable if for any instance of the relations in the query, its complete answer can be computed using the access patterns permitted by the relations. We study the problem of testing stability of various classes of queries, including conjunctive queries, unions of conjunctive queries, and conjunctive queries with arithmetic comparisons. We give algorithms and complexity results for these classes of queries. We show that stability of datalog programs is undecidable, and give a sufficient condition for stability of datalog queries. Finally, we study data-dependent computability of the complete answer to a nonstable query, and propose a decision tree for guiding the process to compute the complete answer.Received: 6 December 2001, Accepted: 25 November 2002, Published online: 3 April 2003Chen Li: This article combines and integrates some content in the technical report at Stanford University [25] and the paper presented in the 8th International Conference on Database Theory (ICDT), London, UK, January, 2001 [28]. In addition to the prior materials, this article contains more results and complete proofs that were not included in the original reports.