272 research outputs found
Learning Models over Relational Databases (Invited Talk)
No full textIn this talk, I will make the case for a first-principles approach to machine learning over relational databases that exploits recent development in database systems and theory.
The input to learning classification and regression models is defined by feature extraction queries over relational databases. The mainstream approach to learning over relational data is to materialize the training dataset, export it out of the database, and then learn over it using statistical software packages. These three steps are expensive and unnecessary. Instead, one can cast the machine learning problem as a database problem by decomposing the learning task into a batch of aggregates over the feature extraction query and by computing this batch over the input database.
The performance of this database-centric approach benefits tremendously from structural properties of the relational data and of the feature extraction query; such properties may be algebraic (semi-ring), combinatorial (hypertree width), or statistical (sampling). It also benefits from database systems techniques such as factorized query evaluation and query compilation. For a variety of models, including factorization machines, decision trees, and support vector machines, this approach may come with lower computational complexity than the materialization of the training dataset used by the mainstream approach. Recent results show that this translates to several orders-of-magnitude speed-up over state-of-the-art systems such as TensorFlow, R, Scikit-learn, and mlpack.
While these initial results are promising, there is much more awaiting to be discovered
LIPIcs, Volume 220, ICDT 2022, Complete Volume
No full textLIPIcs, Volume 220, ICDT 2022, Complete Volum
Front Matter, Table of Contents, Preface, Conference Organization
No full textFront Matter, Table of Contents, Preface, Conference Organizatio
Covers of Query Results
No full textWe introduce succinct lossless representations of query results called covers. They are subsets of the query results that correspond to minimal edge covers in the hypergraphs of these results.
We first study covers whose structures are given by fractional hypertree decompositions of join queries.
For any decomposition of a query, we give asymptotically tight size bounds for the covers of the query result over that decomposition and show that such covers can be computed in worst-case optimal time up to a logarithmic factor in the database size. For acyclic join queries, we can compute covers compositionally using query plans with a new operator called cover-join. The tuples in the query result can be enumerated from any of its covers with linearithmic pre-computation time and constant delay.
We then generalize covers from joins to functional aggregate queries that express a host of computational problems such as aggregate-join queries, in-database optimization, matrix chain multiplication, and inference in probabilistic graphical models
Marius Sala, Dan Munteanu, Valeria Ncagu, Tudora Sandru- Olteanu, El léxico indígena del español americano.
No full textMarius Sala, Dan Munteanu, Valeria Ncagu, Tudora Sandru- Olteanu, El léxico indígena del español americano.. In: Bulletin Hispanique, tome 81, n°3-4, 1979. pp. 357-366
Marius Sala, Dan Munteanu, Valeria Ncagu, Tudora Sandru- Olteanu, El léxico indígena del español americano.
No full textMarius Sala, Dan Munteanu, Valeria Ncagu, Tudora Sandru- Olteanu, El léxico indígena del español americano.. In: Bulletin Hispanique, tome 81, n°3-4, 1979. pp. 357-366
Boolean tensor decomposition for conjunctive queries with negation
No full textWe propose an approach for answering conjunctive queries with negation, where the negated relations have bounded degree. Its data complexity matches that of the InsideOut and PANDA algorithms for the positive subquery of the input query and is expressed in terms of the fractional hypertree width and the submodular width respectively. Its query complexity depends on the structure of the conjunction of negated relations; in general it is exponential in the number of join variables occurring in negated relations yet it becomes polynomial for several classes of queries. This approach relies on several contributions. We show how to rewrite queries with negation on bounded-degree relations into equivalent conjunctive queries with not-all-equal (NAE) predicates, which are a multi-dimensional analog of disequality (!=). We then generalize the known color-coding technique to conjunctions of NAE predicates and explain it via a Boolean tensor decomposition of conjunctions of NAE predicates. This decomposition can be achieved via a probabilistic construction that can be derandomized efficiently
Tractable Conjunctive Queries over Static and Dynamic Relations
No full textWe investigate the evaluation of conjunctive queries over static and dynamic relations. While static relations are given as input and do not change, dynamic relations are subject to inserts and deletes.
We characterise syntactically three classes of queries that admit constant update time and constant enumeration delay. We call such queries tractable. Depending on the class, the preprocessing time is linear, polynomial, or exponential (under data complexity, so the query size is constant).
To decide whether a query is tractable, it does not suffice to analyse separately the sub-queries over the static relations and over the dynamic relations, respectively. Instead, we need to take the interaction between the static and the dynamic relations into account. Even when the sub-query over the dynamic relations is not tractable, the overall query can become tractable if the dynamic relations are sufficiently constrained by the static ones
Declarative probabilistic programming with datalog
No full textProbabilistic programming languages are used for developing statistical models, and they typically consist of two components: a specification of a stochastic process (the prior), and a specification of observations that restrict the probability space to a conditional subspace (the posterior). Use cases of such formalisms include the development of algorithms in machine learning and artificial intelligence. We propose and investigate an extension of Datalog for specifying statistical models, and establish a declarative probabilistic-programming paradigm over databases. Our proposed extension provides convenient mechanisms to include common numerical probability functions; in particular, conclusions of rules may contain values drawn from such functions. The semantics of a program is a probability distribution over the possible outcomes of the input database with respect to the program. Observations are naturally incorporated by means of integrity constraints over the extensional and intensional relations. The resulting semantics is robust under different chases and invariant to rewritings that preserve logical equivalence
Ten Theses on Logic Languages for the Semantic Web
No full textThis articles discusses the logic, or logic-based, languages
required for a full deployment of the SemanticWeb. It presents ten theses
addressing
1. the kinds of logic languages needed,
2. data and data processing,
3. semantics, and
4. engineering and rendering issues.
The views reported about in this article have been presented at the W3C
Workshop on Rule Languages for Interoperability (27-28 April 2005,Washington,
D.C., USA, http://www.w3.org/2004/12/rules-ws/)
- …
