GT ALGA Annual Meeting 2018

Abstract: Recent years have seen an increasing interest in ontology-mediated query answering (OMQA), in which the semantic knowledge provided by an ontology is exploited when querying data. Adding an ontology has several advantages (e.g. simplifying query formulation, integrating data from different sources, providing more complete answers to queries), but it also makes the query answering task more difficult. Query rewriting, which reduces OMQA to the evaluation of database queries, is a key algorithmic technique that allows OMQA to be implemented on top of existing database systems, thereby benefitting from the maturity and performance of such systems.

In this talk, I will give a short introduction to ontology-mediated query answering, focusing on ontologies formulated using description logics. Then I will consider two natural analysis tasks related to query rewriting (concerning the existence and succinctness of rewritings) and present solutions obtained by leveraging connections to different areas of theoretical computer science (namely, circuit complexity, automata, and constraint satisfaction).

Abstract: We define and evaluate a new preprocessing technique for propositional model counting. This technique leverages definability, i.e., the ability to determine that some gates are implied by the input formula F. Such gates can be exploited to simplify F without modifying its number of models. Unlike previous techniques based on gate detection and replacement, gates do not need to be made explicit in our approach. Our preprocessing technique thus consists of two phases: computing a bipartition (I,O) of the variables of F where the variables from O are defined in F in terms of I, then eliminating some variables of O in F. Our experiments show the computational benefits which can be obtained by taking advantage of our preprocessing technique for model counting.

Abstract: Cypher is a query languages for databases that are structured as property graphs. It was originally implemented as part of the proprietary graph database Neo4j and it is now widely used in industry. Cypher was designed to be easily readable and usable by non-experts. As a result, the semantics of Cypher queries is described using natural language and the expected result is often ambiguous. Our work aims at defining a full denotational semantics of Cypher, in order to pave the way for a future open standard.