Search

We study the expressive power of the Lara language – a recently proposed unified model for expressing relational and linear algebra operations – both in terms of traditional database query languages and some analytic tasks often performed in machine learning pipelines. Since Lara is parameterized by a set of user-defined functions which allow to transform values in tables, known as extension functions , the exact expressive power of the language depends on how these functions are defined. We start by showing Lara to be expressive complete with respect to a syntactic fragment of relational algebra with aggregation (under the mild assumption that extension functions in Lara can cope with traditional relational algebra operations such as selection and renaming). We then look further into the expressiveness of Lara based on different classes of extension functions, and distinguish two main cases depending on the level of genericity that queries are enforced to satisfy. Under strong genericity assumptions the language cannot express matrix convolution, a very important operation in current machine learning pipelines. This language is also local, and thus cannot express operations such as matrix inverse that exhibit a recursive behavior. For expressing convolution, one can relax the genericity requirement by adding an underlying linear order on the domain. This, however, destroys locality and turns the expressive power of the language much more difficult to understand. In particular, although under complexity assumptions some versions of the resulting language can still not express matrix inverse, a proof of this fact without such assumptions seems challenging to obtain. [ABSTRACT FROM AUTHOR]

Abstract The Weak Dominance Drawing problem can be defined as follows: given a directed acyclic graph G , find two topological sorts, t X and t Y , minimizing the size of the intersection between them. The intersection of two topological sorts is defined as the set of ordered pair of vertices (u , v) such that t X (u) < t X (v) and t Y (u) < t Y (v). In this work we consider a variation of this problem, that we call One-Sided Weak Dominance Drawing , in which one of the topological sorts is given as input and we must find another topological sort minimizing the intersection set with the given one. This problem has been considered in the literature and its applications include index generation of competitive algorithms for reachability queries on very large graphs. In this paper we formalize the problem, describe one of its applications, show how the problem is currently tackled in the literature, prove that its decision version is NP-complete and determine a primal bound for it as a function of the dimension of G. [ABSTRACT FROM AUTHOR]

Abstract In this paper, the problem of tree size reduction with guarantee of preserving distinguishability is studied. Given a query q and a tree T , evaluating q on T will output q (T) which is a set of nodes of T. Given two nodes a and b in T , they are said to be distinguished by some query q in T , iff exactly one of them belongs to q (T). Then, given a tree T , a query class L , and two disjoint node sets A and B of T , a subtree T ′ of T satisfies the condition of preserving distinguishability of T , iff (1) T ′ contains all nodes in A ∪ B , (2) for any node pair (a , b) ∈ A × B , if a and b can be distinguished by some query in L in T , they can also be distinguished by some query (not necessarily the same one) in L in T ′ , and (3) for any node pair (a , b) ∈ A × B and a query q ∈ L , if a and b can be distinguished by q in T ′ , they can also be distinguished by q in T. The tree size reduction problem considered by this paper is to determine whether there is a small enough subtree T ′ of T , such that for query class L and node sets A and B , T ′ preserves the distinguishability of T. In this paper, as an initial attempt of investigating this problem, fixing L to be a specific part of tree pattern queries which is an important practical query language on trees, the tree size reduction problem is shown to be NP- complete. [ABSTRACT FROM AUTHOR]

Abstract Let D = { T 1 , T 2 , … , T D } be a collection of D documents having n characters in total. Given two patterns P and Q , and an integer k > 0 , we consider the following queries. • top - k forbidden pattern query: Among all documents containing P , but not Q , report the k documents most relevant to P. • top - k two pattern query: Among all documents that contain both P and Q , report the k documents most relevant to P. For the above two queries, we provide a linear space index with O (| P | + | Q | + n k) query time, under some standard relevance functions such as PageRank and TermFrequency. The document listing version of the above two problems asks to report all t documents that either contain P , but not Q , or contain both P and Q , depending on the query type. As a corollary of the top- k result, we obtain a linear space and O (| P | + | Q | + n t) query time solution for the document listing problems. We conjecture that any significant improvement over these results is highly unlikely. We also consider the scenario when the query consists of more than two patterns. Finally, we present space-efficient indexes for these problems. [ABSTRACT FROM AUTHOR]

We give a new deterministic algorithm that non-adaptively learns a hidden hypergraph from edge-detecting queries. All previous non-adaptive algorithms either run in exponential time or have non-optimal query complexity. We give the first polynomial time non-adaptive learning algorithm for learning hypergraphs that asks an almost optimal number of queries. [ABSTRACT FROM AUTHOR]

The present contribution advances an abstract notion of hybrid logic by supplementing the definition of institution with an additional structure to extract frames. The foundation of logic programming is set in the general framework proposed by defining the basic concepts such as Horn clause, query and solution, and proving fundamental results such as the existence of initial model of Horn clauses and Herbrand's theorem. The abstract results are then applied to hybrid logics with user-defined sharing, where the possible worlds share a common domain and the variables used for quantification are interpreted uniformly across the worlds. [ABSTRACT FROM AUTHOR]

Promoting declarative approaches in data mining is a long standing theme, the main idea being to simplify as much as possible the way data analysts interact with their data. This paper goes into this direction by proposing a well-founded logical query language, S a f e RL , allowing the expression of a wide variety of rules to be discovered against a database. By rules, we mean statements of the form “if …then …”, as defined in logics for “implications” between boolean variables. As a consequence, S a f e RL extends and generalizes functional dependencies to new and unexpected rules. We provide a query rewriting technique and a constructive proof of the main query equivalence theorem, leading to an efficient query processing technique. From S a f e RL , we have devised RQL, a user-friendly SQL-like query language. We have shown how a tight integration can be performed on top of any relational database management system. Every RQL query turns out to be seen as a query processing problem, instead of a particular rule mining problem. This approach has been implemented and experimented on sensor network data. A web prototype has been released and is freely available ( http://rql.insa-lyon.fr ). Data analysts can upload a sample of their data, write their own RQL queries and get answers to know whether or not a rule holds (if not, a counterexample from the database is displayed) and much more. [ABSTRACT FROM AUTHOR]

Given a matrix of size N , two dimensional range minimum queries (2D-RMQs) ask for the position of the minimum element in a rectangular range within the matrix. We study trade-offs between the query time and the additional space used by indexing data structures that support 2D-RMQs. Using a novel technique—the discrepancy properties of Fibonacci lattices—we give an indexing data structure for 2D-RMQs that uses O ( N / c ) bits additional space with O ( c log ⁡ c ( log ⁡ log ⁡ c ) 2 ) query time, for any parameter c , 4 ≤ c ≤ N . Also, when the entries of the input matrix are from { 0 , 1 } , we show that the query time can be improved to O ( c log ⁡ c ) with the same space usage. [ABSTRACT FROM AUTHOR]

The test specification language FQL describes relevant test goals as regular expressions over program locations, such that each matching test case has an execution path matching this expression. To specify not only test goals but entire suites, FQL describes families of related test goals by regular expressions over extended alphabets: Herein, each symbol corresponds to a regular expression over program locations, and thus, a word in an FQL expression corresponds to a regular expression describing a single test goal. In this paper we provide a systematic foundation for FQL test specifications, which are in fact rational sets of regular languages (RSRLs). To address practically relevant problems like query optimization, we tackle open questions about RSRLs: We settle closure properties of general and finite RSRLs under common set theoretic operations. We also prove complexity results for checking equivalence and inclusion of star-free RSRLs, and for deciding whether a regular language is a member of a general or star-free RSRL. [ABSTRACT FROM AUTHOR]

Abstract: We study the power of two models of faulty teachers in Valiant’s PAC learning model and Angluin’s exact learning model. The first model we consider is learning from an incomplete membership oracle introduced by Angluin and Slonim [D. Angluin, D.K. Slonim, Randomly fallible teachers: Learning monotone DNF with an incomplete membership oracle, Machine Learning 14 (1) (1994) 7–26]. In this model, the answers to a random subset of the learner’s membership queries may be missing. The second model we consider is random persistent classification noise in membership queries introduced by Goldman, Kearns and Schapire [S. Goldman, M. Kearns, R. Schapire, Exact identification of read-once formulas using fixed points of amplification functions, SIAM Journal on Computing 22 (4) (1993) 705–726]. In this model, the answers to a random subset of the learner’s membership queries are flipped. We show that in both the PAC and the exact learning models the incomplete membership oracle is strictly stronger than the noisy membership oracle under the assumption that the problem of PAC learning parities with random classification noise is intractable. We also show that under the standard cryptographic assumptions the incomplete membership oracle is strictly weaker than the perfect membership oracle. This generalizes the result of Simon [H. Simon, How many missing answers can be tolerated by query learners? Theory of Computing Systems 37 (1) (2004) 77–94] and resolves an open question of Bshouty and Eiron [N. Bshouty, N. Eiron, Learning monotone DNF from a teacher that almost does not answer membership queries, Journal of Machine Learning Research 3 (2002) 49–57]. [Copyright &y& Elsevier]

In language learning, strong relationships between Gold-style models and query models have recently been observed: in some quite general setting Gold-style learners can be replaced by query learners and vice versa, without loss of learning capabilities. These ‘equalities’ hold in the context of learning indexable classes of recursive languages. Former studies on Gold-style learning of such indexable classes have shown that, in many settings, the enumerability of the target class and the recursiveness of its languages are crucial for learnability. Moreover, studying query learning, non-indexable classes have been mainly neglected up to now. So it is conceivable that the recently observed relations between Gold-style and query learning are not due to common structures in the learning processes in both models, but rather to the enumerability of the target classes or the recursiveness of their languages. In this paper, the analysis is lifted onto the context of learning arbitrary classes of recursively enumerable languages. Still, strong relationships between the approaches of Gold-style and query learning are proven, but there are significant changes to the former results. Though in many cases learners of one type can still be replaced by learners of the other type, in general this does not remain valid vice versa. All results hold even for learning classes of recursive languages, which indicates that the recursiveness of the languages is not crucial for the former ‘equality’ results. Thus we analyze how constraints on the algorithmic structure of the target class affect the relations between two approaches to language learning. [Copyright &y& Elsevier]

Abstract: We study the problem of rewriting queries using views in the presence of access patterns, integrity constraints, disjunction and negation. We provide asymptotically optimal algorithms for (1) finding minimally containing and (2) maximally contained rewritings respecting the access patterns (which we call executable) and for (3) deciding whether an exact executable rewriting exists. We show that rewriting queries using views in this case reduces (a) to rewriting queries with access patterns and constraints without views and also (b) to rewriting queries using views under constraints without access patterns. We show how to solve (a) directly and how to reduce (b) to rewriting queries under constraints only (semantic optimization). These reductions provide two separate routes to a unified solution for problems 1, 2 and 3 based on an extension of the relational chase theory to queries and constraints with disjunction and negation. We also handle equality and arithmetic comparisons. We also show that in an information integration setting, maximally contained rewritings are given by the certain answers (under the usual semantics) for a set of constraints derived from the binding patterns. That is, except for defining the appropriate constraints, binding patterns do not need special treatment. Finally, we show that if there is an exact executable rewriting, there is an executable rewriting which is a union of conjunctive queries with negation. [Copyright &y& Elsevier]

Abstract: As a result of the extensive research in view-based query processing, three notions have been identified as fundamental, namely rewriting, answering, and losslessness. Answering amounts to computing the tuples satisfying the query in all databases consistent with the views. Rewriting consists in first reformulating the query in terms of the views and then evaluating the rewriting over the view extensions. Losslessness holds if we can answer the query by solely relying on the content of the views. While the mutual relationship between these three notions is easy to identify in the case of conjunctive queries, the terrain of notions gets considerably more complicated going beyond such a query class. In this paper, we revisit the notions of answering, rewriting, and losslessness and clarify their relationship in the setting of semistructured databases, and in particular for the basic query class in this setting, i.e., two-way regular path queries. Our first result is a clean explanation of the relationship between answering and rewriting, in which we characterize rewriting as a “linear approximation” of query answering. We show that applying this linear approximation to the constraint-satisfaction framework yields an elegant automata-theoretic approach to query rewriting. As for losslessness, we show that there are indeed two distinct interpretations for this notion, namely with respect to answering, and with respect to rewriting. We also show that the constraint-theoretic approach and the automata-theoretic approach can be combined to give algorithmic characterization of the various facets of losslessness. Finally, we deal with the problem of coping with loss, by considering mechanisms aimed at explaining lossiness to the user. [Copyright &y& Elsevier]

Abstract: In recent years wavelets were shown to be effective data synopses. We are concerned with the problem of finding efficiently wavelet synopses for massive data sets, in situations where information about query workload is available. We present linear time, I/O optimal algorithms for building optimal workload-based wavelet synopses for point queries. The synopses are based on a novel construction of weighted inner products and use weighted wavelets that are adapted to those products. The synopses are optimal in the sense that the subset of retained coefficients is the best possible for the bases in use with respect to either the mean-squared absolute or relative errors. For the latter, this is the first optimal wavelet synopsis even for the regular, non-workload-based case. Experimental results demonstrate the advantage obtained by the new optimal wavelet synopses. [Copyright &y& Elsevier]

Abstract: The most natural and perhaps most frequently used method for testing membership of an individual tuple in a conjunctive query is based on searching trees of partial solutions, or search-trees. We investigate the question of evaluating conjunctive queries with a time-bound guarantee that is measured as a function of the size of the optimal search-tree. We provide an algorithm that, given a database , a conjunctive query , and a tuple , tests whether holds in in time bounded by a polynomial in and , where is the size of the domain of the database, is the number of bound variables of the conjunctive query, is the size of the optimal search-tree, and is the maximum arity of the relations. In many cases of interest, this bound is significantly smaller than the bound provided by the naive search-tree method. Moreover, our algorithm has the advantage of guaranteeing the bound for any given conjunctive query. In particular, it guarantees the bound for queries that admit an equivalent form that is much easier to evaluate, even when finding such a form is an NP-hard task. Concrete examples include the conjunctive queries that can be non-trivially folded into a conjunctive query of bounded size or bounded treewidth. All our results translate to the context of constraint-satisfaction problems via the well-publicized correspondence between both frameworks. [Copyright &y& Elsevier]

Abstract: We propose and investigate from the algorithmic standpoint a novel form of fuzzy query called approximately dominating representatives or ADRs. The ADRs of a multidimensional point set consist of a few points guaranteed to contain an approximate optimum of any monotone Lipschitz continuous combining function of the dimensions. ADRs can be computed by appropriately post-processing Pareto, or “skyline”, queries [Kian-Lee Tan, Pin-Kwang Eng, Beng Chin Ooi, Efficient progressive skyline computation, in: VLDB, 2001, pp. 301–310; Wolf-Tilo Balke, Ulrich Güntzer, Jason Xin Zheng, Efficient distributed skylining for web information systems, in: EDBT, 2004. ]. We show that the problem of minimizing the number of points returned, for a user-specified desired approximation, can be solved in polynomial time in two dimensions; for three and more it is NP-hard but has a polynomial-time logarithmic approximation. Finally, we present a polynomial-time, constant factor approximation algorithm for three dimensions. [Copyright &y& Elsevier]

Abstract: We consider the problem of answering queries using views, where queries and views are conjunctive queries with arithmetic comparisons over dense orders. Previous work only considered limited variants of this problem, without giving a complete solution. We first show that obtaining equivalent rewritings for conjunctive queries with arithmetic comparisons is decidable. Then, we consider the problem of finding maximally contained rewritings (MCRs) where the decidability proof does not carry over. We investigate two special cases of this problem where the query uses only semi-interval comparisons. In both cases decidability of finding MCRs depends on the query containment test. First, we address the case where the homomorphism property holds in testing query containment. In this case decidability is easy to prove but developing an efficient algorithm is not trivial. We develop such an algorithm and prove that it is sound and complete. This algorithm applies in many cases where the query uses only left (or right) semi-interval comparisons. Then, we develop a new query containment test for the case where the containing query uses both left and right semi-interval comparisons but with only one left (or right) semi-interval subgoal. Based on this test, we show how to produce an MCR which is a Datalog query with arithmetic comparisons. The containment test that we develop obtains a result of independent interest. It finds another special case where query containment in the presence of arithmetic comparisons can be tested in nondeterministic polynomial time. [Copyright &y& Elsevier]

Abstract: We define a boolean complete dialect of description logic called that can be used to reason about structural equality in semistructured ordered data in the presence of document type definitions. This application depends on the novel ability of to express functional dependencies over possibly infinite sets of feature paths defined by regular languages. We also present a decision procedure for the associated logical implication problem. The procedure underlies a mapping of such problems to satisfiability problems of . [Copyright &y& Elsevier]

Abstract: We investigate the typechecking problem for XML transformations: statically verifying that every answer to a transformation conforms to a given output schema, for inputs satisfying a given input schema. As typechecking quickly turns undecidable for query languages capable of testing equality of data values, we return to the limited framework where we abstract XML documents as labeled ordered trees. We focus on simple top-down recursive transformations motivated by XSLT and structural recursion on trees. We parameterize the problem by several restrictions on the transformations (deleting, non-deleting, bounded width) and consider both tree automata and DTDs as input and output schemas. The complexity of the typechecking problems in this scenario ranges from to . [Copyright &y& Elsevier]

Abstract: The formalism of constraint databases, in which possibly infinite data sets are described by Boolean combinations of polynomial inequality and equality constraints, has its main application area in spatial databases. The standard query language for polynomial constraint databases is first-order logic over the reals. Because of the limited expressive power of this logic with respect to queries that are important in spatial data base applications, various extensions have been introduced. We study extensions of first-order logic with different types of transitive-closure operators and we are in particular interested in deciding the termination of the evaluation of queries expressible in these transitive-closure logics. It turns out that termination is undecidable in general. However, we show that the termination of the transitive closure of a continuous function graph in the two-dimensional plane, viewed as a binary relation over the reals, is decidable, and even expressible in first-order logic over the reals. Based on this result, we identify a particular transitive-closure logic for which termination of query evaluation is decidable and which is more expressive than first-order logic over the reals. Furthermore, we can define a guarded fragment in which exactly the terminating queries of this language are expressible. [Copyright &y& Elsevier]

We introduce a formalism to represent and analyze protein–protein and protein–DNA interaction networks. We illustrate the expressivity of this language, by proposing a formal counterpart of Kohn''s compilation on the mammalian cell-cycle control. This effectively turns an otherwise static knowledge into a discrete transition system incorporating a qualitative description of the dynamics. We then propose to use the computation tree logic (CTL) as a query language for querying the possible behaviors of the system. We provide examples of biologically relevant queries expressed in CTL about the mammalian cell-cycle control and show the effectiveness of symbolic model checking tools to evaluate CTL queries in this context. [Copyright &y& Elsevier]

Active database systems enhance the functionality of traditional databases through the use of active rules or ‘triggers’. One of the principal analysis questions for such systems is that of termination—is it possible for the rules to recursively activate one another indefinitely, given an initial triggering event. In this paper, we study the decidability of the termination problem, our aim being to delimit the boundary between the decidable and the undecidable. We present results for two broad types of variations, variations in rule syntax and variations in meta level features. Within each of these, we identify members close to the boundary of (un)decidability and also look at the effect of combining members of each type. The maximal decidable class we present is capable of expressing some useful kinds of application requirements, such as checking and repairing inclusion constraints. The work is also interesting from a theoretical point of view, since the context is similar to the while query language and the dynamics gives an interesting contrast to Datalog with negation. [Copyright &y& Elsevier]

It is a folk result in database theory that SQL cannot express recursive queries such as reachability; in fact, a new construct was added to SQL3 to overcome this limitation. However, the evidence for this claim is usually given in the form of a reference to a proof that relational algebra cannot express such queries. SQL, on the other hand, in all its implementations has three features that fundamentally distinguish it from relational algebra: namely, grouping, arithmetic operations, and aggregation.In the past few years, most questions about the additional power provided by these features have been answered. This paper surveys those results, and presents new simple and self-contained proofs of the main results on the expressive power of SQL. Somewhat surprisingly, tiny differences in the language definition affect the results in a dramatic way: under some very natural assumptions, it can be proved that SQL cannot define recursive queries, no matter what aggregate functions and arithmetic operations are allowed. But relaxing these assumptions just a tiny bit makes the problem of proving expressivity bounds for SQL as hard as some long-standing open problems in complexity theory. [Copyright &y& Elsevier]

We define a new logic-based query language, called DAC, which is an extension of Datalog. A DAC(w(n),h(n))(b(n))-program consists of a family of Datalog programs Pn such that w(n),h(n),b(n) bound the width of rules, the number of rules, and the recursion depth of any Pn, respectively. We exhibit queries which are not Datalog expressible but are DAC expressible. We also prove non-expressiveness results for DAC and we infer various strict hierarchies obtained by allowing more rapidly growing functions on the bound parameters. [Copyright &y& Elsevier]