Seminars

«Août Oct»

2022
Fri 30th Sep 10:00 am 11:30 am	Seminar by Liat Peterfreund Speaker: Liat Peterfreund — sites.google.com/view/liatpeterfreund/ Title: Querying Incomplete Numerical Data: Between Certain and Possible Answers Abstract: Queries with aggregation and arithmetic operations, as well as incomplete data, are common in real-world databases, but we lack a good understanding of how they should interact. On the one hand, systems based on SQL provide ad-hoc rules for numerical nulls, on the other, theoretical research largely concentrates on the standard notions of certain and possible answers which in the presence of numerical attributes and aggregates are often meaningless. In this work, we define a principled compositional framework for databases with numerical nulls and answering queries with arithmetic and aggregations over them. We assume that missing values are given by probability distributions associated with marked nulls, which yields a model of probabilistic bag databases. We concentrate on queries that resemble standard SQL with arithmetic and aggregation and show that they are measurable, and that their outputs have a finite representation. Moreover, since the classical forms of answers provide little information in the numerical setting, we look at the probability that numerical values in output tuples belong to specific intervals. Even though their exact computation is intractable, we show efficient approximation algorithms to compute such probabilities. The talk is based on joint work with Marco Console and Leonid Libkin, and will be presented in PODS 2023.
Fri 16th Sep 11:00 am 12:00 pm	Seminar Luis Galárraga Speaker : Luis Galárraga — luisgalarraga.de/about/ Title: Computing How-Provenance for SPARQL Queries via Query Rewriting Abstract: Over the past few years, we have witnessed the emergence of large knowledge graphs built by extracting and combining information from multiple sources. This has propelled many advances in query processing over knowledge graphs, however the aspect of providing provenance explanations for query results has so far been mostly neglected. In this talk I will present SPARQLprov, a method based on query rewriting, to compute how-provenance polynomials for SPARQL queries over knowledge graphs. Contrary to existing works, SPARQLprov is system-agnostic and can be applied to standard and already deployed SPARQL engines without the need of customized extensions. To do so, we rely on spm-semirings to compute polynomial annotations that respect the property of commutation with homomorphisms on monotonic and non-monotonic SPARQL queries without aggregate functions. An evaluation on real and synthetic data shows that SPARQLprov over standard engines competes with state-of-the-art solutions for how-provenance computation, while covering a larger fragment of the query language.

2022

Fri 30th Sep

10:00 am

11:30 am

Seminar by Liat Peterfreund

Speaker: Liat Peterfreund — sites.google.com/view/liatpeterfreund/

Title: Querying Incomplete Numerical Data: Between Certain and Possible Answers

Abstract:
Queries with aggregation and arithmetic operations, as well as incomplete data, are common in real-world databases, but we lack a good understanding of how they should interact. On the one hand, systems based on SQL provide ad-hoc rules for numerical nulls, on the other, theoretical research largely concentrates on the standard notions of certain and possible answers which in the presence of numerical attributes and aggregates are often meaningless.
In this work, we define a principled compositional framework for databases with numerical nulls and answering queries with arithmetic and aggregations over them. We assume that missing values are given by probability distributions associated with marked nulls, which yields a model of probabilistic bag databases. We concentrate on queries that resemble standard SQL with arithmetic and aggregation and show that they are measurable, and that their outputs have a finite representation. Moreover, since the classical forms of answers provide little information in the numerical setting, we look at the probability that numerical values in output tuples belong to specific intervals. Even though their exact computation is intractable, we show efficient approximation algorithms to compute such probabilities.

The talk is based on joint work with Marco Console and Leonid Libkin, and will be presented in PODS 2023.

Fri 16th Sep

11:00 am

12:00 pm

Seminar Luis Galárraga

Speaker : Luis Galárraga — luisgalarraga.de/about/

Title: Computing How-Provenance for SPARQL Queries via Query Rewriting

Abstract:
Over the past few years, we have witnessed the emergence of large knowledge graphs built by extracting and combining information from multiple sources. This has propelled many advances in query processing over knowledge graphs, however the aspect of providing provenance explanations for query results has so far been mostly neglected. In this talk I will present SPARQLprov, a method based on query rewriting, to compute how-provenance polynomials for SPARQL queries over knowledge graphs. Contrary to existing works, SPARQLprov is system-agnostic and can be applied to standard and already deployed SPARQL engines without the need of customized extensions. To do so, we rely on spm-semirings to compute polynomial annotations that respect the property of commutation with homomorphisms on monotonic and non-monotonic SPARQL queries without aggregate functions. An evaluation on real and synthetic data shows that SPARQLprov over standard engines competes with state-of-the-art solutions for how-provenance computation, while covering a larger fragment of the query language.

← −− − 10 50 100 + ++ →