On the Complexity of Ontological Reasoning under Disjunctive Existential Rules

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

   Google Scholar 

2. Alviano, M., Faber, W., Leone, N., Manna, M.: Disjunctive Datalog with existential quantifiers: Semantics, decidability, and complexity issues. In: TPLP (to appear, 2012)

   Google Scholar 

3. Andréka, H., Németi, I., van Benthem, J.: Modal languages and bounded fragments of predicate logic. J. Philosophical Logic 27(3), 217–274 (1998)

   Article  MATH  Google Scholar 

4. Baader, F.: Least common subsumers and most specific concepts in a description logic with existential restrictions and terminological cycles. In: Proc. of IJCAI, pp. 319–324 (2003)

   Google Scholar 

5. Baader, F., Brandt, S., Lutz, C.: Pushing the \(\mathcal{EL}\) envelope. In: Proc. of IJCAI, pp. 364–369 (2005)

   Google Scholar 

6. Baader, F., Calvanese, D., McGuinness, D.L., Nardi, D., Patel-Schneider, P.F.: The Description Logic Handbook: Theory, Implementation, and Applications. Cambridge University Press (2003)

   Google Scholar 

7. Baget, J.-F., Leclère, M., Mugnier, M.-L., Salvat, E.: On rules with existential variables: Walking the decidability line. Artif. Intell. 175(9-10), 1620–1654 (2011)

   Article  MATH  Google Scholar 

8. Bárány, V., Gottlob, G., Otto, M.: Querying the guarded fragment. In: Proc. of LICS, pp. 1–10 (2010)

   Google Scholar 

9. Beeri, C., Vardi, M.Y.: The Implication Problem for Data Dependencies. In: Even, S., Kariv, O. (eds.) ICALP 1981. LNCS, vol. 115, pp. 73–85. Springer, Heidelberg (1981)

   Chapter  Google Scholar 

10. Berardi, D., Calvanese, D., Giacomo, G.D.: Reasoning on UML class diagrams. Artif. Intell. 168(1-2), 70–118 (2005)

    Article  MATH  Google Scholar 

11. Cabibbo, L.: The expressive power of stratified logic programs with value invention. Inf. Comput. 147(1), 22–56 (1998)

    Article  MathSciNet  MATH  Google Scholar 

12. Calì, A., Gottlob, G., Kifer, M.: Taming the infinite chase: Query answering under expressive relational constraints. In: Proc. of KR, pp. 70–80 (2008)

    Google Scholar 

13. Calì, A., Gottlob, G., Lukasiewicz, T.: A general Datalog-based framework for tractable query answering over ontologies. In: Proc. of PODS, pp. 77–86 (2009)

    Google Scholar 

14. Calì, A., Gottlob, G., Lukasiewicz, T., Marnette, B., Pieris, A.: Datalog^±: A family of logical knowledge representation and query languages for new applications. In: Proc. of LICS, pp. 228–242 (2010)

    Google Scholar 

15. Calì, A., Gottlob, G., Pieris, A.: Advanced processing for ontological queries. VLDB 3(1), 554–565 (2010)

    Google Scholar 

16. Calì, A., Gottlob, G., Pieris, A.: Query Answering under Non-guarded Rules in Datalog^±. In: Hitzler, P., Lukasiewicz, T. (eds.) RR 2010. LNCS, vol. 6333, pp. 1–17. Springer, Heidelberg (2010)

    Chapter  Google Scholar 

17. Calvanese, D., Giacomo, G.D., Lembo, D., Lenzerini, M., Rosati, R.: Data complexity of query answering in description logics. In: Proc. of KR, pp. 260–270 (2006)

    Google Scholar 

18. Calvanese, D., Giacomo, G.D., Lembo, D., Lenzerini, M., Rosati, R.: Tractable reasoning and efficient query answering in description logics: The DL-Lite family. J. Autom. Reasoning 39(3) (2007)

    Google Scholar 

19. Chen, P.P.: The Entity-Relationship model - Toward a unified view of data. ACM Trans. Database Syst. 1(1), 9–36 (1976)

    Article  Google Scholar 

20. Deutsch, A., Nash, A., Remmel, J.B.: The chase revisited. In: Proc. of PODS, pp. 149–158 (2008)

    Google Scholar 

21. Eiter, T., Gottlob, G., Mannila, H.: Disjunctive Datalog. ACM Trans. Database Syst. 22(3), 364–418 (1997)

    Article  Google Scholar 

22. Fagin, R., Kolaitis, P.G., Miller, R.J., Popa, L.: Data exchange: Semantics and query answering. Theor. Comput. Sci. 336(1), 89–124 (2005)

    Article  MathSciNet  MATH  Google Scholar 

23. Grädel, E.: On the restraining power of guards. J. Symb. Log. 64(4), 1719–1742 (1999)

    Article  MATH  Google Scholar 

24. Johnson, D.S., Klug, A.C.: Testing containment of conjunctive queries under functional and inclusion dependencies. J. Comput. Syst. Sci. 28(1), 167–189 (1984)

    Article  MathSciNet  MATH  Google Scholar 

25. Krisnadhi, A., Lutz, C.: Data complexity in the EL family of DLs. In: Proc. of DL (2007)

    Google Scholar 

26. Krötzsch, M., Rudolph, S.: Extending decidable existential rules by joining acyclicity and guardedness. In: Proc. of IJCAI, pp. 963–968 (2011)

    Google Scholar 

27. Leone, N., Manna, M., Terracina, G., Veltri, P.: Efficiently computable Datalog^∃ programs. In: Proc. of KR, pp. 13–23 (2012)

    Google Scholar 

28. Marnette, B.: Generalized schema-mappings: From termination to tractability. In: Proc. of PODS, pp. 13–22 (2009)

    Google Scholar 

29. Patel-Schneider, P.F., Horrocks, I.: A comparison of two modelling paradigms in the semantic web. J. Web Sem. 5(4), 240–250 (2007)

    Article  Google Scholar 

30. Poggi, A., Lembo, D., Calvanese, D., Giacomo, G.D., Lenzerini, M., Rosati, R.: Linking data to ontologies. J. Data Semantics 10, 133–173 (2008)

    Google Scholar 

31. Vardi, M.Y.: The complexity of relational query languages (extended abstract). In: Proc. of STOCS, pp. 137–146 (1982)

    Google Scholar 

32. Vardi, M.Y.: On the complexity of bounded-variable queries. In: Proc. of PODS, pp. 266–276 (1995)

    Google Scholar 

Download references