Completeness is a crucial data quality aspect that deals with the question: do we have all the data we need? The lack of awareness on the completeness state of a knowledge graph (KG) may result in bias or even falsity for any decisions made based on the KG. Given a KG, one may be wondering how its completeness may vary across different topics. In this paper, we present ProWD, a framework and tool for profiling the completeness of Wikidata, a central KG on the (Semantic) Web that is open and free to use. ProWD measures the degree of completeness based on the Class-Facet-Attribute (CFA) profiles. A class denotes a collection of entities, which can be of multiple facets, allowing attribute completeness to be analyzed and compared, e.g., how does the completeness of the attribute "educated at" and "date of birth" compare between male, German computer scientists, and female, Indonesian computer scientists? ProWD generates summaries and visualizations for such analysis, giving insights into the KG completeness. ProWD is available online at~\urlhttp://prowd.id.

Most news summarization techniques are static, and thus do not satisfy user needs in having summaries with specific structures or details. Meanwhile, existing dynamic techniques such as query-based summarization fail to handle content-independent queries that target the type of summary information such as time, location, reasons, and consequences of reported events. The NEWS system supports multi-granular summarization along two dimensions: the level of detail and type of information. The system employs fine-grained information extraction to extract facts and their facets with type tagging. The extracted information is then modeled as a graph used to create summaries. The system incrementally expands summaries based on the nodes visited by users, folding related events into the search space.

Recent knowledge extraction methods are moving towards ternary and higher-arity relations to capture more information about binary facts. An example is to include the time, the location, and the duration of a specific fact. These relations can be even more complex to extract in advanced domains such as news, where events typically come with different facets including reasons, consequences, purposes, involved parties, and related events. The main challenge consists in first finding the set of facets related to each fact, and second tagging those facets to the relevant category.

The Semantic Web is commonly interpreted under the open-world assumption, meaning that information available (e.g., in a data source) captures only a subset of the reality. Therefore, there is no certainty about whether the available information provides a complete representation of the reality. The broad aim of this article is to contribute a formal study of how to describe the completeness of parts of the Semantic Web stored in RDF data sources. We introduce a theoretical framework allowing augmentation of RDF data sources with statements, also expressed in RDF, about their completeness. One immediate benefit of this framework is that now query answers can be complemented with information about their completeness. We study the impact of completeness statements on the complexity of query answering by considering different fragments of the SPARQL language, including the RDFS entailment regime, and the federated scenario. We implement an efficient method for reasoning about query completeness and provide an experimental evaluation in the presence of large sets of completeness statements.

Organizations continuously accumulate data, often according to some business processes. If one poses a query over such data for decision support, it is important to know whether the query is stable, that is, whether the answers will stay the same or may change in the future because business processes may add further data. We investigate query stability for conjunctive queries. To this end, we define a formalism that combines an explicit representation of the control flow of a process with a specification of how data is read and inserted into the database. We consider different restrictions of the process model and the state of the system, such as negation in conditions, cyclic executions, read access to written data, presence of pending process instances, and the possibility to start fresh process instances. We identify for which restriction combinations stability of conjunctive queries is decidable and provide encodings into variants of Datalog that are optimal with respect to the worst-case complexity of the problem.

Data completeness is commonly regarded as one of the key aspects of data quality. With this paper we make two main contributions: (i) we develop techniques to reason about the completeness of a query answer over a partially complete database, taking into account constraints that hold over the database, and (ii) we implement them by an encoding into logic programming paradigms. As constraints we consider primary and foreign keys as well as finite domain constraints. In this way we can identify more situations in which a query is complete than was possible with previous work. For each combination of constraints, we establish characterizations of the completeness reasoning and we show how to translate them into logic programs. As a proof of concept we ran our encodings against test cases that capture characteristics of a real-world scenario.

News websites give their users the opportunity to participate in discussions about published articles, by writing comments. Typically, these comments are unstructured making it hard to understand the flow of user discussions. Thus, there is a need for organizing comments to help users to (1) gain more insights about news topics, and (2) have an easy access to comments that trigger their interests. In this work, we address the above problem by organizing comments around the entities and the aspects they discuss. More specifically, we propose an approach for entity and aspect extraction from user comments through the following contributions. First, we extend traditional Named-Entity Recognition approaches, using coreference resolution and external knowledge bases, to detect more occurrences of entities in comments. Second, we exploit part-of-speech tag, dependency tag, and lexical databases to extract explicit and implicit aspects around discussed entities. Third, we evaluate our entity and aspect extraction approach, on manually annotated data, showing that it highly increases precision and recall compared to baseline approaches.

In many applications including loosely coupled cloud databases, collaborative editing and network monitoring, data from multiple sources is regularly used for query answering. For reasons such as system failures, insufficient author knowledge or network issues, data may be temporarily unavailable or generally nonexistent. Hence, not all data needed for query answering may be available.

Many kinds of information, such as addresses, crawls of webpages, or academic affiliations, are prone to becoming outdated over time. Therefore, in some applications, updates are performed periodically in order to keep the correctness and usefulness of such information high. As refreshing information usually has a cost, e.g. computation time, network bandwidth or human work time, a problem is to find the right update frequency depending on the benefit gained from the information and on the speed with which the information is expected to get outdated.

Real-life spatial databases are inherently incomplete. This is in particular the case when data from different sources are combined. An extreme example are volunteered geographical information systems like OpenStreetMap.

We present a system that computes for a query that may be incomplete, complete approximations from above and from below. We assume a setting where queries are posed over a partially complete database, that is, a database that is generally incomplete, but is known to contain complete information about specific aspects of its application domain. Which parts are complete, is described by a set of so-called table-completeness statements. Previous work led to a theoretical framework and an implementation that allowed one to determine whether in such a scenario a given conjunctive query is guaranteed to return a complete set of answers or not. With the present demonstrator we show how to reformulate the original query in such a way that answers are guaranteed to be complete. If there exists a more general complete query, there is a unique most specific one, which we find. If there exists a more specific complete query, there may even be infinitely many. In this case, we find the least specific specializations whose size is bounded by a threshold provided by the user. Generalizations are computed by a fixpoint iteration, employing an answer set programming engine. Specializations are found leveraging unification from logic programming.

Data completeness is an important aspect of data quality. We consider a setting, where databases can be incomplete in two ways: records may be missing and records may contain null values. We (i) formalize when the answer set of a query is complete in spite of such incompleteness, and (ii) we introduce table completeness statements, by which one can express that certain parts of a database are complete. We then study how to deduce from a set of table-completeness statements that a query can be answered completely.

MAGIK demonstrates how to use meta-information about the completeness of a database to assess the quality of the answers returned by a query. The system holds so-called table-completeness (TC) statements, by which one can express that a table is partially complete, that is, it contains all facts about some aspect of the domain.

Sources of data uncertainty and imprecision are numerous. A way to handle this uncertainty is to associate probabilistic annotations to data. Many such probabilistic database models have been proposed, both in the relational and in the semi-structured setting. The latter is particularly well adapted to the management of uncertain data coming from a variety of automatic processes. An important problem, in the context of probabilistic XML databases, is that of answering aggregate queries (count, sum, avg, etc.), which has received limited attention so far. In a model unifying the various (discrete) semi-structured probabilistic models studied up to now, we present algorithms to compute the distribution of the aggregation values (exploiting some regularity properties of the aggregate functions) and probabilistic moments (especially expectation and variance) of this distribution. We also prove the intractability of some of these problems and investigate approximation techniques. We finally extend the discrete model to a continuous one, in order to take into account continuous data values, such as measurements from sensor networks, and extend our algorithms and complexity results to the continuous case.

Sources of data uncertainty and imprecision are numerous. A way to handle this uncertainty is to associate probabilistic annotations to data. Many such probabilistic database models have been proposed, both in the relational and in the semi-structured setting. The latter is particularly well adapted to the management of uncertain data coming from a variety of automatic processes. An important problem, in the context of probabilistic XML databases, is that of answering aggregate queries (count, sum, avg, etc.), which has received limited attention so far. In a model unifying the various (discrete) semi-structured probabilistic models studied up to now, we present algorithms to compute the distribution of the aggregation values (exploiting some regularity properties of the aggregate functions) and probabilistic moments (especially, expectation and variance) of this distribution. We also prove the intractability of some of these problems and investigate approximation techniques. We finally extend the discrete model to a continuous one, in order to take into account continuous data values, such as measurements from sensor networks, and present algorithms to compute distribution functions and moments for various classes of continuous distributions of data values.

Information integration is becoming a critical problem for both businesses and individuals. The data, especially the one that comes from the Web, is naturally incomplete, that is, some data values may be unknown or lost because of communication problems, hidden due to privacy considerations. At the same time research in (virtual) integration in the community focusses on null-free sources and addresses limited forms of incompleteness only. In our work we aim to extend current results on virtual integration by considering various forms of incompleteness at the level of the sources, the integrated database and the queries (we call this Incomplete Information Integration , or III). More specifically, we aim to extend current query answering techniques for local-, and global-as-view integration to integration of tables with SQL nulls, Codd tables, etc. We also aim to consider incomplete answers as a natural extension of the classical approach. Our main research issues are (i) semantics of III, (ii) semantics of query answering in III, (iii) complexity of query answering, and (iv) algorithms (possibly approximate) to compute the answers.

Equivalence of aggregate queries is investigated for the class of conjunctive queries with comparisons and the aggregate operators count, count-distinct, min, max, and sum. Essentially, this class contains unnested SQL queries with the above aggregate operators, with a where clause consisting of a conjunction of comparisons, and without a having clause. The comparisons are either interpreted over a domain with a dense order (like the rationals) or with a discrete order (like the integers). Characterizations of equivalence differ for the two cases. For queries with either max or min, equivalence is characterized in terms of dominance mappings, which can be viewed as a generalization of containment mappings. For queries with the count-distinct operator, a sufficient condition for equivalence is given in terms of equivalence of conjunctive queries under set semantics. For some special cases, it is shown that this condition is also necessary. For conjunctive queries with comparisons but without aggregation, equivalence under bag-set semantics is characterized in terms of isomorphism. This characterization essentially remains the same also for queries with the count operator. Moreover, this characterization also applies to queries with the sum operator if the queries have either constants or comparisons, but not both. In the general case (i.e., both comparisons and constants), the characterization of the equivalence of queries with the sum operator is more elaborate. All the characterizations given in the paper are decidable in polynomial space.

The problem of rewriting aggregate queries using views is studied for conjunctive queries with arbitrary aggregation functions and built-in predicates. Two types of queries over views are introduced for rewriting aggregate queries: pure candidates and aggregate candidates . Pure candidates can be used to rewrite arbitrary aggregate queries. Aggregate candidates can be used to rewrite queries containing aggregate functions definable in terms of a commutative-semigroup operation. For both types of candidates (as well as for several relaxations of these candidates), the unfolding property holds. This allows characterizations for query equivalence to be used to determine whether a candidate is a rewriting of a query. The complexity of the rewriting-existence problem is also studied and upper and lower complexity bounds are given.

Query equivalence is investigated for disjunctive aggregate queries with negated subgoals, constants and comparisons. A full characterization of equivalence is given for the aggregation functions count, max, sum, prod, top2 and parity . A related problem is that of determining, for a given natural number N , whether two given queries are equivalent over all databases with at most N constants. This problem is called bounded equivalence . A complete characterization of decidability of bounded equivalence is given. In particular, it is shown that this problem is decidable for all the above aggregation functions as well as for cntd (count distinct) and avg . For quasilinear queries (i.e., queries in which predicates that occur positively are not repeated), it is shown that equivalence can be decided in polynomial time for the aggregation functions count, max, sum, prty, prod, top2 and avg . A similar result holds for cntd provided that a few additional conditions hold. The results are couched in terms of abstract characteristics of aggregation functions, and new proof techniques are used. Finally, the results above also imply that equivalence, under bag-set semantics, is decidable for nonaggregate queries with negation.

Abstract EquiX is a search language for XML that combines the power of querying with the simplicity of searching. Requirements for such languages are discussed, and it is shown that EquiX meets the necessary criteria. Both a graph‐based abstract syntax and a formal concrete syntax are presented for EquiX queries. In addition, the semantics is defined and an evaluation algorithm is presented. The evaluation algorithm is polynomial under combined complexity. EquiX combines pattern matching, quantification, and logical expressions to query both the data and meta‐data of XML documents. The result of a query in EquiX is a set of XML documents. A DTD describing the result documents is derived automatically from the query.

Query equivalence is investigated for disjunctive aggregate queries with negated subgoals, constants and comparisons. A full characterization of equivalence is given for the aggregation functions count, max, sum, prod, top2 and parity. A related problem is that of determining, for a given natural number N, whether two given queries are equivalent over all databases with at most N constants. We call this problem bounded equivalence. A complete characterization of decidability of bounded equivalence is given. In particular, it is shown that this problem is decidable for all the above aggregation functions as well as for cntd (count distinct) and avg. For quasilinear queries (i.e., queries where predicates that occur positively are not repeated) it is shown that equivalence can be decided in polynomial time for the aggregation functions count, max, sum, parity, prod, top2 and avg. A similar result holds for cntd provided that a few additional conditions hold. The results are couched in terms of abstract characteristics of aggregation functions, and new proof techniques are used. Finally, the results above also imply that equivalence, under bag-set semantics, is decidable for non-aggregate queries with negation. 1

We investigate the problem of rewriting queries with aggregate\noperators using views that may or may not contain aggregate\noperators. A rewriting of a query is a second query\nthat uses view predicates such that evaluating first the views\nand then the rewriting yields the same result as evaluating\nthe original query. In this sense, the original query and the\nrewriting are equivalent modulo the view definitions. The\nqueries and views we consider correspond to unnested SQL\nqueries, possibly with union, that employ the operators min,\nmax, count, and sum.\nOur approach is based on syntactic characterizations of the equivalence of aggregate queries. One contribution of this paper are characterizations of the equivalence of disjunctive aggregate queries, which generalize our previous results for the conjunctive case.\nFor each operator a, we introduce several types of queries using views as candidates for rewritings. We unfold such a candidate by replacing each occurrence of a view predicate with its definition, thus obtaining a regular aggregate query. The candidates have a different, usually more complex operator than a. We prove that unfolding the candidate, however, results in a regular aggregate query that is equivalent to the candidate modulo the view definitions. This property justifies considering these types of queries as natural candidates for rewritings. In this way, we reduce the problem of whether there exist rewritings of a particular type to a problem involving equivalence.\nWe distinguish between partial rewritings that contain at least one view predicate and complete rewritings that contain only view predicates. In contrast to previous work on this topic, we not only give sufficient, but also necessary conditions for a rewriting to exist. More precisely, we show for each type of candidate that the existence of both, partial and complete rewritings is decidable, and we provide upper and lower complexity bounds.

Semistructured data occur in situations where informationThe growing need to integrate data from heterogeneous lacks a homogeneous structure and is incomplete.Yet, up to sources and to access data sources with irregular or incomnow the incompleteness of information has not been reflected plete contents is the main motivation for research into semiby special features of query languages for semistructured structured data models and query languages for them.Semidata.Our goal is to investigate the principles of queries that structured data do not comply with a strict schema and allow for incomplete answers.We do not present, however, are inherently incomplete.Query languages for such data a concrete query language.should ,reflect these characteristics.Queries over classical structured data models contain a number of variables and conditions on these variables.An answer is a binding of the variables by elements of the database such that the conditions 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 conditions: under some circumstances we consider conditions 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 conditions of the query.

E Franconi, G De Giacomo, IR Horrocks, DL McGuinness, W Nutt, PF Patel-Schneider, CA Welty; Conferences. Report on the 1998 International Workshop on Descriptio

Equivalcncc of aggregate queries is investigated for the class of conjunctive queries with comparisons and the aggregate operators min, max, count, count-distinct, and sum.Essentlally, this class contains all unnested SQL queries with the above aggregate operators, with a WHERE clause consisting of a conjunction of comparisons, and without a HAVING clause.The comparisons can be interpreted over either a dense order (c,g., over the rationals) or a discrete order (e.g., over the integers).Generally, however, different techniques and characterizations are needed in each of these two case-s.For queries with either max or min, equivalence is characterlzcd in terms of dominance mappings, which can be viewed aa a goncralization of containment mappings.For queries with the count-distinct operator, a sufficient condition for cquivalcncc is given in terms of equivalence of conjunctive qucrics under set semantics.For some special cases, it is shown that this condition is also necessary.For conjunctive queries with comparisons but without aggregation, equivalence under bag-set semantics is characterized in terms of isomorphism, This characterization essentially remains the same also for queries with the count operator.Moreover, this characterization also applies to queries with the sum operator if the queries have either constants or comparisons, but not both.In the general case (i.e., both comparisons and constants), the characterization of the equivalence of queries with the sum operator is more elaborate.All the characterizations given in the paper are decidable with polynomial spncc, Finally, it is shown that all the characterizations for min-, max-, count-, and sum-queries yield polynomial-time algorithms for linear queries, i.e., queries with no repeated prcdicatcs in their bodies.