Answer Set Programming et interrogation

Answer Set Programming et interrogation

Fabien Garreau Laurent Garcia Claire Lefèvre Igor Stéphan  

Université d’Angers, 2 boulevard Lavoisier, 49045 Angers, France

Corresponding Author Email: 
fabien.garreau|laurent.garcia|claire.lefevre|igor.stephan@univ-angers.fr
Page: 
555-602
|
DOI: 
https://doi.org/10.3166/ria.32.555-602
Received: 
| |
Accepted: 
| | Citation

OPEN ACCESS

Abstract: 

Ontologies are used to describe information about concepts and links between them. Several efficient reasoners are available for query answering with ontologies. When information to be processed is imperfect or is subject to exception, common formalisms are not suitable anymore, that is why we propose the use of Answer Set Programming (ASP) that offers a better expressivity for ontologies. We take interest in the formal definition of query answering in ASP and we show that related implementations give interesting results both on traditional ontologies and with those containing exceptions.

Keywords: 

answer set programming, query answering, ontology.

1. Introduction
2. Préliminaires
3. Interrogation en ASP
4. Inconsistance et interrogation en ASP
5. Dépendance de la requête
6. Implémentation et expérimentations
7. Perspectives d’optimisation
8. Conclusion
Annexes
  References

Abiteboul S., Hull R., Vianu V. (1995). Foundations of Databases. Addison-Wesley.

Alviano M., Dodaro C., Faber W., Leone N., Ricca F. (2013). WASP: A Native ASP Solver Based on Constraint Learning. In Proceedings of the 12th International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR’13), vol. 8148, p. 55-67.

Alviano M., FaberW. (2011). Dynamic Magic Sets and Super-Coherent Answer Set Programs. AI Communication, vol. 24, no 2, p. 125–145.

Alviano M., Faber W., Woltran S. (2014). Complexity of Super-Coherence Problems in ASP. Theory and Practice of Logic Programming, vol. 14, p. 339–361.

Alviano M., Leone N., Manna M., Terracina G., Veltri P. (2012). Magic Sets for Datalog with Existential Quantifiers. In Proceedings of the 2nd International Workshop on Datalog in Academia and Industry, Datalog 2.0, p. 31–43.

Alviano M., Morak M., Pieris A. (2017). Stable Model Semantics for Tuple-Generating Dependencies Revisited. In Proceedings of the 36th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, p. 377–388.

Apt K. R., Bol R. (1994). Logic Programming and Negation: A Survey. Journal of Logic Programming, vol. 19, p. 9–71.

Arenas M., Gottlob G., Pieris A. (2014). Expressive Languages for Querying the Semantic Web. In Proceedings of the 33rd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, p. 14–26.

Baget J.-F., Garcia L., Garreau F., Lefèvre C., Rocher S., Stéphan I. (2018). Bringing Existential Variables in Answer Set Programming and Bringing Non-Monotony in Existential Rules: Two Sides of the Same Coin. Annals of Mathematics and Artificial Intelligence, vol. 82, no 1-3, p. 3–41.

Baget J.-F., Garreau F., Mugnier M.-L., Rocher S. (2014). Revisiting Chase Termination for Existential Rules and their Extension to Nonmonotonic Negation. In Proceedings of the 15th International Workshop on Non-Monotonic Reasoning (NMR’14).

Baget J.-F., Leclère M., Mugnier M.-L., Salvat E. (2011). On Rules with Existential Variables: Walking the Decidability Line. Artificial Intelligence, vol. 175, no 9-10, p. 1620-1654.

Bancilhon F., Maier D., Sagiv Y., Ullman J. D. (1986). Magic Sets and Other Strange Ways to Implement Logic Programs (Extended Abstract). In Proceedings of the 5th ACM SIGACTSIGMOD Symposium on Principles of Database Systems, p. 1–15.

Benchmark university dlv. (2012). http://www.mat.unical.it/kr2012/.

Benchmark university graal. (2014). http://graphik-team.github.io/graal/experiments1.

Cali A., Gottlob G., Lukasiewicz T., Marnette B., Pieris A. (2010). Datalog+/-: A Family of Logical Knowledge Representation and Query Languages for New Applications. In Proceedings of the 25th Annual IEEE Symposium on Logic in Computer Science, p. 228–242.

Calvanese D., Giacomo G. D., Lembo D., Lenzerini M., Rosati R. (2007). Tractable Reasoning and Efficient Query Answering in Description Logics: The DL-Lite Family. Journal of Automated Reasoning, vol. 39, no 3, p. 385-429.

Ceri S., Gottlob G., Tanca L. (1989). What You Always Wanted to Know About Datalog (And Never Dared to Ask). IEEE Transactions on Knowledge and Data Engineering, vol. 1, no 1, p. 146–166.

Costa N., Knorr M., Leite J. (2015). Querying LUBM with Non-monotonic Features in Protege using NoHR. In Proceedings of the ISWC 2015 Posters & Demonstrations Track co-located with the 14th International Semantic Web Conference (ISWC’15).

Dix J. (1992). A Framework for Representing and Characterizing Semantics of Logic Programs. In Proceedings of the 3rd International Conference on Principles of Knowledge Representation and Reasoning (KR’92), p. 591–602.

Dung P. (1992). On the Relations between Stable and Well-Founded Semantics of Logic Programs. Theoretical Computer Science, vol. 105, no 1, p. 7 - 25.

Eiter T., Ianni G., Lukasiewicz T., Schindlauer R., Tompits H. (2008). Combining Answer Set Programming with Description Logics for the Semantic Web. Artificial Intelligence, vol. 172, no 12-13, p. 1495–1539.

Faber W., Greco G., Leone N. (2007). Magic Sets and their Application to Data Integration. Journal of Computer and System Sciences, vol. 73, no 4, p. 584 - 609. (Special Issue: Database Theory 2005)

Faber W., Leone N., Perri S. (2012). The Intelligent Grounder of DLV. In Correct Reasoning - Essays on Logic-Based AI in Honour of Vladimir Lifschitz, LNCS, vol. 7265, p. 247-264.

Ferraris P., Lee J., Lifschitz V. (2011). Stable Models and Circumscription. Artificial Intelligence, vol. 175, no 1, p. 236 - 263.

Gallaire H., Minker J., Nicolas J. (1984). Logic and Databases: A Deductive Approach. ACM Computing Surveys, vol. 16, no 2, p. 153–185.

Garreau F., Garcia L., Lefèvre C., Stéphan I. (2015). 9-ASP. In Proceedings of ONTOLP Workshop (co-located with IJCAI’15).

Gebser M., Kaminski R., Kaufmann B., Schaub T. (2014). Clingo = ASP + Control: Preliminary Report. In Proceedings of Technical Communications of the 29th International Conference on Logic Programming (ICLP’14).

Gebser M., Kaminski R., König A., Schaub T. (2011). Advances in gringo Series 3. In Proceedings of 11th International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR’11), LNCS, vol. 6645, p. 345-351.

Gebser M., Kaufmann B., Neumann A., Schaub T. (2007). Conflict-Driven Answer Set Solving. In Proceedings of the 20th International Joint Conference on Artificial Intelligence (IJCAI’07), p. 386-392.

Gebser M., Obermeier P., Schaub T. (2013). A System for Interactive Query Answering with Answer Set Programming. In Proceedings of the 6th Workshop on Answer Set Programming and Other Computing Paradigms (ASPOCP’13).

Gelfond M., Lifschitz V. (1988). The Stable Model Semantics for Logic Programming. In Proceedings of the 5th International Conference and Symposium on Logic Programming (iclp’88), p. 1070-1080.

Glimm B., Horrocks I., Motik B., Stoilos G., Wang Z. (2014). Hermit: An OWL 2 Reasoner. Journal of Automated Reasoning, vol. 53, no 3, p. 245–269.

Gottlob G., Hernich A., Kupke C., Lukasiewicz T. (2012). Equality-friendly Well-founded Semantics and Applications to Description Logics. In Proceedings of the 26th National Conference on Artificial Intelligence (AAAI’12), p. 757–764.

Gottlob G., Hernich A., Kupke C., Lukasiewicz T. (2014). Stable Model Semantics for Guarded Existential Rules and Description Logics. In Proceedings of the 14th International Conference on the Principles of Knowledge Representation and Reasoning (KR’14), p. 258–267.

Guo Y., Pan Z., Heflin J. (2005). LUBM: A Benchmark for OWL Knowledge Base Systems. Journal of Web Semantics, vol. 3, no 2-3, p. 158–182.

Hernich A., Kupke C., Lukasiewicz T., Gottlob G. (2013). Well-founded Semantics for Extended Datalog and Ontological Reasoning. In Proceedings of the 32rd ACM SIGMODSIGACT- SIGAI Symposium on Principles of Database Systems, p. 225–236.

Kollia I., Glimm B., Horrocks I. (2011). SPARQL Query Answering over OWL Ontologies. In The Semantic Web: Research and Applications - 8th Extended Semantic Web Conference (ESWC’11), p. 382–396.

Lefèvre C., Béatrix C., Stéphan I., Garcia L. (2017). ASPeRiX, a First Order Forward Chaining Approach for Answer Set Computing. Theory and Pratice of Logic Programming, vol. 17, no 3, p. 266-310.

Leone N., Manna M., Terracina G., Veltri P. (2012). Efficiently Computable Datalog9 Programs. In Proceedings of the 13th International Conference on Principles of Knowledge Representation and Reasoning (KR’12), p. 13–23.

Leone N., Pfeifer G., FaberW., Eiter T., Gottlob G., Perri S. et al. (2006). The DLV System for Knowledge Representation and Reasoning. ACM Transactions on Computational Logic, vol. 7, no 3, p. 499-562.

Lloyd J. (1987). Foundations of Logic Programming. Springer-Verlag New York, Inc. Lukasiewicz T. (2004). A Novel Combination of Answer Set Programming with Description Logics for the Semantic Web. In Proceedings of the 14th International Conference on Principles of Knowledge Representation and Reasoning (KR’04), p. 141–151.

Magka D., Krötzsch M., Horrocks I. (2013). Computing Stable Models for Nonmonotonic Existential Rules. In Proceedings of the 23rd International Joint Conference on Artificial Intelligence (IJCAI’13), p. 1031–1038.

Motik B., Rosati R. (2008). Reconciling Description Logics and Rules. Journal of ACM, vol. 57, no 5, p. 30:1–30:62.

Musen M. A. (2015). The protégé Project: a Look Back and a Look Forward. AI Matters, vol. 1, no 4, p. 4–12.

Owl2dlgp graal. (2015). http://graphik-team.github.io/graal/downloads/owl2dlgp.

OWL 2 Web Ontology Language Document Overview (Second Edition). (2012). https://www.w3.org/TR/2012/REC-owl2-overview-20121211/.

Pérez-Urbina H., Horrocks I., Motik B. (2009). Efficient Query Answering for OWL 2. In Proceedings of the 8th International Semantic Web Conference, (ISWC’09), p. 489–504.

Prud’hommeaux E., Seaborne A. (2008). SPARQL Query Language for RDF. In W3c: Available at http://www.w3.org/tr/rdf-sparql-query/.

Schaub T., Thielscher M. (1996). Skeptical Query-Answering in Constrained Default Logic. In Proceedings of the International Conference on Formal and Applied Practical Reasoning (FAPR’96), p. 567–581.

Sirin E., Parsia B., Grau B. C., Kalyanpur A., Katz Y. (2007). Pellet: A Practical OWL-DL Reasoner. Journal of Web Semantics, vol. 5, no 2, p. 51–53.

DLV - User Manual. (2004). http://www.dlvsystem.com/html/DLV_User_Manual.html.

Van Gelder A., Ross K. A., Schlipf J. S. (1991). The Well-founded Semantics for General Logic Programs. Journal of the ACM (JACM), vol. 38, no 3, p. 619–649.

Weinzierl A. (2017). Blending Lazy-Grounding and CDNL Search for Answer-Set Solving. In Proceedings of the 14th International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR’17), LNCS, p. 191–204.