Probabilistic query answering over inconsistent databases

This paper presents a framework for querying inconsistent databases in the presence of functional dependencies. Most of the works dealing with the problem of extracting reliable information from inconsistent databases are based on the notion of repair, a minimal set of tuple insertions and deletions which leads the database to a consistent state (called repaired database), and the notion of consistent query answer, a query answer that can be obtained from every repaired database. In this work, both the notion of repair and query answer differ from the original ones. In the presence of functional dependencies, tuple deletions are the only operations that are performed in order to restore the consistency of an inconsistent database. However, deleting a tuple to remove an integrity violation potentially eliminates useful information in that tuple. In order to cope with this problem, we adopt a notion of repair, based on tuple updates, which allows us to better preserve information in the source database. A drawback of the notion of consistent query answer is that it does not allow us to discriminate among non-consistent answers, namely answers which can be obtained from a non-empty proper subset of the repaired databases. To obtain more informative query answers, we propose the notion of probabilistic query answer, that is query answers are tuples associated with probabilities. This new semantics of query answering over inconsistent databases allows us to give a measure of uncertainty to query answers. We show that the problem of computing probabilistic query answers is FP ^#P -complete. We also propose a technique for computing probabilistic answers to arbitrary relational algebra queries.     

An incremental clustering scheme for data de-duplication

We propose an incremental technique for discovering duplicates in large databases of textual sequences, i.e., syntactically different tuples, that refer to the same real-world entity. The problem is approached from a clustering perspective: given a set of tuples, the objective is to partition them into groups of duplicate tuples. Each newly arrived tuple is assigned to an appropriate cluster via nearest-neighbor classification. This is achieved by means of a suitable hash-based index, that maps any tuple to a set of indexing keys and assigns tuples with high syntactic similarity to the same buckets. Hence, the neighbors of a query tuple can be efficiently identified by simply retrieving those tuples that appear in the same buckets associated to the query tuple itself, without completely scanning the original database. Two alternative schemes for computing indexing keys are discussed and compared. An extensive experimental evaluation on both synthetic and real data shows the effectiveness of our approach.     

Processing negation and disjunction in logic programs through integrity constraints

Integrity constraints were initially defined to verify the correctness of the data that is stored in a database. They were used to restrict the modifications that can be applied to a database. However, there are many other applications in which integrity constraints can play an important role. For example, the semantic query optimization method developed by Chakravarthy, Grant, and Minker for definite deductive databases uses integrity constraints during query processing to prevent the exploration of search space that is bound to fail. In this paper, we generalize the semantic query optimization method to apply to negated atoms. The generalized method is referred to assemantic compilation. This exploration has led to two significant results. First, semantic compilation provides an alternative search space for negative query literals. The alternative search space can find answers in cases for which negation-as-finite-failure and constructive negation cannot. Second, we show how semantic compilation can be used to transform a disjunctive database with or without functions and denial constraints without negation into a new disjunctive database that complies with the integrity constraints.     

Partial Evaluation of Views

Many database applications and environments, such as mediation over heterogeneous database sources and data warehousing for decision support, lead to complex queries. Queries are often nested, defined over previously defined views, and may involve unions. There are good reasons why one might want to remove pieces (sub-queries or sub-views) from such queries: some sub-views of a query may be effectively cached from previous queries, or may be materialized views; some may be known to evaluate empty, by reasoning over the integrity constraints; and some may match protected queries, which for security cannot be evaluated for all users.In this paper, we present a new evaluation strategy with respect to queries defined over views, which we call tuple-tagging, that allows for an efficient removal of sub-views from the query. Other approaches to this are to rewrite the query so the sub-views to be removed are effectively gone, then to evaluate the rewritten query. With the tuple tagging evaluation, no rewrite of the original query is necessary.We describe formally a discounted query (a query with sub-views marked that are to be considered as removed), present the tuple tagging algorithm for evaluating discounted queries, provide an analysis of the algorithm's performance, and present some experimental results. These results strongly support the tuple-tagging algorithm both as an efficient means to effectively remove sub-views from a view query during evaluation, and as a viable optimization strategy for certain applications. The experiments also suggest that rewrite techniques for this may perform worse than the evaluation of the original query, and much worse than the tuple tagging approach.     

Automatic knowledge acquisition and maintenance for semantic queryoptimization

The authors present an approach to acquiring knowledge from previously processed queries. By using newly acquired knowledge together with given semantic knowledge, it is possible to make the query processor and/or optimizer more intelligent so that future queries can b processed more efficiently. The acquired knowledge is in the form of constraints. While some constraints are to be enforced for all database states, others are known to be valid for the current state of the database. The former constraints are statistic integrity constraints, while the latter are called dynamic integrity constraints. Some situations in which certain dynamic semantic constraints can be automatically extracted are identified. This automatic tool for knowledge acquisition can also be used as an interactive tool for identifying potential static integrity constraints. The concept of minimal knowledge base is introduced, and a method to maintain the knowledge base is presented. An algorithm to compute the restriction (selection) closure, i.e. all deductible restrictions, from a given set of restrictions, join predicates (as given in a query), and constraints is given     

Ordering and selecting production rules for constraint maintenance:complexity and heuristic solution

Presents a technique for analyzing the run-time behavior of integrity constraint repair actions, i.e. active database rules that are specifically designed to correct violations of database integrity. When constraints become violated due to an incorrect user transaction, rule computation is started to restore the database to a correct state. Since repair actions may be numerous and may conflict with each other, automated support for the analysis of their run-time behavior is necessary. The proposed technique helps the rule base administrator define a repair rule selection strategy such that the computation terminates for every input transaction, the final database state satisfies all the constraints, and the user's preferences among different ways to restore integrity are taken into account. In addition, it can be used by the rule designer to spot “dangerous” rules that may be subject to redesign. This problem is formulated as an optimization problem on directed hypergraphs, which we demonstrate to be NP-hard and which we solve by means of a heuristic algorithm     

Active Integrity Constraints for Database Consistency Maintenance

This paper introduces active integrity constraints (AICs), an extension of integrity constraints for consistent database maintenance. An active integrity constraint is a special constraint whose body contains a conjunction of literals which must be false and whose head contains a disjunction of update actions representing actions (insertions and deletions of tuples) to be performed if the constraint is not satisfied (that is its body is true). The AICs work in a domino-like manner as the satisfaction of one AIC may trigger the violation and therefore the activation of another one. The paper also introduces founded repairs, which are minimal sets of update actions that make the database consistent, and are specified and “supported” by active integrity constraints. The paper presents: 1) a formal declarative semantics allowing the computation of founded repairs and 2) a characterization of this semantics obtained by rewriting active integrity constraints into disjunctive logic rules, so that founded repairs can be derived from the answer sets of the derived logic program. Finally, the paper studies the computational complexity of computing founded repairs.     

Tuple calculus: Formal definition and conversion from first-order calculus

In classical database theory, relational calculus has long been used in expressing query formulae and integrity constraints. In fact, relational calculus formulae are much easier to deal with than first-order formulae when evaluating queries and validating database updates in the database environment. In deductive databases, however, first-order calculus is preferred because it is convenient when proof procedures are involved. Since both situations should coexist in advanced information systems, it is very desirable to devise a conversion procedure between relational calculus and first-order calculus. In this paper, interpretation of first-order formulae in the database environment is discussed first, then tuple calculus, an extension of relational calculus, is presented. This extension enables us to describe query formulae and general rules necessary in advanced information systems, in particular, dealing with complex objects. Finally, a conversion algorithm from first-order formulae into tuple calculus formulae is presented. Several application issues are also included.     

Semantic optimization techniques for preference queries

Preference queries are relational algebra or SQL queries that contain occurrences of the winnow operator (find the most preferred tuples in a given relation). Such queries are parameterized by specific preference relations. Semantic optimization techniques make use of integrity constraints holding in the database. In the context of semantic optimization of preference queries, we identify two fundamental properties: containment of preference relations relative to integrity constraints and satisfaction of order axioms relative to integrity constraints. We show numerous applications of those notions to preference query evaluation and optimization. As integrity constraints, we consider constraint-generating dependencies, a class generalizing functional dependencies. We demonstrate that the problems of containment and satisfaction of order axioms can be captured as specific instances of constraint-generating dependency entailment. This makes it possible to formulate necessary and sufficient conditions for the applicability of our techniques as constraint validity problems. We characterize the computational complexity of such problems.     

Study on consistent query answering in inconsistent databases

Consistent query answering is an approach to retrieving consistent answers over databases that might be inconsistent with respect to some given integrity constraints. The approach is based on a concept of repair. This paper surveys several recent researches on obtaining consistent information from inconsistent databases, such as the underlying semantic model, a number of approaches to computing consistent query answers and the computational complexity of this problem. Furthermore, the work outlines potential research directions in this area.     

Database Repairs and Analytic Tableaux

In this article, we characterize in terms of analytic tableaux the repairs of inconsistent relational databases, that is databases that do not satisfy a given set of integrity constraints. For this purpose we provide closing and opening criteria for branches in tableaux that are built for database instances and their integrity constraints. We use the tableaux based characterization as a basis for consistent query answering, that is for retrieving from the database answers to queries that are consistent with respect to the integrity constraints.     

On the finite controllability of conjunctive query answering in databases under open-world assumption

In this paper we study queries over relational databases with integrity constraints (ICs). The main problem we analyze is OWA query answering, i.e., query answering over a database with ICs under open-world assumption. The kinds of ICs that we consider are inclusion dependencies and functional dependencies, in particular key dependencies; the query languages we consider are conjunctive queries and unions of conjunctive queries. We present results about the decidability of OWA query answering under ICs. In particular, we study OWA query answering both over finite databases and over unrestricted databases, and identify the cases in which such a problem is finitely controllable, i.e., when OWA query answering over finite databases coincides with OWA query answering over unrestricted databases. Moreover, we are able to easily turn the above results into new results about implication of ICs and query containment under ICs, due to the deep relationship between OWA query answering and these two classical problems in database theory. In particular, we close two long-standing open problems in query containment, since we prove finite controllability of containment of conjunctive queries both under arbitrary inclusion dependencies and under key and foreign key dependencies. The results of our investigation are very relevant in many research areas which have recently dealt with databases under an incomplete information assumption: e.g., data integration, data exchange, view-based information access, ontology-based information systems, and peer data management systems.     

Validating database updates

Individual facts in the real world are represented by tuples in database relations (instances), while universal (time-independent) facts are treated as semantic constraints regarding database relation schemata. One important role of these semantic constraints is their use as integrity constraints that must not be violated by update operations. Among these, static constraints are represented by assertions, which are extended relational calculi in which every tuple variable is bound over a relation, and become true in a consistent database. When an update has been made on a consistent database, it is necessary to ascertain if the updated database is still consistent. It can be done by evaluating all the assertions in the updated database, but this is very time consuming. If a given assertion is in one of some classes, it is possible to devise an efficient validation procedure, which before the update is actually applied determines if the update violates the given assertion. In many cases a simplified form can be found, by examining whose value the properness of the given update is determined. The existence of such an efficient procedure and simplified form depends on what class the given assertion belongs, and also on what type of the update is to be made on what relation. This paper presents a method of finding such a procedure and simplified form using several simple syntactical transformation rules regarding extended relational calculi. This method is based on several basic properties in prepositional logic and many-sorted predicate logic.     

区间约束及其代数查询语言

提出了区间约束和基于区间约束的代数查询语言。区间约束与密序约束相经,增加了简单的加减运算,具有更强的描述能力,同时区间约束元组有简洁,唯一的规范区间表示,文中给出了计算区间约束的规范区间表示的算法,针对区间约束关系,定义了基本代数操作的语法及语义,研究了代数查询语言,并证明代数约束查询语言满足封闭性,最后讨论了区间约束的实现与应用。     

Transaction repair for integrity enforcement

A transaction repair system detects erroneous transactions as they update the database, and for each erroneous transaction, it finds the necessary and sufficient changes to the transaction that would repair it. Detection and repair are the two essential components of semantic integrity maintenance since detection alone would leave the user with the difficult responsibility of manually correcting and reentering an erroneous transaction. Both detection and repair rely on incremental integrity maintenance techniques. The detection process takes advantage of the integrity of the database before the transaction, and detects only the new errors introduced by the transaction. The repair process takes advantage of the integrity before the transaction and integrity violation after the transaction but before the repair. Such a two-step incremental analysis produces the minimal repair necessary and sufficient to correct the transaction. All necessary and sufficient repairs are generated, for all first order constraints, and by using only substitution with no resolution search. Multiple constraints are repaired in parallel, with no sequencing of constraints, and no possibility of cycles. Extensions to recursive constraints and nondeterministic transactions are provided     

A logical framework for querying and repairing inconsistent databases

In this paper, we address the problem of managing inconsistent databases, i.e., databases violating integrity constraints. We propose a general logic framework for computing repairs and consistent answers over inconsistent databases. A repair for a possibly inconsistent database is a minimal set of insert and delete operations which makes the database consistent, whereas a consistent answer is a set of tuples derived from the database, satisfying all integrity constraints. In our framework, different types of rules defining general integrity constraints, repair constraints (i.e., rules defining conditions on the insertion or deletion of atoms), and prioritized constraints (i.e., rules defining priorities among updates and repairs) are considered. We propose a technique based on the rewriting of constraints into (prioritized) extended disjunctive rules with two different forms of negation (negation as failure and classical negation). The disjunctive program can be used for two different purposes: to compute "repairs" for the database and produce consistent answers, i.e., a maximal set of atoms which do not violate the constraints. We show that our technique is sound, complete (each preferred stable model defines a repair and each repair is derived from a preferred stable model), and more general than techniques previously proposed.     

The use of deleted tuples in database querying and updating

The traditional approach to database querying and updating treats insertions and deletions of tuples in an asymmetric manner: if a tuple is inserted then, intuitively, we think of as being true and we use this knowledge in query and update processing; in contrast, if a tuple is deleted then we think of as being false but we do not use this knowledge at all! In this paper, we present a new approach to database querying and updating in which insertions and deletions of tuples are treated in a symmetric manner. Contrary to the traditional approach, we use both inserted and deleted tuples in our derivation algorithms. Our approach works as follows: if the deletion of a tuple is requested, then we mark as being deleted without removing it from the database; if the insertion of a tuple is requested, then we simply place in the database and remove all its marked subtuples. Derivation of tuples is done using two derivation rules under one constraint: a tuple is derived only if has no marked subtuples in the database. The derivation rules reflect relational projection and relational join. The main contribution of our work is to provide a method which allows insertion or deletion of a tuple over any relation scheme in a deterministic way. Received: 12 June 1995 / 19 February 1997     

Implication and referential constraints: a new formal reasoning

The authors address the issue of reasoning with two classes of commonly used semantic integrity constraints in database and knowledge-base systems: implication constraints and referential constraints. They first consider a central problem in this respect, the IRC-refuting problem, which is to decide whether a conjunctive query always produces an empty relation on (finite) database instances satisfying a given set of implication and referential constraints. Since the general problem is undecidable, they only consider acyclic referential constraints. Under this assumption, they prove that the IRC-refuting problem is decidable, and give a novel necessary and sufficient condition for it. Under the same assumption, they also study several other problems encountered in semantic query optimization, such as the semantics-based query containment problem, redundant join problem, and redundant selection-condition problem, and show that they are polynomially equivalent or reducible to the IRC-refuting problem. Moreover, they give results on reducing the complexity for some special cases of the IRC-refuting problem     

Fast graph query processing with a low-cost index

This paper studies the problem of processing supergraph queries, that is, given a database containing a set of graphs, find all the graphs in the database of which the query graph is a supergraph. Existing works usually construct an index and performs a filtering-and-verification process, which still requires many subgraph isomorphism testings. There are also significant overheads in both index construction and maintenance. In this paper, we design a graph querying system that achieves both fast indexing and efficient query processing. The index is constructed by a simple but fast method of extracting the commonality among the graphs, which does not involve any costly operation such as graph mining. Our query processing has two key techniques, direct inclusion and filtering. Direct inclusion allows partial query answers to be included directly without candidate verification. Our filtering technique further reduces the candidate set by operating on a much smaller projected database. Experimental results show that our method is significantly more efficient than the existing works in both indexing and query processing, and our index has a low maintenance cost.     

Logic-based query optimization for object databases

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