Agenda

Département
Langue
Date
Thématique

Aucun évènement

Voici les prochains

2023

février

  • 13:00
    14:00

    [LX] Aliaume Lopez

    Preservation theorems and locality of first order logic

    In this talk, we will investigate the tight connection between the locality properties of first-order logic, and the relativisation (or lack thereof) of the Łós-Tarski Theorem to classes of structures. Starting with a gentle introduction to preservation theorems, we will then focus on two particular classes of sentences: existential formulas, and existential local formulas. We prove that existential local sentences are exactly those that can be rewritten in a positive variant of the Gaifman normal form, and can be characterized semantically as sentences that are preserved under local elementary embeddings. As expected, this semantic characterization fails in the finite. Quite surprisingly though, we can leverage this class of sentences to prove the following locality property for classes of finite structures: the Łós-Tarski Theorem relativises to a class C of finite structures if and only if the Łós-Tarski Theorem locally relativises to the class C, provided that the class C is hereditary and closed under disjoint unions. As a consequence of this result, we not only obtain new proofs of relativisation of Łós-Tarski Theorem, but also provide new classes where this relativisation holds.

    LaBRI
  • 13:00
    14:00

    [MTV]

    salle 178, zoom: https://bordeaux-inp-fr.zoom.us/j/89508306159
  • 14:00
    15:00

    [RATIO] Anantha Padmanabha

    https://ratio.labri.fr/#meetings
    Title: Algorithms for consistent query answering under primary key constraints

    Abstract: Databases often have constraints. One of the basic constraints is the « primary key constraint » which states there can be at most one tuple for every primary key. However, these days it is common to have databases that violate such constraints which is called an « inconsistent database ». In particular, if a database violates primary key constraint, it will contain more than one tuple for the same primary key. In this setting, the notion of a repair is defined by picking exactly one tuple for each primary key (maximal consistent subset of the database). A Boolean conjunctive query q, is certain for an inconsistent database D if q evaluates to true over all repairs of D. In this context, we have a dichotomy conjecture that states that for a fixed boolean conjunctive query q, testing whether q is certain for an input database D is either polynomial time or coNP-complete.

    The conjecture is open in general, but has been verified for self-join-free and path queries. However, the polynomial time algorithms known in the literature are complex and use different strategies in the two cases. We propose a simple inflationary fixpoint algorithm for consistent query answering which correctly computes certain answers when the query q falls in the polynomial time cases for self-join-free queries and path queries. This raises a natural question, whether this algorithm works for all polynomial time cases. We answer this negatively and show that there are polynomial time certain queries (with self-joins) which cannot be computed by such an algorithm. These results were obtained in collaboration with Diego Figueira, Luc Segoufin and Cristina Sirangelo and will be presented at ICDT'23.

    We will also discuss some ongoing work on the conjecture for queries with self-joins over two atoms.
    https://ratio.labri.fr/#meetings

    LaBRI
  • 14:00
    15:00

    [M2F] Balder ten Cate (University of Amsterdam)

    LaBRI
  • 13:00
    14:00

    [LX] Sylvain Lombardy

    LaBRI
  • 14:00
    15:00

    [RATIO] Elise Perrotin (CRIL Lens)

    LaBRI

mars