On similarity relations in fuzzy relational databases

A characterization of a certain type of similarity relation is presented. This characterization is conceptually very easy and may be used to provide easier proofs of already established theorems.We use this characterization to show that if only a few similarity values of a similarity relation are known, then the others may be computed. This results in efficient storage of similarity relations associated with fuzzy relational databases.In addition, we use our characterization to show that there is only one type of similarity relation that provides a non-redundant decomposition of data in a fuzzy relational data base.     

A fuzzy representation of data for relational databases

A structure for representing inexact information in the form of a relational database is presented. The structure differs from ordinary relational databases in two important respects: Components of tuples need not be single values and a similarity relation is required for each domain set of the database. Two critical properties possessed by ordinary relational databases are proven to exist in the fuzzy relational structure. These properties are (1) no two tuples have identical interpretations, and (2) each relational operation has a unique result.     

Stream-based inconsistency measurement

Inconsistency measures have been proposed to assess the severity of inconsistencies in knowledge bases of classical logic in a quantitative way. In general, computing the value of inconsistency is a computationally hard task as it is based on the satisfiability problem which is itself NP-complete. In this work, we address the problem of measuring inconsistency in knowledge bases that are accessed in a stream of propositional formulæ. That is, the formulæ of a knowledge base cannot be accessed directly but only once through processing of the stream. This work is a first step towards practicable inconsistency measurement for applications such as Linked Open Data, where huge amounts of information is distributed across the web and a direct assessment of the quality or inconsistency of this information is infeasible due to its size. Here we discuss the problem of stream-based inconsistency measurement on classical logic, in order to make use of existing measures for classical logic. However, it turns out that inconsistency measures defined on the notion of minimal inconsistent subsets are usually not apt to be used in the streaming scenario. In order to address this issue, we adapt measures defined on paraconsistent logics and also present a novel inconsistency measure based on the notion of a hitting set. We conduct an extensive empirical analysis on the behavior of these different inconsistency measures in the streaming scenario, in terms of runtime, accuracy, and scalability. We conclude that for two of these measures, the stream-based variant of the new inconsistency measure and the stream-based variant of the contension inconsistency measure, large-scale inconsistency measurement in streaming scenarios is feasible.     

Compound approximation spaces for relational data

Rough set theory provides a powerful tool for dealing with uncertainty in data. Application of variety of rough set models to mining data stored in a single table has been widely studied. However, analysis of data stored in a relational structure using rough sets is still an extensive research area. This paper proposes compound approximation spaces and their constrained versions that are intended for handling uncertainty in relational data. The proposed spaces are expansions of tolerance approximation ones to a relational case. Compared with compound approximation spaces, the constrained version enables to derive new knowledge from relational data. The proposed approach can improve mining relational data that is uncertain, incomplete, or inconsistent.     

Approaches to measuring inconsistency for stratified knowledge bases

A number of proposals have been proposed for measuring inconsistency for knowledge bases. However, it is rarely investigated how to incorporate preference information into inconsistency measures. This paper presents two approaches to measuring inconsistency for stratified knowledge bases. The first approach, termed the multi-section inconsistency measure (MSIM for short), provides a framework for characterizing the inconsistency at each stratum of a stratified knowledge base. Two instances of MSIM are defined: the naive MSIM and the stratum-centric MSIM. The second approach, termed the preference-based approach, aims to articulate the inconsistency in a stratified knowledge base from a global perspective. This approach allows us to define measures by taking into account the number of formulas involved in inconsistencies as well as the preference levels of these formulas. A set of desirable properties are introduced for inconsistency measures of stratified knowledge bases and studied with respect to the inconsistency measures introduced in the paper. Computational complexity results for these measures are presented. In addition, a simple but explanatory example is given to illustrate the application of the proposed approaches to requirements engineering.     

Responsibility for inconsistency

It is desirable to identify the degree of responsibility of each part of a knowledge base for the inconsistency of that base to make some necessary trade-off decisions on restoring the consistency of that base. In this paper, we propose a measurement for the degree of responsibility of each formula in a knowledge base for the inconsistency of that base. This measurement is given in terms of minimal inconsistent subsets of a knowledge base. Moreover, it can be well explained in the context of causality and responsibility presented by Chockler and Halpern [1].     

Measuring and repairing inconsistency in probabilistic knowledge bases

In this paper we present a family of measures aimed at determining the amount of inconsistency in probabilistic knowledge bases. Our approach to measuring inconsistency is graded in the sense that we consider minimal adjustments in the degrees of certainty (i.e., probabilities in this paper) of the statements necessary to make the knowledge base consistent. The computation of the family of measures we present here, in as much as it yields an adjustment in the probability of each statement that restores consistency, provides the modeler with possible repairs of the knowledge base. The case example that motivates our work and on which we test our approach is the knowledge base of CADIAG-2, a well-known medical expert system.     

Computational approaches to finding and measuring inconsistency in arbitrary knowledge bases

There is extensive theoretical work on measures of inconsistency for arbitrary formulae in knowledge bases. Many of these are defined in terms of the set of minimal inconsistent subsets (MISes) of the base. However, few have been implemented or experimentally evaluated to support their viability, since computing all MISes is intractable in the worst case. Fortunately, recent work on a related problem of minimal unsatisfiable sets of clauses (MUSes) offers a viable solution in many cases. In this paper, we begin by drawing connections between MISes and MUSes through algorithms based on a MUS generalization approach and a new optimized MUS transformation approach to finding MISes. We implement these algorithms, along with a selection of existing measures for flat and stratified knowledge bases, in a tool called mimus. We then carry out an extensive experimental evaluation of mimus using randomly generated arbitrary knowledge bases. We conclude that these measures are viable for many large and complex random instances. Moreover, they represent a practical and intuitive tool for inconsistency handling.     

Representation of ideals of relational structures

The age of a relational structure A of signature μ is the set age(A) of its finite induced substructures, considered up to isomorphism. This is an ideal in the poset Ω_μ consisting of finite structures of signature μ and ordered by embeddability. We shall show that if the structures have infinitely many relations and if, among those, infinitely many are at least binary then there are ideals which do not come from an age. We provide many examples. We particularly look at metric spaces and offer several problems. We also answer a question due to Cusin and Pabion [R. Cusin, J.F. Pabion, Une généralisation de l’âge des relations, C. R. Acad. Sci. Paris, Sér. A-B 270 (1970) A17-A20]: there is an ideal I of isomorphism types of at most countable structures whose signature consists of a single ternary relation symbol such that I does not come from the set of isomorphism types of substructures of A induced on the members of an ideal I of sets.     

Inferring null join dependencies in relational databases

The inference problem for data dependencies in relational databases is the problem of deciding whether a set of data dependencies logically implies another data dependency. For join dependencies (JDs), the inference problem has been extensively studied by utilising the well-known chase procedure. We generalise JDs to null join dependencies (NJDs) that hold in relations which may contain null values. In our model for incomplete information we allow only a single unmarked null value denoted bynull. This allows us to solve the inference problem for NJDs by extending the chase procedure to the or-chase procedure. In order to define the or-chase procedure we generalise relations with nulls to or-relations which contain a limited form of disjunctive information. The main result of the paper shows that the inference problem for NJDs, including embedded NJDs (which are a special case of NJDs), is decidable; this is realised via the or-chase procedure.     

Enhancing the generality of fuzzy relational models for control

A promising area of research in fuzzy control is the model-based fuzzy controller. At the heart of this approach is a fuzzy relational model of the process to be controlled. Since this model is identified directly from process input-output data it is likely that ‘holes’ will be present in the identified relational model. These holes are real problems when the model is incorporated into a model-based controller since the model will be unable to make any predictions whatsoever if the system drifts into an unknown region. The present work deals with the completeness of the fuzzy relational model which forms the core of the controller. This work proposes a scheme of post-processing to ‘fiil in’ the fuzzy relational model once it has been built and thereby improve its applicability for on-line control. A comparative study of the post-processed model and conventional relational model is presented for Box-Jenkins data identification system and a real-time, highly non-linear application of pH control identification.     

Fuzzy relational clustering around medoids: A unified view

Medoid-based fuzzy clustering generates clusters of objects based on relational data, which records pairwise similarities or dissimilarities among objects. Compared with single-medoid based approaches, our recently proposed fuzzy clustering with multiple-weighted medoids has shown superior performance in clustering via experimental study. In this paper, we present a new version of fuzzy relational clustering in this family called fuzzy clustering with multi-medoids (FMMdd). Based on the new objective function of FMMdd, update equations can be derived more conveniently. Moreover, a unified view of FMMdd and two existing fuzzy relational approaches fuzzy c-medoids (FCMdd) and assignment-prototype (A-P) can be established, which allows us to conduct further analytical study to investigate the effectiveness and feasibility of the proposed approach as well as the limitations of existing ones. The robustness of FMMdd is also investigated. Our theoretical and numerical studies show that the proposed approach produces good quality of clusters with rich cluster-based information and it is less sensitive to noise.     

Eigenvector method,consistency test and inconsistency repairing for an incomplete fuzzy preference relation

In this paper, we extend the eigenvector method (EM) to priority for an incomplete fuzzy preference relation. We give a reasonable definition of multiplicative consistency for an incomplete fuzzy preference relation. We also give an approach to judge whether an incomplete fuzzy relation is acceptable or not. We develop the acceptable consistency ratio for an incomplete multiplicative fuzzy preference relation, which is simple and similar to Saaty’s consistency ratio (CR) for the multiplicative preference relation. If the incomplete fuzzy preference relation is not of acceptable consistency, we define a criterion to find the unusual and false element (UFE) in the preference relation, and present an algorithm to repair an inconsistent fuzzy preference relation until its consistency is satisfied with the consistency ratio. As a result, our improvement method cannot only satisfy the consistency requirement, but also preserve the initial preference information as much as possible. Finally, an example is illustrated to show that our method is simple, efficiency, and can be performed on computer easily.     

Towards optimal workload-aware XML to relational schema mapping

Storing XML documents in relational databases has drawn much attention in recent years because it can leverage existing investments in relational database technologies. Different algorithms have been proposed to map XML DTD/Schema to relational schema in order to store XML data in relational databases. However, most work defines mapping rules based on heuristics without considering application characteristics, hence fails to produce efficient relational schema for various applications. In this paper, we propose a workload-aware approach to generate relational schema from XML data and user specified workload. Our approach adopts the genetic algorithm to find optimal mappings. An elegant encoding method and related operations are proposed to manipulate mappings using bit strings. Various techniques for optimization can be applied to the XML to relational mapping problem based on this representation. We implemented the proposed algorithm and our experiment results showed that our algorithm was more robust and produced better mappings than existing work.     

Explanation of exceptional values in multi-dimensional business databases

In this paper, we describe an extension of the OnLine Analytical Processing (OLAP) framework with causal explanation, offering the possibility to automatically generate explanations for exceptional cell values. This functionality can be built into conventional OLAP databases using a generic explanation formalism, which supports the work of managers in diagnostic processes. The central goal is the identification of specific knowledge structures and reasoning methods required to construct computerized explanations from multi-dimensional data and business models. The methodology was tested on a case study involving the comparison of financial figures of a firm’s business units. The findings suggest improved decision-making by managers because the current tedious and error-prone manual analysis process is enhanced by automated problem identification and explanation generation. It is also noted that this novel methodology has general utility for decision-support systems, for example, for automated diagnosis in the financial and accountancy domain.     

Estimating suppressed data in regional economic databases: A goal-programming approach

To avoid disclosure of individual establishment information, data records may have to be suppressed in regional economic databases, with values represented by flags. This paper investigates this suppression process and presents a goal-programming optimization approach to estimate these flagged data, using the 2000 County Business Patterns (CBP) database as a case study. The approach minimizes the sum of weighted deviations between the estimates and target values, subject to constraints related to county and sector total employment, as well as to flag and establishment size intervals. The model is tested using Ohio and Arizona data, for both sources of inconsistencies and parameter selection. A decision-theoretic analysis of the test results points to specific strategies that yield the best estimates of the suppressed data.     

A relational perspective of attribute reduction in rough set-based data analysis

Attribute reduction is very important in rough set-based data analysis (RSDA) because it can be used to simplify the induced decision rules without reducing the classification accuracy. The notion of reduct plays a key role in rough set-based attribute reduction. In rough set theory, a reduct is generally defined as a minimal subset of attributes that can classify the same domain of objects as unambiguously as the original set of attributes. Nevertheless, from a relational perspective, RSDA relies on a kind of dependency principle. That is, the relationship between the class labels of a pair of objects depends on component-wise comparison of their condition attributes. The larger the number of condition attributes compared, the greater the probability that the dependency will hold. Thus, elimination of condition attributes may cause more object pairs to violate the dependency principle. Based on this observation, a reduct can be defined alternatively as a minimal subset of attributes that does not increase the number of objects violating the dependency principle. While the alternative definition coincides with the original one in ordinary RSDA, it is more easily generalized to cases of fuzzy RSDA and relational data analysis.     

Threshold phenomena in the transient behaviour of Markovian models of communication networks and databases

This paper accompanies a talk given at the Workshop on Mathematical Methods in Queueing Networks held at the Mathematical Sciences Institute at Cornell University in August 1988. In earlier work we had exhibited a threshold phenomenon in the transient behaviour of a closed network of ./M/1 nodes: When there areN customers circulating, and the initial state isx, letd _x ^N (t) denote the total variation distance between the distribution at timet and the stationary distribution. Let d^N(t) = max _x d _x ^N (t). We explicitly founda _N proportional toN such thatd ^N(ta_N)1 forevery t<1, andd ^N(ta_N)0 forevery t>1. Thus it appears that the network has not yet converged to stationarity uptoa _N , but has converged to stationarity aftera _N , soa _N can be naturally interpreted as the settling time of the network. Here we briefly deal with some other similar models — closed networks of ./M/m nodes, a well studied model for circuit switched networks, and a model of Mitra for studying concurrency control in databases. Similar threshold phenomena are established in the transient behaviour of these models.Research supported by the National Science Foundation, Grant No. NCR 8710840.     

Sets and indices in linear programming modelling and their integration with relational data models

LP models are usually constructed using index sets and data tables which are closely related to the attributes and relations of relational database (RDB) systems. We extend the syntax of MPL, an existing LP modelling language, in order to connect it to a given RDB system. This approach reuses existing modelling and database software, provides a rich modelling environment and achieves model and data independence. This integrated software enables Mathematical Programming to be widely used as a decision support tool by unlocking the data residing in corporate databases.