A possible world semantics for disjunctive databases

The fundamental problem that arises when a ground atom in a disjunctive database is assumed false is discussed. There are basically two different approaches for inferring negative information for disjunctive databases: J. Minker's (1982) generalized closed world assumption (GCWA) and K.A. Ross and R.W. Topor's (1988) disjunctive database rule (DDR). It is argued that neither approach is satisfactory. A database semantics called PWS is proposed. It is shown that for propositional databases with no negative clauses, the problem of determining if a negative ground literal is inferred under the GCWA is co-NP-hard, while the same problem can be solved efficiently under the DDR and PWS. However, in the general case, the problem becomes co-NP-complete for the DDR and PWS. Relationships among GCWA, DDR, and PWS are highlighted. In general, disjunctive clauses are interpreted inclusively under the DDR and unpredictably under the GCWA     

An integrated information fusion approach based on the theory of evidence and group decision-making

Dempster–Shafer theory of evidence has been employed as a major method for reasoning with multiple evidence. The Dempster’s rule of combination is however incapable of managing highly conflicting evidence coming from different information sources at the normalization step. Extending current rules, we incorporate the ideas of group decision-making into the theory of evidence and propose an integrated approach to automatically identify and discount unreliable evidence. An adaptive robust combination rule that incorporates the information contained in the consistent focal elements is then constructed to combine such evidence. This rule adjusts the weights of the conjunctive and disjunctive rules according to a function of the consistency of focal elements. The theoretical arguments are supported by numerical experiments. Compared to existing combination rules, the proposed approach can obtain a reasonable and reliable decision, as well as the level of uncertainty about it.     

View updates in stratified disjunctive databases

The view update problem is considered in the context of deductive databases where the update of an intensional predicate is accomplished by modifying appropriately the underlying relations in the extensional database. Two classes of disjunctive databases are considered. The first class contains those disjunctive databases which allow only definite rules in the intensional database and disjunctive facts in the extensional database. The second class contains stratified disjunctive databases so that in addition to the first class, negation is allowed in the bodies of the rules, but the database must be stratified. Algorithms are given both for the insertion of an intensional predicate into and the deletion of an intensional predicate from the database. The algorithms use SLD resolution and the concept of minimal models of the extensional database. The algorithms are proved to be correct and best according to the criterion of causing minimal change to the database, where we give first priority to minimizing deletions.Research supported by the National Science Foundation under grant numbers IRI-8916059, IRI-8921591, IRI-9200898, and IRI-9210220.     

Robust combination rules for evidence theory

Dempster’s rule of combination in evidence theory is a powerful tool for reasoning under uncertainty. Since Zadeh highlighted the counter-intuitive behaviour of Dempster’s rule, a plethora of alternative combination rules have been proposed. In this paper, we propose a general formulation for combination rules in evidence theory as a weighted sum of the conjunctive and disjunctive rules. Moreover, with the aim of automatically accounting for the reliability of sources of information, we propose a class of robust combination rules (RCR) in which the weights are a function of the conflict between two pieces of information. The interpretation given to the weight of conflict between two BPAs is an indicator of the relative reliability of the sources: if the conflict is low, then both sources are reliable, and if the conflict is high, then at least one source is unreliable. We show some interesting properties satisfied by the RCRs, such as positive belief reinforcement or the neutral impact of vacuous belief, and establish links with other classes of rules. The behaviour of the RCRs over non-exhaustive frames of discernment is also studied, as the RCRs implicitly perform a kind of automatic deconditioning through the simple use of the disjunctive operator. We focus our study on two special cases: (1) RCR-S, a rule with symmetric coefficients that is proved to be unique and (2) RCR-L, a rule with asymmetric coefficients based on a logarithmic function. Their behaviours are then compared to some classical combination rules proposed thus far in the literature, on a few examples, and on Monte Carlo simulations.     

Model theoretic approach to view updates in deductive databases

The view update problem for deductive databases has been defined as the problem of accomplishing the update of an intensional predicate by modifying appropriately the extensional database. A previous paper by Grant, Horty, Lobo, and Minker developed algorithms for the insertion and the deletion of an intensional predicate in certain important classes of stratified disjunctive deductive databases. This paper introduces a model theoretic approach which encompasses a wide class of Herbrand semantics, including the perfect model and stable model semantics, for disjunctive databases including negation. This generalizes the earlier results: now the intensional database may contain disjunctive and denial rules, and the database may be required to satisfy integrity constraints. As in the previous paper, the algorithms are proved to be correct and best according to the criterion of causing minimal change to the database, where the first priority is to minimize deletions.     

Answering Queries Addressed to Several Databases According to a Majority Merging Approach

The general context of this work is the problem of merging data provided by several sources which can be contradictory. Focusing on the case when the information sources do not contain any disjunction, this paper first defines a propositional modal logic for reasoning with data obtained by merging several information sources according to a majority approach. Then it defines a theorem prover to automatically deduce these merged data. Finally, it shows how to use this prover to implement a query evaluator which answers queries addressed to several databases. This evaluator is such that the answer to a query is the one that could be computed by a classical evaluator if the query was addressed to the merged databases. The databases we consider are made of an extensional part, i.e. a set of positive or negative ground literals, and an intensional part i.e. a set of first order function-free clauses. A restriction is imposed to these databases in order to avoid disjunctive data.     

基于条件冲突分析的主动规则集汇流性判定方法

主动规则使数据库具备自反应能力,在数据库、知识库和无线传感器网络等领域得到了广泛应用。汇流性分析是保持数据一致性的重要手段,但有效判定汇流性仍是一个难题。现有的方法基于规则可交换性进行判定,没有考虑规则之间是否存在条件冲突而导致它们不可能同时出现在同一个执行序列中;同时基于触发关系的集合分析没有考虑在规则触发序列中的先后时序性。为此,提出了规则的触发序列概念,分析了单个触发序列上的条件冲突和一对无序规则所在的两条触发序列之间的条件冲突,从而提出了更有效的汇流性先决条件及其判定定理,同时给出了新的判定算法的完整描述及其可终止性、正确性证明和复杂度分析。     

Default logic generalized and simplified

We study a generalization of default logic obtained by extending its logical, monotonic basis to disjunctive (multiple-conclusion) rules. Special attention will be paid to the representation opportunities created by such rules, in particular to the use of default justifications in the heads of the rules. On the other hand, it will be shown that even the generalized default logic can be simplified to a formal system that involves only monotonic inference rules and unconditional (‘supernormal’) default assumptions.     

Set-valued ordered information systems

Set-valued ordered information systems can be classified into two categories: disjunctive and conjunctive systems. Through introducing two new dominance relations to set-valued information systems, we first introduce the conjunctive/disjunctive set-valued ordered information systems, and develop an approach to queuing problems for objects in presence of multiple attributes and criteria. Then, we present a dominance-based rough set approach for these two types of set-valued ordered information systems, which is mainly based on substitution of the indiscernibility relation by a dominance relation. Through the lower/upper approximation of a decision, some certain/possible decision rules from a so-called set-valued ordered decision table can be extracted. Finally, we present attribute reduction (also called criteria reduction in ordered information systems) approaches to these two types of ordered information systems and ordered decision tables, which can be used to simplify a set-valued ordered information system and find decision rules directly from a set-valued ordered decision table. These criteria reduction approaches can eliminate those criteria that are not essential from the viewpoint of the ordering of objects or decision rules.     

Analyzing the combination of conflicting belief functions

We consider uncertain data which uncertainty is represented by belief functions and that must be combined. The result of the combination of the belief functions can be partially conflictual. Initially Shafer proposed Dempster’s rule of combination where the conflict is reallocated proportionally among the other masses. Then Zadeh presented an example where Dempster’s rule of combination produces unsatisfactory results. Several solutions were proposed: the TBM solution where masses are not renormalized and conflict is stored in the mass given to the empty set, Yager’s solution where the conflict is transferred to the universe and Dubois and Prade’s solution where the masses resulting from pairs of conflictual focal elements are transferred to the union of these subsets. Many other suggestions have then been made, creating a ‘jungle’ of combination rules. We discuss the nature of the combinations (conjunctive versus disjunctive, revision versus updating, static versus dynamic data fusion), argue about the need for a normalization, examine the possible origins of the conflicts, determine if a combination is justified and analyze many of the proposed solutions.