ASP technologIes for Querying large scale multisource heterogeneous web information – ASPIQ

The used methodology stems from three languages for knowledge representation:

The lightweight description logic DL-Lite, which is a high level language, which provides the foundations of a tractable dialect of OWL2 (namely OWL2 QL). This language is not very expressive but is suitable for knowledge bases with large amounts of data. Moreover the satisfiability and conjunctive query answering problems within this language are polynomial.

Answer Set Programming (ASP) which is a unified formalism for both knowledge representation and reasoning in Artificial Intelligence (AI). This is a very expressive language suitable for representing exceptions and incomplete information. Moreover several efficient solvers are available for non-monotonic reasoning.

Existential rules are a formalism which can be seen as an extension of Datalog or as a logical translation of conceptual graph rules, suitable for query answering within the framework of Ontology Based Data Access (OBDA). The expressivity of this language is between DL-Lite and ASP, and it offers several expressivity-complexity tradeoffs corresponding to different classes of rules.

The main results of the project concerning knowledge representation are:

• ?ASP: a language that generalizes ASP with the introduction and the processing of existential variables and existential rules with the introduction and the processing of non-monotonic rules

• ?-DL-Lite: the possibilistic extension of the lightweight description logic DL-Lite for representing uncertain Aboxes/Tboxes

Results of this project also concern reasoning issues:

• revision and merging of ASP logic programs
• revision and merging of knowledge bases expressed in DL-Lite and in ?-DL-Lite
• inconsistency-tolerant query answering on knowledge bases expressed in existential rules with the definition of a unified framework for inference relations
• query answering of ASP logic programs

A prototype has been implemented that from a knowledge base expressed within a OWL2 fragment produces an ASP which can be queried. The prototype has been experimented on query answering information stemming from 3D surveys of underwater archaeologist sites and provides an helpful tool to underwater archaeologists for the wrecks study.

Three international workshops have been organized within the project « ONTOlogies and Logic programming » (http://ontolp.lsis.org) ONTOLP 2015 (affiliated with IJCAI 2015), ONTOLP 2016 (affiliated with IJCAI 2016) and « ASP technologIes for Querying large scale multisource heterogeneous web information » (http://waspiq2017.lsis.org) WASPIQ 2017 (affiliated with IEA/AIE 2017)
Two PHD thesis have been defended during the project (Zied Bouraoui CRIL in june 2015 and Fabien Garreau LERIA + LIRMM in November 2016).
The project gave rise to numerous publications in international journals (TPLP 2017, JLC 2017, AMAI 2017, …) and international conferences (ECAI 2014, JELIA 2014, IJCAI 2015, IJCAI 2016, KR 2016, ECAI 2016, IJCAI 2017, …). See web site (http://aspiq.lsis.org/)

The project provides numerous future issues. The ASP extension with existential variables in the head of rules (?ASP) has been achieved both from theoretical and practical points of views, a new version of the ASPeRiX solver is now available, optimizations must be further investigated in order to improve the query answering efficiency, in particular minimizing the instantiation of necessary rules to answer to queries.
?ASP generalizes both ASP and existential rules, and the identification of tractable classes of this language is a significant problem. Stopping conditions of the saturation mechanism have been given for the FES class, however redefining rewriting mechanisms in ?ASP is a difficult open problem.

A unified framework has been proposed for inconsistent-tolerant inference relations for knowledge bases represented in the existential rules formalism which captures already known inference relations and proposes new inference relations. This is a road map which suggests directions for defining new inference relations of polynomial complexity.

The qualitative possibilistic extension of DL-Lite has been achieved with a min based semantics, a quantitative possibilistic extension of DL-Lite with a product based semantics is a natural sequel to this project.

The revision and fusion of ASP programs proposed within the project could be extended to possibilistic ASP programs, moreover in order to introduce uncertainty to ?ASP a study could be deal with the possibilistic extension of ?ASP.

The application to query answering from 3D surveys of underwater archaeological sites provides an useful tool for archaeologists, in particular the possibility of visualizing density maps of the sites. Other applications using default rules could be possible for query answering from 3D surveys of building within the context of medieval archaelogy.

Publications

Edition (2): CEUR-WS proc 205, No special AMAI S83 2018
Book chapter (1): BRA 2013
International Journals (5): ACM-CL 2016, AMAI 2017, TPLP 2017, JLC 2017, AMAI 2018
International Conferences (28): SUM 2013 (2), IAT 2013, ISAIM 2014, ECAI 2014 (3), JELIA 2014, ICTAI 2014, SUM 2014 (3), FLAIRS 2015, BRA 2015, ECSQARU 2015, IJCAI 2015, SUM 2016 (2), KR 2016, ECAI 2016, JELIA 2016, IJCAI 2016, AAMAS 2017 (2), RuleML+RR 2017, ECSQARU 2017, SUM 2017, IJCAI 2017
National Conferences (7): MFI 2013, JIAF 2013, RFIA 2014(2), JIAF 2014, LFA 2014, JIAF 2015
International workshops (11): NMR 2014, ONTOLP 2015 (2), ONTOLP 2016 (2), ESWC 2017, WASPIQ 2017 (5)

PHD Thesis

Z. Bouraoui. Inconsistency and uncertainty handling in lightweight description logics. Université d’Artois. Juin 2015.

F. Garreau. Extension d’ASP pour couvrir des fragments DL traitables : étude théorique et implémentation. Université d’Angers et Université Montpellier 2. Novembre 2016.

Softwares

plrsf: software implementing the merging of ASP logic programs.
dlgp2easp: translator of a .dlgp file into a .easp file.
eASPeRiX: extension of the ASPeRiX solver with existential variables in the head of the rules.
easp2asp: translator of a .easp into a .asp file.
query answering integrated within the eASPeRiX solver: query answering of ASP logic programs.
vizualisation of the results of the queries integrated within the Arpenteur tool
Prototype: integration of the previous tools in order knowledge bases query answering.
?-DL-Lite: a tool for representing and reasoning with possibilistic DL-Lite ontologies. It implements in particular, of a new algorithm for computing the inconsistency degree.
no-inference: a tool developed in java for the inconsistency tolerant inference by non-objection within the framework of OBDA.
GoDL: tool for handling ordered possibilistic knowledge bases potentially inconsistent.

The overall objective of the project is to propose new solutions for querying large scale multisource heterogeneous information, with two applications to web linked data and underwater archaeological surveys, where in both applications we face large data sets expressed in RDFs and OWL. The project is centered on three main requirements:
Processing multisource information: The fusion of multisource information systems is a huge and urgent task for the World-Wide Web applications, where pieces of information are often redundant, heterogeneous, imprecise,uncertain.. Besides, even if the information provided by each source is consistent it is rather unlikely that the union of all information will be consistent too. This project proposes adequate solutions to cope with inconsistent information.
Processing heterogeneous information: The information provided by multiple sources is often heterogeneous. This project focuses on web-based languages such as OWL2 family, more precisely, tractable sublanguages dedicated to query answering, OWL2 EL, OWL2 QL OWL2 RL. Nevertheless, currently available languages do not allow for satisfactory uncertainty and inconsistency handling.
Performing large scale reasoning: Effective implementation of huge amount of heterogeneous multi-source items of information requires suitable tools. The Answer Set Programming paradigm (ASP), with the development of more and more efficient solvers, compelled recognition in the last decade as an efficient reasoning tool but also as a very expressive formalism. However, most of the solvers are mainly dedicated to propositional logic, while an extension of ASP is required for querying ontological knowledge represented in OWL2 sublanguages.
The main objective of this project is to propose:
1.Extensions of standard ASP for representing OWL2 tractable sublanguages in order to provide a common representation of the knowledge provided by multiple sources, allowing to deal with inconsistencies, exceptions and uncertainties, while staying compatible with efficiently querying knowledge bases with large amounts of data.
2.New operations for merging information represented in extended ASP, of various reliability and quality with or without uncertainty, according to the commensurability assumption or not. Besides efficient algorithms will be proposed for handling conflicts in extended ASP programs.
3.The identification of subclasses of this extended ASP allowing for an implementation of efficient query answering mechanisms moreover able to order and compute the most relevant answers.
4.An efficient implementation of scalable inconsistency handling, fusion operations, defeasible reasoning like exception handling, possibilistic uncertainty and query answering for multiple knowledge bases The design of a prototype reasoning system capable of managing fusion operations, solving conflicts and query answering for multiple knowledge bases. This prototype will be evaluated on two applications :
Web data integration, the Linked Data issue, which consists of interconnecting web data sources (bibliographic catalogues in our case) in collaboration with ABES (http://www.abes.fr).
querying information stemming from 3D surveys for helping archaeologists to study underwater sites, in the following of the European VENUS project (http://sudek.esil.univmed.fr/venus/).
This project is part of different very active research directions at the international level. It highlight methods and technologies for managing uncertainty and inconsistency in a semantically defendable manner while being able to process huge amounts of data.
This project joins four partners together: CRIL, LERIA, LIRMM, LSIS and combines complementary skills in different domains of Artificial Intelligence. The project participants are particularly well placed in the international community as shown by their recent publications in famous international journals and top-level conferences (IJCAI, AAAI, ECAI, KR, ...).