Real-world data are often inconsistent. Although a substantial amount of research has been done on measuring inconsistency, this research concentrated on knowledge bases formalized in propositional logic. Recently, inconsistency measures have been introduced for relational databases. However, nowadays, real-world information is always more frequently represented by graph-based structures which offer a more intuitive conceptualization than relational ones. In this paper, we explore inconsistency measures for graph databases with regular path constraints, a class of integrity constraints based on a well-known navigational language for graph data. In this context, we define several inconsistency measures dealing with specific elements contributing to inconsistency in graph databases. We also define some rationality postulates that are desirable properties for an inconsistency measure for graph databases. We analyze the compliance of each measure with each postulate and find various degrees of satisfaction; in fact, one of the measures satisfies all the postulates. Finally, we investigate the data and combined complexity of the calculation of all the measures as well as the complexity of deciding whether a measure is lower than, equal to, or greater than a given threshold. It turns out that for a majority of the measures these problems are tractable, while for the other different levels of intractability are exhibited.

Real-world data are often inconsistent. Although a substantial amount of research has been done on measuring inconsistency, this research concentrated on knowledge bases formalized in propositional logic. Recently, inconsistency measures have been introduced for relational databases. However, nowadays, real-world information is always more frequently represented by graph-based structures which offer a more intuitive conceptualization than relational ones. In this paper, we explore inconsistency measures for graph databases with regular path constraints, a class of integrity constraints based on a well-known navigational language for graph data. In this context, we define several inconsistency measures dealing with specific elements contributing to inconsistency in graph databases. We also define some rationality postulates that are desirable properties for an inconsistency measure for graph databases. We analyze the compliance of each measure with each postulate and find various degrees of satisfaction; in fact, one of the measures satisfies all the postulates. Finally, we investigate the data and combined complexity of the calculation of all the measures as well as the complexity of deciding whether a measure is lower than, equal to, or greater than a given threshold. It turns out that for a majority of the measures these problems are tractable, while for the other different levels of intractability are exhibited.

Handling conflicting information is an important challenge in AI. Measuring inconsistency is an approach that provides ways to quantify the severity of inconsistency and helps understanding the primary sources of conflicts. In particular, a relative inconsistency measure computes, by some criteria, the proportion of the knowledge base that is inconsistent. In this paper we investigate relative inconsistency measures for indefinite databases, which allow for indefinite or partial information which is formally expressed by means of disjunctive tuples. We introduce a postulate-based definition of relative inconsistency measure for indefinite databases with denial constraints, and investigate the compliance of some relative inconsistency measures with rationality postulates for indefinite databases as well as for the special case of definite databases. Finally, we investigate the complexity of the problem of computing the value of the proposed relative inconsistency measures as well as of the problems of deciding whether the inconsistency value is lower than, greater than, or equal to a given threshold for indefinite and definite databases.

Real-world databases are often inconsistent. Although there has been an extensive body of work on handling inconsistency, little work has been done on measuring inconsistency in databases. In this paper, building on work done on measuring inconsistency in propositional knowledge bases, we explore inconsistency measures (IMs) for definite and indefinite databases with denial constraints. We first introduce database IMs that are inspired by well-established methods to quantify inconsistency in propositional knowledge bases, but are tailored to the relational database context where data is generally the reason for inconsistency, not the integrity constraints. Then, we analyze the compliance of the database IMs with rationality postulates for both definite and indefinite databases. Finally, we investigate the complexity of the inconsistency measurement problem as well as of the problems of deciding whether the inconsistency is lower than, greater than, or equal to a given threshold for both the definite and the indefinite cases.

AI systems often need to deal with inconsistencies. One way of getting information about inconsistencies is by measuring the amount of information in the knowledgebase. In the past 20 years numerous inconsistency measures have been proposed. Many of these measures are syntactic measures, that is, they are based in some way on the minimal inconsistent subsets of the knowledgebase. Very little attention has been given to semantic inconsistency measures, that is, ones that are based on the models of the knowledgebase where the notion of a model is generalized to allow an atom to be assigned a truth value that denotes contradiction. In fact, only one nontrivial semantic inconsistency measure, the contension measure, has been in wide use. The purpose of this paper is to define a class of semantic inconsistency measures based on 3-valued logics. First, we show which 3-valued logics are useful for this purpose. Then we show that the class of semantic inconsistency measures can be developed using a graphical framework similar to the way that syntactic inconsistency measures have been studied. We give several examples of semantic inconsistency measures and show how they apply to three useful 3-valued logics. We also investigate the properties of these inconsistency measures and show their computation for several knowledgebases.

We define and investigate new inconsistency measures that are particularly suitable for dealing with inconsistent spatio-temporal information, as they explicitly take into account the spatial and temporal dimensions, as well as the dimension concerning the identifiers of the monitored objects. Specifically, we first define natural measures that look at individual dimensions (time, space, and objects), and then propose measures based on the notion of a repair. We then analyze their behavior w.r.t. common postulates defined for classical propositional knowledge bases, and find that the latter are not suitable for spatio-temporal databases, in that the proposed inconsistency measures do not often satisfy them. In light of this, we argue that also postulates should explicitly take into account the spatial, temporal, and object dimensions, and thus define ``dimension-aware'' counterparts of common postulates, which are indeed often satisfied by the new inconsistency measures. Finally, we study the complexity of the proposed inconsistency measures.

The problem of managing spatio-temporal data arises in many applications, such as location-based services, environmental monitoring, geographic information systems, and many others. Often spatio-temporal data arising from such applications turn out to be inconsistent, i.e., representing an impossible situation in the real world. Though several inconsistency measures have been proposed to quantify in a principled way inconsistency in propositional knowledge bases, little effort has been done so far on inconsistency measures tailored for the spatio-temporal setting. In this paper, we define and investigate new measures that are particularly suitable for dealing with inconsistent spatio-temporal information, because they explicitly take into account the spatial and temporal dimensions, as well as the dimension concerning the identifiers of the monitored objects. Specifically, we first define natural measures that look at individual dimensions (time, space, and objects), and then propose measures based on the notion of a repair. We then analyze their behavior w.r.t. common postulates defined for classical propositional knowledge bases, and find that the latter are not suitable for spatio-temporal databases, in that the proposed inconsistency measures do not often satisfy them. In light of this, we argue that also postulates should explicitly take into account the spatial, temporal, and object dimensions and thus define “dimension-aware” counterparts of common postulates, which are indeed often satisfied by the new inconsistency measures. Finally, we study the complexity of the proposed inconsistency measures.

The aim of measuring inconsistency is to obtain an evaluation of the imperfections in a set of formulas, and this evaluation may then be used to help decide on some course of action (such as rejecting some of the formulas, resolving the inconsistency, seeking better sources of information, etc). A number of proposals have been made to define measures of inconsistency. Each has its rationale. But to date, it is not clear how to delineate the space of options for measures, nor is it clear how we can classify measures systematically. To address these problems, we introduce a general framework for comparing syntactic measures of inconsistency. It is based on the notion of an inconsistency graph for each knowledgebase (a bipartite graph with a set of vertices representing formulas in the knowledgebase, a set of vertices representing minimal inconsistent subsets of the knowledgebase, and edges representing that a formula belongs to a minimal inconsistent subset). We then show that various measures can be computed using the inconsistency graph. Then we introduce abstractions of the inconsistency graph and use them to construct a hierarchy of syntactic inconsistency measures. Furthermore, we extend the inconsistency graph concept with a labeling that extends the hierarchy to include some other types of inconsistency measures.

A number of proposals have been made to define inconsistency measures. Each has its rationale. But to date, it is not clear how to delineate the space of options for measures, nor is it clear how we can classify measures systematically. In this paper, we introduce a general framework for comparing syntactic inconsistency measures. It uses the construction of an inconsistency graph for each knowledgebase. We then introduce abstractions of the inconsistency graph and use the hierarchy of the abstractions to classify a range of inconsistency measures.

There have been a number of proposals for measuring inconsistency in a knowledgebase (i.e. a set of logical formulae). These include measures that consider the minimally inconsistent subsets of the knowledgebase, and measures that consider the paraconsistent models (3 or 4 valued models) of the knowledgebase. In this paper, we present a new approach that considers the amount by which each formula has to be weakened in order for the knowledgebase to be consistent. This approach is based on ideas of knowledge merging by Konienczny and Pino-Perez. We show that this approach gives us measures that are different from existing measures, that have desirable properties, and that can take the significance of inconsistencies into account. The latter is useful when we want to differentiate between inconsistencies that have minor significance from inconsistencies that have major significance. We also show how our measures are potentially useful in applications such as evaluating violations of integrity constraints in databases and for deciding how to act on inconsistency.

Scrum is a cyclical project management technique whereby members of a development team work together to define product development strategies in pursuit of a common objective in an adaptable and incremental manner. We have found that Scrum is a promising approach for exposing students to project management of undergraduate engineering projects. But, the technique is not used often in undergraduate education, and it is virtually unknown outside of software engineering circles. We are experimenting with using Scrum in projects across several years of undergraduate engineering education. Our goal is to gradually expose students to project management in order to make their project experiences and learning more efficient and effective. We report on successful initial implementations in freshman courses and senior capstone design courses. Obstacles include expanding practice across all four years, accommodating a diverse student population, and overcoming a lack of experience in assessing Scrum project management.

We represent knowledge as integrity constraints in a formalization of probabilistic spatio-temporal knowledge bases. We start by defining the syntax and semantics of a formalization called PST knowledge bases. This definition generalizes an earlier version, called SPOT, which is a declarative framework for the representation and processing of probabilistic spatio-temporal data where probability is represented as an interval because the exact value is unknown. We augment the previous definition by adding a type of non-atomic formula that expresses integrity constraints. The result is a highly expressive formalism for knowledge representation dealing with probabilistic spatio-temporal data. We obtain complexity results both for checking the consistency of PST knowledge bases and for answering queries in PST knowledge bases, and also specify tractable cases. All the domains in the PST framework are finite, but we extend our results also to arbitrarily large finite domains.

Spatiotemporal databases can be used to efficiently store and retrieve information about objects moving in space and time. Probabilities are added to model the case where the locations are not known with certainty. A few years ago a new formalism was introduced to represent such information in the form of atomic formulas, each of which represents the probability (in the form of an interval because even the probabilities are not known precisely) that a particular object is in a particular location at a particular time. We extend this formalism to obtain several different probabilistic logics by adding logical operators. Furthermore, we axiomatize these logics, provide corresponding semantics, prove that the axiomatizations are sound and complete, and discuss decidability issues. While we relate these logics to previous axiomatizations of probabilistic logics, this article is self-contained: no prior knowledge of probabilistic logics is assumed.

Most real-world databases have at least some missing data. Today, users of such databases are “on their own” in terms of how they manage this incompleteness. In this paper, we propose the general concept of partial information policy (PIP) operator to handle incompleteness in relational databases. PIP operators build upon preference frameworks for incomplete information, but accommodate different types of incomplete data (e.g., a value exists but is not known; a value does not exist; a value may or may not exist). Different users in the real world have different ways in which they want to handle incompleteness-PIP operators allow them to specify a policy that matches their attitude to risk and their knowledge of the application and how the data was collected. We propose index structures for efficiently evaluating PIP operators and experimentally assess their effectiveness on a real-world airline data set. We also study how relational algebra operators and PIP operators interact with one another.

STUN is an extension of social networks in which the edges are characterized by spatio-temporal annotations, as well as uncertainty allowing us to express not only relationships between vertices, but when and where these relationships were true, and how certain we are that the relationships hold. We propose a STUN query language that consists of sub graphs with spatio-temporal constraints and uncertainty requirements. We then develop an index structure to store STUN graphs, together with an algorithm to answer such queries. We describe experiments with a real-world YouTube social network data set and show that our algorithm performs well on graphs with over a million edges.

There is interest in artificial intelligence for principled techniques to analyze inconsistent information. This stems from the recognition that the dichotomy between consistent and inconsistent sets of formulae that comes from classical logics is not sufficient for describing inconsistent information. We review some existing proposals and make new proposals for measures of inconsistency and measures of information, and then prove that they are all pairwise incompatible. This shows that the notion of inconsistency is a multi-dimensional concept where different measures provide different insights. We then explore relationships between measures of inconsistency and measures of information in terms of the trade-offs they identify when using them to guide resolution of inconsistency.

Intentions have been widely studied in AI, both in the context of decision-making within individual agents and in multi-agent systems. Work on intentions in multi-agent systems has focused on joint intention models, which characterise the mental state of agents with a shared goal engaged in teamwork. In the absence of shared goals, however, intentions play another crucial role in multi-agent activity: they provide a basis around which agents can mutually coordinate activities. Models based on shared goals do not attempt to account for or explain this role of intentions. In this paper, we present a formal model of multi-agent systems in which belief-desire-intention agents choose their intentions taking into account the intentions of others. To understand rational mental states in such a setting, we formally define and investigate notions of multi-agent intention equilibrium, which are related to equilibrium concepts in game theory.

Spatial probabilistic temporal (SPOT) databases are a paradigm for reasoning with probabilistic statements about where a vehicle may be now or in the future. They express statements of the form "Object O is in spatial region R at some time t with some probability in the interval [L,U]." Past work on SPOT databases has developed selection operators based on selecting SPOT atoms that are entailed by the SPOT database-we call this "cautious" selection. In this paper, we study several problems. First, we note that the runtime of consistency checking and cautious selection algorithms in past work is influenced greatly by the granularity of the underlying Cartesian space. In this paper, we first introduce the notion of "optimistic" selection, where we are interested in returning all SPOT atoms in a database that are consistent with respect to a query, rather than having an entailment relationship. We then develop an approach to scaling SPOT databases that has three main contributions: 1) We develop methods to eliminate variables from the linear programs used in past work, thus greatly reducing the size of the linear programs used-the resulting advances apply to consistency checking, optimistic selection, and cautious selection. 2) We develop a host of theorems to show how we can prune the search space when we are interested in optimistic selection. 3) We use the above contributions to build an efficient index to execute optimistic selection queries over SPOT databases. Our approach is superior to past work in two major respects: First, it makes fewer assumptions than all past works on this topic except that in. Second, our experiments, which are based on real-world data about ship movements, show that our algorithms are much more efficient than those in.

There are numerous applications where there: is uncertainty over space and time. Examples of such uncertainty arise in vehicle tracking systems where we are not always sure where a vehicle is now (or may be in the future), and cell and satellite phone applications where we are not sure exactly where a phone may be, and so on. In this paper, we propose the concept of a Spatial Probabilistic Temporal (SPOT) database that contains statements of the form "Object O is in spatial region R at some time / with some probability in the interval [L, U]." We define the syntax and a declarative semantics for SPOT databases based on a mix of logic and linear programming, as well as query algebra. We show alternative implementations of some of these query algebra operators when the SPOT database has a disjoint/less property. Though the declarative semantics of SPOT databases is rooted in linear programming, we have found very efficient algorithms that do not use linear programming methods. We report on experiments we have conducted that show that the system scales to large numbers of SPOT atoms, as well as to fairly fine temporal and spatial granularity.

Though extensions to the relational data model have been proposed in order to handle probabilistic information, there has been very little work to date on handling aggregate operators in such databases. In this article, we present a very general notion of an aggregate operator and show how classical aggregation operators (such as COUNT, SUM, etc.) as well as statistical operators (such as percentiles, variance, etc.) are special cases of this general definition. We devise a formal linear programming based semantics for computing aggregates over probabilistic DBMSs, develop algorithms that satisfy this semantics, analyze their complexity, and introduce several families of approximation algorithms that run in polynomial time. We implemented all of these algorithms and tested them on a large set of data to help determine when each one is preferable.

An important aspect of data integration involves answering queries using various resources rather than by accessing database relations. The process of transforming a query from the database relations to the resources is often referred to as query folding or answering queries using views, where the views are the resources. We present a uniform approach that includes as special cases much of the previous work on this subject. Our approach is logic-based using resolution. We deal with integrity constraints, negation, and recursion also within this framework.

We present a technique for transferring query optimization techniques, developed for relational databases, into object databases. We demonstrate this technique for ODMG database schemas defined in ODL and object queries expressed in OQL. The object schema is represented using a logical representation (Datalog). Semantic knowledge about the object data model, e.g., class hierarchy information, relationship between objects, etc., as well as semantic knowledge about a particular schema and application domain are expressed as integrity constraints. An OQL object query is represented as a logic query and query optimization is performed in the Datalog representation. We obtain equivalent (optimized) logic queries, and subsequently obtain equivalent (optimized) OQL queries for each equivalent logic query. We present one optimization technique for semantic query optimization (SQO) based on the residue technique of U. Charavarthy et al. (1990; 1986; 1988). We show that our technique generalizes previous research on SQO for object databases. We handle a large class of OQL queries, including queries with constructors and methods. We demonstrate how SQO can be used to eliminate queries which contain contradictions and simplify queries, e.g., by eliminating joins, or by reducing the access scope for evaluating a query to some specific subclass(es). We also demonstrate how the definition of a method or integrity constraints describing the method, can be used in optimizing a query with a method.

Presents a technique for semantic query optimization (SQO) for object databases. We use the ODMG-93 (Object Data Management Group) standard ODL (Object Database Language) and OQL (Object Query Language) languages. The ODL object schema and the OQL object query are translated into a DATALOG representation. Semantic knowledge about the object model and the particular application is expressed as integrity constraints. This is an extension of the ODMG-93 standard. SQO is performed in the DATALOG representation, and an equivalent logic query and (subsequently) an equivalent OQL object query are obtained. SQO is based on the residue technique of Chakravarthy et al. (1990). We show that our technique generalizes previous research on SQO for object databases. It can be applied to queries with structure constructors and method application. It utilizes integrity constraints about keys, methods and knowledge of access support relations, to produce equivalent queries, which may have more efficient evaluation plans.

Databases and knowledge bases could be inconsistent in many ways. For example, during the construction of an expert system, we may consult many different experts. Each expert may provide us with a group of rules and facts which are self-consistent. However, when we coalesce the facts and rules provided by these different experts, inconsistency may arise. Alternatively, knowledge bases may be inconsistent due to the presence of some erroneous information. Thus, a framework for reasoning about knowledge bases that contain inconsistent information is necessary. However, existing frameworks for reasoning with inconsistency do not support reasoning by cases and reasoning with the law of excluded middle ("everything is either true or false"). In this paper, we show how reasoning with cases, and reasoning with the law of excluded middle may be captured. We develop a declarative and operational semantics for knowledge bases that are possibly inconsistent. We compare and contrast our work with work on explicit and non-monotonic modes of negation in logic programs and suggest under what circumstances one framework may be preferred over another.>

The purpose of semantic query optimization is to use semantic knowledge (e.g., integrity constraints) for transforming a query into a form that may be answered more efficiently than the original version. In several previous papers we described and proved the correctness of a method for semantic query optimization in deductive databases couched in first-order logic. This paper consolidates the major results of these papers emphasizing the techniques and their applicability for optimizing relational queries. Additionally, we show how this method subsumes and generalizes earlier work on semantic query optimization. We also indicate how semantic query optimization techniques can be extended to databases that support recursion and integrity constraints that contain disjunction, negation, and recursion.

A common framework is provided for the investigation of various types of integnty constraints for relaaonal databases.The family of generahzed dependency constraints is introduced.It is shown that this famdy contains as members most of the classes of dependencies studied m the database literature as well as some other classes of database constraints.A charactenzaaon, together with an algorithm, Is provided for determining whether or not a universal statement of first-order logic is a logical consequence of a class in the family.Thts result is shown to be a generalization of former results concerning unphcatmns of dependencies and yields a connection between the resolution method and the chase method as well as a method for constructing Armstrong databases In addition, an alternative version of the theorem ~s described, the preservation of the theorem is discussed m the context of lossless join decomposluons, and the extension of the results to embedded dependencies is elaborated.