Requêtes de comptage pour l’accès aux données en présence d’ontologies
Language
en
Thèses de doctorat
Date
2022-09-30Speciality
Informatique
Doctoral school
École doctorale de mathématiques et informatiqueAbstract
La réponse à des requêtes en présence d'ontologies est une approche prometteuse pour l'intégration et l'accès aux données qui a été activement étudiée ces quinze dernières années. La grande majorité des travaux dans ce ...Read more >
La réponse à des requêtes en présence d'ontologies est une approche prometteuse pour l'intégration et l'accès aux données qui a été activement étudiée ces quinze dernières années. La grande majorité des travaux dans ce domaine se concentre sur les requêtes conjonctives, alors que des requêtes plus expressives, qui offrent des fonctionnalités de comptage ou d'autres formes d'agrégation demeurent largement inexplorées. Dans cette thèse, nous introduisons une forme unifiée de requêtes de comptage, nous la relions à celles déjà existantes, et étudions la complexité du problème consistant à répondre à ces requêtes en présence d'ontologies exprimées dans la logique de description ALCHI ou l'une de ses sous-logiques. Dans la mesure où la complexité de ce problème dans le cas général est inaccessible en pratique et parfois très élevée sur de telles ontologies, nous considérons également deux restrictions sur ces requêtes: l'enracinement et l'atomicité, pour lesquelles nous établissons de meilleurs résultats en terme de complexité.Read less <
English Abstract
Ontology-mediated query answering (OMQA) is a promising approach to data access and integration that has been actively studied in the knowledge representation and database communities for more than a decade. The vast ...Read more >
Ontology-mediated query answering (OMQA) is a promising approach to data access and integration that has been actively studied in the knowledge representation and database communities for more than a decade. The vast majority of work on OMQA focuses on conjunctive queries, whereas more expressive queries that feature counting or other forms of aggregation remain largely unexplored. In this thesis, we introduce a general form of counting conjunctive query (CCQ), relate it to previous proposals, and study the complexity of answering such queries in the presence of ontologies expressed in the description logic ALCHI or its sublogics. As the general case of CCQ answering is intractable and often of high complexity over such ontologies, we consider two practically relevant restrictions, namely rooted CCQs and Boolean atomic CCQs, for which we establish improved complexity bounds.Read less <
Keywords
Accès aux données en présence d'ontologie
Logiques de description
Requêtes de comptage
Complexité du raisonnement
English Keywords
Ontology-Mediated query answering
Description logics
Counting query
Complexity of reasoning
Origin
STAR importedCollections