Search

From a set of existing tuples, a skyline operator retrieves only a subset, superior tuples that are of a person’s interest and are non-dominant. Processing of queries using the skyline operator is an expensive and exhaustive task. It gets more complicated when skyline queries are applied on partially complete data and databases are distributed over different data centers. Incompleteness in data raises many issues such as compromise on transitivity property and the threat of cyclic dominance to occur within database. To overcome such issues this paper proposes an efficient algorithm called Cloud-based Incomplete Data Skyline algorithm (CIDS) for processing skyline queries over partially complete databases in cloud environment. The algorithm retrieves superior tuples with the aim of reducing domination tests between the tuples, decreasing processing time and reducing the huge amount of data flow from one data center to another. Several experiments have been conducted over different types of datasets, and results have proven that the proposed algorithm outplays the existing algorithms in terms of processing time, domination tests as well as the amount of data flow.

We study the complexity of various fundamental counting problems that arise in the context of incomplete databases, i.e., relational databases that can contain unknown values in the form of labeled nulls. Specifically, we assume that the domains of these unknown values are finite and, for a Boolean query q, we consider the following two problems: Given as input an incomplete database D, (a) return the number of completions of D that satisfy q; or (b) return the number of valuations of the nulls of D yielding a completion that satisfies q. We obtain dichotomies between #P-hardness and polynomial-time computability for these problems when q is a self-join–free conjunctive query and study the impact on the complexity of the following two restrictions: (1) every null occurs at most once in D (what is called Codd tables); and (2) the domain of each null is the same. Roughly speaking, we show that counting completions is much harder than counting valuations: For instance, while the latter is always in #P, we prove that the former is not in #P under some widely believed theoretical complexity assumption. Moreover, we find that both (1) and (2) can reduce the complexity of our problems. We also study the approximability of these problems and show that, while counting valuations always has a fully polynomial-time randomized approximation scheme (FPRAS), in most cases counting completions does not. Finally, we consider more expressive query languages and situate our problems with respect to known complexity classes. [ABSTRACT FROM AUTHOR]

A lot of research activity has recently taken place around the chase procedure, due to its usefulness in data integration, data exchange, query optimization, peer data exchange and data correspondence, to mention a few. As the chase has been investigated and further developed by a number of research groups and authors, many variants of the chase have emerged and associated results obtained. Due to the heterogeneous nature of the area it is frequently difficult to verify the scope of each result. In this paper we take closer look at recent developments, and provide additional results. Our analysis allows us create a taxonomy of the chase variations and the properties they satisfy. Two of the most central problems regarding the chase is termination, and discovery of restricted classes of sets of dependencies that guarantee termination of the chase. The search for the restricted classes has been motivated by a fairly recent result that shows that it is undecidable (RE-complete, to be more precise) to determine whether the chase with a given dependency set will terminate on a given instance. There is a small dissonance here, since the quest has been for classes of sets of dependencies guaranteeing termination of the chase on all instances, even though the latter problem was not known to be undecidable. We resolve the dissonance in this paper by showing that determining whether the chase with a given set of dependencies terminates on all instances is unsolvable, and on level II02 in the Arithmetical Hierarchy. For this we use a reduction from word rewriting systems, thereby also showing the close connection between the chase and word rewriting. The same reduction also gives us the aforementioned instancedependent RE-completeness result as a byproduct. For one of the restricted classes guaranteeing termination on all instances, the stratified sets dependencies, we provide new complexity results for the problem of testing whether a given set of dependencies belongs to it. These results rectify some previous claims that have occurred in the literature. [ABSTRACT FROM AUTHOR]

With the proliferation of mobile devices and wireless technologies, location based services (LBSs) are becoming popular in smart cities. Two important classes of LBSs are Nearest Neighbor (NN) queries and range queries that provide user information about the locations of point of interests (POIs) such as hospitals or restaurants. Answers of these queries are more reliable and satisfiable if they come from trustworthy crowd instead of traditional location service providers (LSPs). We introduce an approach to evaluate NN and range queries with crowdsourced data and computation that eliminates the role of an LSP. In our crowdsourced approach, a user evaluates LBSs in a group. It may happen that group members do not have knowledge of all POIs in a certain area. We present efficient algorithms to evaluate queries with accuracy guarantee in incomplete databases. Experiments show that our approach is scalable and incurs less computational overhead. [ABSTRACT FROM AUTHOR]

Abstract: 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. [Copyright &y& Elsevier]

Abstract: This paper addresses the problem of efficiently computing consistent answers to queries over relational databases which may be inconsistent with respect to functional dependencies and foreign key constraints. Since consistent query answers over inconsistent databases are obtained from repaired databases, we first present a repair strategy. More specifically, in this paper we consider particular sets of functional dependencies, called canonical, and a repair strategy whereby only tuple updates and insertions are allowed in order to restore consistency: if foreign key constraints are violated, new tuples (possibly containing null values) are inserted into the database, whereas if functional dependency violations occur, tuple updates (possibly introducing unknown values, i.e. special symbols which can take values from a limited set of constants of the source database) are performed. Therefore, we propose a semantics of constraint satisfaction for incomplete databases containing null and unknown values since the repair process can lead to such databases. The proposed approach allows us to obtain a unique (incomplete) repaired database which may be computed in polynomial time. Drawing on the results on the complexity of querying incomplete databases containing OR-objects, we identify classes of constraints for which the consistent answers to particular classes of conjunctive queries can be computed in polynomial time. [Copyright &y& Elsevier]

Abstract: Answering queries over an incomplete database w.r.t. a set of constraints is an important computational task with applications in fields as diverse as information integration and metadata management in the semantic Web. Description Logics (DLs) are constraint languages that have been extensively studied with the goal of providing useful modeling constructs while keeping the query answering problem decidable. For many DLs, query answering under constraints can be solved via query rewriting: given a conjunctive query Q and a set of DL constraints , the query Q can be transformed into a datalog query that takes into account the semantic consequences of ; then, to obtain answers to Q w.r.t. and some (arbitrary) database instance , one can simply evaluate over using existing (deductive) database technology, without taking into account. In this paper, we present a novel query rewriting algorithm that handles constraints modeled in the DL and use it to show that answering conjunctive queries in this setting is PTime-complete w.r.t. data complexity. Our algorithm deals with various description logics of the and DL-Lite families and is worst-case optimal w.r.t. data complexity for all of them. [Copyright &y& Elsevier]

This paper addresses the problem of representing the set of repairs of a possibly inconsistent database by means of a disjunctive database. Specifically, the class of denial constraints is considered. We show that, given a database and a set of denial constraints, there exists a (unique) disjunctive database, called canonical, which represents the repairs of the database w.r.t. the constraints and is contained in any other disjunctive database with the same set of minimal models. We propose an algorithm for computing the canonical disjunctive database. Finally, we study the size of the canonical disjunctive database in the presence of functional dependencies for both subset-based repairs and cardinality-based repairs. [ABSTRACT FROM AUTHOR]

Controlled query evaluation (CQE) preserves confidentiality in information systems at runtime. A confidentiality policy specifies the information a certain user is not allowed to know. At each query, a censor checks whether the answer would enable the user to learn any classified information. In that case, the answer is distorted, either by lying or by refusal. We introduce a framework in which CQE can be analyzed wrt. possibly incomplete logic databases. For each distortion method, lying and refusal, a class of confidentiality-preserving mechanisms is presented. Furthermore, we specify a third approach that combines lying and refusal and compensates the disadvantages of the respective uniform methods. The enforcement methods are compared to the existing methods for complete databases. [ABSTRACT FROM AUTHOR]