Search

An uncertain database db is defined as a database in which distinct tuples of the same relation can agree on their primary key. A repair is obtained by selecting a maximal number of tuples without ever selecting two distinct tuples of the same relation that agree on their primary key. Obviously, the number of possible repairs can be exponential in the size of the database. Given a Boolean query q, certain (or consistent) query answering concerns the problem to decide whether q evaluates to true on every repair. In this article, we study a counting variant of consistent query answering. For a fixed Boolean query q, we define @?CERTAINTY(q) as the following counting problem: Given an uncertain database db, how many repairs of db satisfy q? Our main result is that conjunctive queries q without self-join exhibit a complexity dichotomy: @?CERTAINTY(q) is in FP or @?P-complete.

View-based query answering is the problem of answering a query based only on the precomputed answers to a set of views. While this problem has been widely investigated in databases, it is largely unexplored in the context of Description Logic ontologies. Differently from traditional databases, Description Logics may express several forms of incomplete information, and this poses challenging problems in characterizing the semantics of views. In this paper, we first present a general framework for view-based query answering, where we address the above semantical problems by providing two notions of view-based query answering over ontologies, all based on the idea that the precomputed answers to views are the certain answers to the corresponding queries. We also relate such notions to privacy-aware access to ontologies. Then, we provide decidability results, algorithms, and data complexity characterizations for view-based query answering in several Description Logics, ranging from those with limited modeling capability to highly expressive ones.

The complexity of containment and satisfiability of conjunctive queries over finite, unranked, labeled trees is studied with respect to the axes Child, NextSibling, their transitive and reflexive closures, and Following. For the containment problem a trichotomy is presented, classifying the problems as in PTIME, coNP-complete, or Π2P-complete. For the satisfiability problem most problems are classified as either in PTIME or NP-complete.

The problem of query containment is fundamental to many aspects of database systems, including query optimization, determining independence of queries from updates, and rewriting queries using views. In the data-integration framework, however, the standard notion of query containment does not suffice. We define relative containment, which formalizes the notion of query containment relative to the sources available to the data-integration system. First, we provide optimal bounds for relative containment for several important classes of datalog queries, including the common case of conjunctive queries. Next, we provide bounds for the case when sources enforce access restrictions in the form of binding pattern constraints. Surprisingly, we show that relative containment for conjunctive queries is still decidable in this case, even though it is known that finding all answers to such queries may require a recursive datalog program over the sources. Finally, we provide tight bounds for variants of relative containment when the queries and source descriptions may contain comparison predicates.

Semistructured data occur in situations where information lacks a homogeneous structure and is incomplete. Yet, up to now the incompleteness of information has not been reflected by special features of query languages. Our goal is to investigate the principles of queries that allow for incomplete answers. We do not present, however, a concrete query language. Queries over classical structured data models contain a number of variables and constraints on these variables. An answer is a binding of the variables by elements of the database such that the constraints are satisfied. In the present paper, we loosen this concept in so far as we allow also answers that are partial; that is, not all variables in the query are bound by such an answer. Partial answers make it necessary to refine the model of query evaluation. The first modification relates to the satisfaction of constraints: in some circumstances we consider constraints involving unbound variables as satisfied. Second, in order to prevent a proliferation of answers, we only accept answers that are maximal in the sense that there are no assignments that bind more variables and satisfy the constraints of the query. Our model of query evaluation consists of two phases, a search phase and a filter phase. Semistructured databases are essentially labeled directed graphs. In the search phase, we use a query graph containing variables to match a maximal portion of the database graph. We investigate three different semantics for query graphs, which give rise to three variants of matching. For each variant, we provide algorithms and complexity results. In the filter phase, the maximal matchings resulting from the search phase are subjected to constraints, which may be weak or strong. Strong constraints require all their variables to be bound, while weak constraints do not. We describe a polynomial algorithm for evaluating a special type of queries with filter constraints, and assess the complexity of evaluating other queries for several kinds of constraints. In the final part, we investigate the containment problem for queries consisting only of search constraints under the different semantics.

When answering queries using external information sources, the contents of the queries can be described by views. To answer a query, we must rewrite it using the set of views presented by the sources. When the external information sources also have the ability to answer some (perhaps limited) sets of queries that require performing operations on their data, the set of views presented by the source may be infinite (albeit encoded in some finite fashion). Previous work on answering queries using views has only considered the case where the set of views is finite. In order to exploit the ability of information sources to answer more complex queries, we consider the problem of answering conjunctive queries using infinite sets of conjunctive views. Our first result is that an infinite set of conjunctive views can be partitioned into a finite number of equivalence classes, such that picking one view from every nonempty class is sufficient to determine whether the query can be answered using the views. Second, we show how to compute the set of equivalence classes for sets of conjunctive views encoded by a datalog program. Furthermore, we extend our results to the case when the query and the views use the built-in predicates

After inserting a tuple into or deleting a tuple from a database, a first-order incremental evaluation system (or a “foies”) for a database query derives the new query answer by using a first-order query on the new database, the old answer, and perhaps some stored auxiliary relations. Moreover, the auxiliary relations must also be maintained similarly using first-order queries. In this paper we measure the space needed by foies in terms of the maximal arity of the auxiliary relations and present results on the existence and nonexistence of such space-restricted foies for a variety of graph queries, including counting and transitive closure. We construct space efficient foies for these queries and show that the arity bounds are tight using Ehrenfeucht–Fraı̈ssé games. In particular, for transitive closure over undirected graphs, the minimum arity bound of its foies is shown to be exactly two; this resolves an open problem raised by Patnaik and Immerman in 1994. For the general case, we show that the arity-based hierarchy is strict for all arities. The strictness proof uses queries with input relations having arities much larger than the auxiliary relations. It is still open whether the hierarchy remains strict for arities two or greater when the input relations of queries have arities bounded by a fixed number, such as two, or by the arities of the auxiliary relations. Finally, we consider a variation of foies where the cost of storing the answer to the query is also “charged.” We show that the arity hierarchy in this case is also strict. The positions of queries in the two arity-based hierarchies can differ; we give the positions in this hierarchy of the queries considered for the other arity hierarchy.

The method of the canonical connection introduced by Maier and Ullman provides an optimal procedure for query processing in universal-relation databases. We present an algorithm for computing canonical connections in a database scheme which is more efficient than the classical algorithm based on tableau reduction. Moreover, with a slight modification of the algorithm we obtain a join plan which succeeds in controlling the nonmonotonicity of cyclic canonical connections.

Much of the work to date on the optimization of queries for relational databases has focussed on the case where the only dependencies allowed are functional dependencies. We extend this work to the case where inclusion dependencies are also allowed. We show that there are substantial special cases where the presence of inclusion dependencies does not make the basic problems of optimization any harder than they are when there are no dependencies at all. In particular, we show that the problems of query containment, equivalence, and nonminimality remain in NP when either (a) all dependencies are inclusion dependencies or (b) the set of dependencies is what we call “key-based.” These results assume that infinite databases are allowed. If only finite databases are allowed, new containments and equivalences may arise, as we illustrate by an example, and the problems may be substantialy more difficult. We can, however, prove a “finite controllability” theorem that shows that no such examples exist for case (b), or for (a) when the only inclusion dependencies allowed are those having “width” equal to one.

Or-sets were introduced by Imielinski, Naqvi, and Vadaparty for dealing with limited forms of disjunctive information in database queries. Independently, Rounds used a similar notion for representing disjunctive and conjunctive information in the context of situation theory. In this paper we formulate a query language with adequate expressive power for or-sets. Using the notion of normalization of or-sets, queries at the “structural” and “conceptual” levels are distinguished. Losslessness of normalization is established for a large class of queries. We obtain upper bounds for the cost of normalization. An approach related to that of Rounds is used to provide semantics for or-sets. We also treat or-sets in the context of partial information in databases.