Finding a subset of representative items from a large set of data items has been studied extensively, under a variety of conditions and constraints. In our setting, data items belong to a metric space and also have a sensitive attribute (e.g., gender, race). Our focus is on effectively choosing a set of representatives while taking into consideration two distinct notions of fairness. First, each data item in the dataset should be similar to a representative (while precisely how similar depends on data distributions). Second, representatives should satisfy a given social equity constraint specifying the number of representatives with each attribute value. To satisfy these two fairness requirements, we build upon previous results in fair facility location, extending this work to allow for social equity constraints. Our extension is parameterized by requirements on the neighborhood of data items, and we show lower and upper bounds for an optimal algorithm for some cases, and NP-completeness results for others. We then further extend this work to ensure that representatives should be similar, in their attribute values, to the set of data that they represent. To this end, we develop methods to choose items that are highly representative of their surrounding data items, while still satisfying a social equity constraint. Combining these results yields a method that can be leveraged to choose representative data items while simultaneously meeting several fairness requirements. Experimental results show the quality of our results and demonstrate that, in practice, the cost for social equity (in terms of increased distance to representatives) is low.

Assigning semantically relevant, real-world locations to documents opens new possibilities to perform geographic information retrieval. We propose a novel approach to automatically determine the latitude-longitude coordinates of appropriate Wikipedia articles with high accuracy, leveraging both text and metadata in the corpus. By examining articles whose base-truth coordinates are known, we show that our method attains a substantial improvement over state of the art works. We subsequently demonstrate how our approach could yield two benefits: (1) detecting significant geolocation errors in Wikipedia; and (2) proposing approximated coordinates for hundreds of thousands of articles which are not traditionally considered to be locations (such as events, ideas or people), opening new possibilities for conceptual geographic retrievals over Wikipedia.

Traditional query answering returns all answers T to a given query. When T is large, the user may be interested in viewing only a smaller subset S of T. Previous work has focused on finding subsets S that are diverse, i.e., such that all items s,s' in S are very different one from another. This paper focuses on a complementary problem, namely finding subsets that are highly representative of the entire set of query results.

We focus on summarizing hierarchical data by adapting the well-known notion of end biased-histograms to trees. Over relational data, such histograms have been well-studied, as they have a good balance between accuracy and space requirements. Extending histograms to tree data is a non-trivial problem, due to the need to preserve and leverage structure in the output. We develop a fast greedy algorithm, and a polynomial algorithm that finds provably optimal hierarchical end-biased histograms. Preliminary experimentation demonstrates that our histograms work well in practice.

We study the problem of deriving geolocations for Wikipedia pages. To this end, we introduce a general four-step process to location derivation, and consider different instantiations of this process, leveraging both textual and categorical data. Extensive experimentation shows that our methods provide good precision-recall trade-offs and improvements over text-only methods. Hence, our system can be used to augment the geographic information of Wikipedia, and to enable more effective geographic information retrieval.

Maximal clique enumeration is a well-studied problem due to its many applications. We present a new algorithm for this problem that enumerates maximal cliques in a diverse ordering. The main idea behind our approach is to adapt the classic Bron-Kerbosch (BK) algorithm by, conceptually, jumping between different nodes in the execution tree. Special care is taken to ensure that (1) each maximal clique is created precisely once, (2) the theoretical runtime remains the same as in the BK algorithm and (3) memory requirements remain reasonable. Experimental results show that we indeed achieve our goals, and moreover, that the cliques are enumerated in a diverse order.

A key difference between using blockchains to store data and centrally controlled databases is that transactions are accepted to a blockchain via a consensus mechanism, and not by a controlling central party. Hence, once a user has issued a transaction, she cannot be certain if it will be accepted. Moreover, a yet unaccepted transaction cannot be retracted by the user, and may (or may not) be appended to the blockchain at any point in the future. This causes difficulties as the user may wish to formulate new transactions based on the knowledge of which previous transactions will be accepted. Yet this knowledge is inherently uncertain. We introduce a formal abstraction for blockchains as a data storage layer that underlies a database. The main issue that we tackle is the need to reason about possible worlds, due to the uncertainty in transaction appending. In particular, we consider the theoretical complexity of determining whether it is possible for a denial constraint to be contradicted, given the current state of the blockchain, pending transactions, and integrity constraints on blockchain data. We then present practical algorithms for this problem that work well in practice.

The weighted set cover problem is defined over a universe U of elements, and a set S of subsets of U, each of which is associated with a weight. The goal is then to find a subset C of S that collectively covers U, while having minimal weight. The decision version of this well-known problem is NP-complete, but approximation algorithms have been presented that are guaranteed to find a θS-approximation of the optimal solution, where θSis the harmonic sum of the size of the largest set in S. Finding minimal weight set covers is an important problem, used, e.g., in facility location, team formation and transaction summarization. This paper studies the enumeration version of this problem. Thus, we present an algorithm that enumerates all minimal weight set covers in polynomial delay (i.e., with polynomial time between results) in θS-approximate order. We also present a variant of this algorithm in order to enumerate non-redundant set covers in θS-approximate order. Experimental results show that our algorithms run well in practice over both real and synthetic data.

This paper investigates the problem of reverse engineering, i.e., learning, select-project-join (SPJ) queries from a user-provided example set, containing positive and negative tuples. The goal is then to determine whether there exists a query returning all the positive tuples, but none of the negative tuples, and furthermore, to find such a query, if it exists. These are called the satisfiability and learning problems, respectively. The ability to solve these problems is an important step in simplifying the querying process for non-expert users.

When crowdsourcing to achieve some goal, or to gather information, there is a distinct advantage to choosing a diverse team of users. Past research has shown the advantages of diversity in the workplace, as team members bring different perspectives and points of view. Similarly, when choosing users from a crowd, user diversity must be taken into consideration. This paper studies the diverse team formation problem. More precisely, we are given a set of required skills, as wells as a large set of people, each of who has some subset of the skills. The goal is to form a team satisfying the skills, that is also diverse, as is reflected by differences in the characteristics of team members (e.g., gender, race, country of residence, economic bracket).

Social networks are fascinating and valuable datasets, which can be leveraged to better understand society, and to make inter-personal choices. This tutorial explores the fundamental issues that arise when storing and querying social data. The discussion is divided into three main parts. First, we consider some of the key computational problems that arise over the social graph structure, such as node centrality, link prediction, community detection and information diffusion. Second, we consider algorithmic challenges that leverage both the textual content and the graph structure of a social network, e.g., social search and querying, and team formation. Finally, we consider critical aspects of implementing a social network database management system, and discuss existing systems. In this tutorial, we also point out gaps between the state-of-the-art and desired features of a data management system for social networking, and discuss open research challenges.

This article investigates the problem of learning tree patterns that return nodes with a given set of labels, from example graphs provided by the user. Example graphs are annotated by the user as being either positive or negative . The goal is then to determine whether there exists a tree pattern returning tuples of nodes with the given labels in each of the positive examples, but in none of the negative examples, and furthermore, to find one such pattern if it exists. These are called the satisfiability and learning problems, respectively. This article thoroughly investigates the satisfiability and learning problems in a variety of settings. In particular, we consider example sets that (1) may contain only positive examples, or both positive and negative examples, (2) may contain directed or undirected graphs, and (3) may have multiple occurrences of labels or be uniquely labeled (to some degree). In addition, we consider tree patterns of different types that can allow, or prohibit, wildcard labeled nodes and descendant edges. We also consider two different semantics for mapping tree patterns to graphs. The complexity of satisfiability is determined for the different combinations of settings. For cases in which satisfiability is polynomial, it is also shown that learning is polynomial. (This is nontrivial as satisfying patterns may be exponential in size.) Finally, the minimal learning problem, that is, that of finding a minimal-sized satisfying pattern, is studied for cases in which satisfiability is polynomial.

Link prediction functions are important tools that are used to predict the evolution of a network, to locate hidden or surprising links, and to recommend new connections that should be formed. Multiple link prediction functions have been developed in the past. However, their evaluation has mostly been based onexperimental work, which has shown that the quality of a link prediction function varies significantly depending on the input domain. There is currently very little understanding of why and how a specific link prediction function works well for a particular domain. The underlying foundations of a link prediction function are often left informal---each function contains implicit assumptions about the dynamics of link formation, and about structural properties that result from these dynamics. We draw upon the motivation used in characterizations of ranking algorithms, as well as other celebrated results from social choice, and present an axiomatic basis for link prediction. This approach seeks to deconstruct each function into basic axioms, or properties, that make explicit its underlying assumptions. Our framework uses ``property templates'' that can be considered as general choices made by a function designer, such as what score is assigned to a 2-vertex graph, which vertices are irrelevant to the score, how removing edges or contracting vertices affects the score, and more. Using this framework, we fully characterize four well known link prediction functions and show that they are in fact derived from different variants of a single basic set of property templates.

The ability to accurately predict recipients of an email, while it is being composed, is of great practical importance for two reasons. First, prediction of recipients allows for effective "auto-complete" of this field, thereby improving user experience and reducing the overhead of manual typing of the recipient. Second, this capability allows the system to alert the user when she has typed unlikely recipients. Such alerts can help avoid human error that might result in forgetting relevant recipients, or, even worse, disclosure of personal or classified information.

This paper investigates the problem of learning tree patterns that return nodes with a given set of labels, from example graphs provided by the user. Example graphs are annotated by the user as being either positive or negative. The goal is then to determine whether there exists a tree pattern returning tuples of nodes with the given labels in each of the positive examples, but in none of the negative examples, and, furthermore, to find one such pattern if it exists. These are called the satisfiability and learning problems, respectively. This paper thoroughly investigates the satisfiability and learning problems in a variety of settings. In particular, we consider example sets that (1) may contain only positive examples, or both positive and negative examples, (2) may contain directed or undirected graphs, and (3) may have multiple occurrences of labels or be uniquely labeled (to some degree). In addition, we consider tree patterns of different types that can allow, or prohibit, wildcard labeled nodes and descendant edges. We also consider two different semantics for mapping tree patterns to graphs. The complexity of satisfiability is determined for the different combinations of settings. For cases in which satisfiability is polynomial, it is also shown that learning is polynomial (This is non-trivial as satisfying patterns may be exponential in size). Finally, the minimal learning problem, i.e., that of finding a minimal-sized satisfying pattern, is studied for cases in which satisfiability is polynomial.

The problem of enumerating (i.e., generating) all maximal cliques in a graph has received extensive treatment, due to the plethora of applications in various areas such as data mining, bioinformatics, network analysis and community detection. However, requiring the enumerated subgraphs to be full cliques is too restrictive in common real-life scenarios where "almost cliques" are equally useful. Hence, the notion of a k-plex, a clique relaxation that allows every node to be "missing" k neighbors, has been introduced. But this seemingly minor relaxation casts existing algorithms for clique enumeration inapplicable, for inherent reasons. This paper presents the first provably efficient algorithms, both for enumerating the maximal k-plexes and for enumerating the maximal connected k-plexes. Our algorithms run in polynomial delay for a constant k and incremental FPT delay when k is a parameter. The importance of such algorithms is in the areas mentioned above, as well as in new applications. Extensive experimentation over both real and synthetic datasets shows the efficiency of our algorithms, and their scalability with respect to graph size, density and choice of k, as well as their clear superiority over the state-of-the-art.

Determining similarity between trees is an important problem in a variety of areas. The subtree similarity-search problem is that of finding, given a tree Q and a large set of trees Γ = {T1; ...; Tn}, the subtrees of trees among Γ that are most similar to Q. Similarity is defined using some tree distance function. While subtree similarity-search has been studied in the past, solutions mostly focused on specific tree distance functions, and were usually applicable only to ordered trees. This paper presents an efficient new algorithm that solves the subtree similarity-search problem, and is compatible with a wide family of tree distance functions (for both ordered and unordered trees). Extensive experimentation confirms the efficiency and scalability of the algorithm, which displays consistently good runtime even for large queries and datasets.

Formulating an XPath query over an XML document is a difficult chore for a non-expert user. This paper introduces a novel approach to ease the querying process. Instead of specifying a query, the user simply marks positive examples χ+ of nodes that fit her information need. She may also mark negative examples χ− of undesirable nodes. A deductive method, to suggest additional nodes that will interest the user, is developed in this paper.

Given a tree Q and a large set of trees T = {T1,...,Tn}, the subtree similarity-search problem is that of finding the subtrees of trees among T that are most similar to Q, using the tree edit distance metric. Determining similarity using tree edit distance has been proven useful in a variety of application areas. While subtree similarity-search has been studied in the past, solutions required traversal of all of T, which poses a severe bottleneck in processing time, as T grows larger. This paper proposes the first index structure for subtree similarity-search, provided that the unit cost function is used. Extensive experimentation and comparison to previous work shows the huge improvement gained when using the proposed index structure and processing algorithm.

When a query is evaluated under bag semantics, each answer is returned as many times as it has derivations. Bag semantics has long been recognized as important, especially when aggregation functions will be applied to query results. This article is the first to focus on bag semantics for tree pattern queries. In particular, the problem of bag equivalence of a large class of tree pattern queries (which can be used to model XPath) is explored. The queries can contain unions, branching, label wildcards, the vertical child and descendant axes, the horizontal following and following-sibling axes, as well as positional (i.e., first and last) axes. Equivalence characterizations are provided, and their complexity is analyzed. As the descendant axis involves a recursive relationship, this article is also the first to address bag equivalence over recursive queries, in any setting.

Stochastic context-free grammars (SCFGs) have long been recognized as useful for a large variety of tasks including natural language processing, morphological parsing, speech recognition, information extraction, Web-page wrapping and even analysis of RNA. A string and an SCFG jointly represent a probabilistic interpretation of the meaning of the string, in the form of a (possibly infinite) probability space of parse trees. The problem of evaluating a query over this probability space is considered under the conventional semantics of querying a probabilistic database. For general SCFGs, extremely simple queries may have results that include irrational probabilities. But, for a large subclass of SCFGs (that includes all the standard studied subclasses of SCFGs) and the language of tree-pattern queries with projection (and child/descendant edges), it is shown that query results have rational probabilities with a polynomial-size bit representation and, more importantly, an efficient query-evaluation algorithm is presented.

When a query is evaluated under bag semantics, each answer is returned as many times as it has derivations. Bag semantics has long been recognized as important, especially when aggregation functions will be applied to query results. This paper is the first to focus on bag semantics for XPath queries. In particular, the problem of bag-equivalence of a large class of XPath queries (modeled as tree patterns) is explored. The queries can contain unions, branching, label wildcards, the vertical child and descendant axes, the horizontal following, following-sibling and immediately-following sibling axes, as well as positional (i.e., first and last) axes. Equivalence characterizations are provided, and their complexity is analyzed. As the descendent axis involves a recursive relationship, this paper is also the first to address bag equivalence over recursive queries, in any setting.

Preferences over results of an XML query are of two distinct flavors. First, the user may prefer results which contain desired values, e.g., lower prices, favorite foods, higher ratings. Second, the user may prefer results with a certain structure, e.g., existence of a "discount" node, existence of an edge (and not only a path) between "departure" and "arrival" nodes. The first type of preference has been studied extensively over relational data, using skyline semantics, but has barely been considered for XML. The second type of preference has been studied for XML in the context of inexact querying, using scoring functions to rank results. This paper presents a query language for XML that incorporates both value-based and structural desires. Skyline semantics is used to determine optimal results. Algorithms for query evaluation under skyline semantics are presented and experimentation proves efficiency. The paper is novel in three aspects. First, it considers skyline querying over XML data values, and not over values in a relational database. Second, it presents a method for inexact querying of the structure of XML that is based on computing a skyline, instead of using scoring functions. Third, it combines both types of user preference into a single language. These facets join together to yield a versatile language for flexible querying of XML.

Tree automata (specifically, bottom-up and unranked) form a powerful tool for querying and maintaining validity of XML documents. XML with uncertain data can be modeled as a probability space of labeled trees, and that space is often represented by a tree with distributional nodes. This paper investigates the problem of evaluating a tree automaton over such a representation, where the goal is to compute the probability that the automaton accepts a random possible world. This problem is generally intractable, but for the case where the tree automaton is deterministic (and its transitions are defined by deterministic string automata), an efficient algorithm is presented. The paper discusses the applications of this result, including the ability to sample and to evaluate queries (e.g., in monadic second-order logic) while requiring a-priori conformance to a schema (e.g., DTD). XML schemas also include attribute constraints, and the complexity of key, foreign-key and inclusion constraints are studied in the context of probabilistic XML. Finally, the paper discusses the generalization of the results to an extended data model, where distributional nodes can repeatedly sample the same subtree, thereby adding another exponent to the size of the probability space.

Constraints are important, not only for maintaining data integrity, but also because they capture natural probabilistic dependencies among data items. A probabilistic XML database (PXDB) is the probability subspace comprising the instances of a p-document that satisfy a set of constraints. In contrast to existing models that can express probabilistic dependencies, it is shown that query evaluation is tractable in PXDBs. The problems of sampling and determining well-definedness (i.e., whether the aforesaid subspace is nonempty) are also tractable. Furthermore, queries and constraints can include the aggregate functions count, max, min, and ratio. Finally, this approach can be easily extended to allow a probabilistic interpretation of constraints.

Constraints are important not just for maintaining data integrity, but also because they capture natural probabilistic dependencies among data items. A probabilistic XML database (PXDB) is the probability sub-space comprising the instances of a p-document that satisfy a set of constraints. In contrast to existing models that can express probabilistic dependencies, it is shown that query evaluation is tractable in PXDBs. The problems of sampling and determining well-definedness (i.e., whether the above subspace is nonempty) are also tractable. Furthermore, queries and constraints can include the aggregate functions count, max, min and ratio. Finally, this approach can be easily extended to allow a probabilistic interpretation of constraints.

This paper presents a framework for automatically generating structural XML documents. The user provides a target DTD and an example of an XML document, called a Generate-XML-By-Example Document , or a GxBE document , for short. GxBE documents use a natural declarative syntax, which includes XPath expressions and the function count. Using GxBE documents, users can express important global and local characteristics for the desired target documents, and can require satisfaction of XPath expressions from a given workload. This paper explores the problem of efficiently generating a document that satisfies a given DTD and GxBE document.

Users tend to store huge amounts of files, of various formats, on their personal computers. As a result, finding a specific, desired file within the file system is a challenging task. This article addresses thedesktop searchproblem by considering various techniques for ranking results of a search query over the file system. First, basic ranking techniques, which are based on various file features (e.g., file name, access date, file size, etc.), are considered and their effectiveness is empirically analyzed. Next, two learning-based ranking schemes are presented, and are shown to be significantly more effective than the basic ranking methods. Finally, a novel ranking technique, based on query selectiveness, is considered for use during the cold-start period of the system. This method is also shown to be empirically effective, even though it does not involve any learning.

It has been observed that queries over XML data sources are often unsatisfiable. Unsatisfiability may stem from several different sources, e.g., the user may be insufficiently familiar with the labels appearing the documents, or may not be intimately aware of the hierarchical structure of the documents. This difficulty may be compounded by the fact that errors in query formulation lead to an empty answer, and not to some sort of compilation error.

This paper addresses the desktop search problem by considering varioustechniques for ranking results of a search query over thefile system. First, basic ranking techniques, which are based ona single file feature (e.g., file name, file content, access date, etc.)are considered. Next, two learning-based ranking schemes are presented, and are shown to be significantly more effective than the basic ranking methods. Finally, a novel ranking technique, based on query selectiveness is considered,for use during the cold-start period of the system. This method isalso shown to be empirically effective, even though it does notinvolve any learning.

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 query equivalence problem has been studied extensively for set-semantics and, more recently, for bag-set semantics. However, SQL queries often combine set and bag-set semantics. For example, an SQL query that returns a multiset of elements may call a subquery or view that returns a set of elements. As another example, in SQL one can compute a multiset-union of queries, each of which returns a set of answers. This paper presents combined semantics, which formally models query evaluation combining set and bag-set semantics. The equivalence problem for queries evaluated under combined semantics is studied. A sufficient condition for equivalence is presented. For several important common classes of queries necessary and sufficient conditions for equivalence are presented.

The ability to create user-defined aggregate functions (UDAs) is rapidly becoming a standard feature in relational database systems. Therefore, problems such as query optimization, query rewriting and view maintenance must take into account queries (or views) with UDAs. There is a wealth of research on these problems for queries with general aggregate functions. Unfortunately, there is a mismatch between the manner in which UDAs are created, and the information that the database system requires in order to apply previous research.The purpose of this paper is to explore this mismatch and to bridge the gap between theory and practice, thereby enabling UDAs to become first-class citizens within the database. Specifically, we consider query optimization, query rewriting and view maintenance for queries with UDAs. For each of these problems we first survey previous results and explore the mismatch between theory and practice. We then present theoretical and practical insights that can be combined to derive a coherent framework for defining UDAs within a database system.

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.

A framework for describing semantic relationships among nodes in XML documents is presented. In contrast to earlier work, the XML documents may have ID references (i.e., they correspond to graphs and not just trees). A specific interconnection semantics in this framework can be defined explicitly or derived automatically. The main advantage of interconnection semantics is the ability to pose queries on XML data in the style of keyword search. Several methods for automatically deriving interconnection semantics are presented. The complexity of the evaluation and the satisfiability problems under the derived semantics is analyzed. For many important cases, the complexity is tractable and hence, the proposed interconnection semantics can be efficiently applied to real-world XML documents.

The full disjunction is a variation of the join operator that maximally combines tuples from connected relations, while preserving all information in the relations. The full disjunction can be seen as a natural extension of the binary outerjoin operator to an arbitrary number of relations and is a useful operator for information integration. This paper presents the algorithm INCREMENTALFD for computing the full disjunction of a set of relations. INCREMENTALFD improves upon previous algorithms for computing the full disjunction in three ways. First, it has a lower total run-time when computing the full result and a lower runtime when computing only k tuples of the result, for any constant k. Second, for a natural class of ranking functions, INCREMENTALFD returns tuples in ranking order. Third, INCREMENTALFD can be adapted to have a block-based execution, instead of a tuple-based execution.

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.

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.