Characterizing tractable restrictions of query languages

Sala Javier Pinto, DCC, Pontificia Universidad Católica de Chile

One of the most fundamental problem associated to any query language is that of evaluation: Given a query Q, a database D, an a tuple t, decided whether t belongs to the answer of Q over D. As expected, this problem is computational intractable for most natural languages, for example, first-order queries and conjunctive queries. Thus a natural problem is to identify tractable restrictions of these languages. An even more challenging problem is to identify precisely all the tractable restrictions, that is, to characterize the tractable restrictions in terms of structural properties of queries. In this talk, we first review a known characterization of the tractable restrictions of conjunctive queries. Then we discuss how to apply these ideas to obtain new characterizations for well-designed SPARQL queries.