Ricerc@Sapienza

The Ontology-Based Data Access (OBDA) paradigm aims at providing to the users a unified and shared conceptual view of the domain of interest (ontology), while still enabling the data to be stored in different data sources. Such data are mapped to the ontology through declarative specifications. In this work we consider the ontology expressed in OWL 2 QL, relational sources, the mapping expressed in R2RML, and the user queries expressed in SPARQL.

In this work we introduce the operations of unbounded and bounded prefix-suffix square reduction. We show that, in general, the time complexity of the unbounded prefix-suffix square reduction of a language increases by an n factor in comparison to the complexity of the given language. This factor is just the bound in the case of bounded prefix-suffix square reduction and is not necessary for regular languages. As a consequence, the class of regular languages is closed under unbounded and bounded prefix-suffix square reduction.