[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Skip to main content
Springer Nature Link
Log in

Living with Inconsistency and Taming Nonmonotonicity

  • Conference paper
Datalog Reloaded (Datalog 2.0 2010)

Part of the book series: Lecture Notes in Computer Science ((LNISA,volume 6702))

Included in the following conference series:

Abstract

In this paper we consider rule-based query languages with negation in bodies and heads of rules, traditionally denoted by Datalog ¬¬. Tractable and at the same time intuitive semantics for Datalog ¬¬ has not been provided even though the area of deductive databases is over 30 years old. In this paper we identify sources of the problem and propose a query language, which we call 4QL.

The 4QL language supports a modular and layered architecture and provides a tractable framework for many forms of rule-based reasoning both monotonic and nonmonotonic. As the underpinning principle we assume openness of the world, which may lead to the lack of knowledge. Negation in rule heads may lead to inconsistencies. To reduce the unknown/inconsistent zones we introduce simple constructs which provide means for application-specific disambiguation of inconsistent information, the use of Local Closed World Assumption (thus also Closed World Assumption, if needed), as well as various forms of default and defeasible reasoning.

Supported in part by grant N N206 399334 from Polish Ministry of Science and National Education.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
GBP 19.95
Price includes VAT (United Kingdom)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
GBP 35.99
Price includes VAT (United Kingdom)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
GBP 44.99
Price includes VAT (United Kingdom)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Abiteboul, S., Hull, R., Vianu, V.: Foundations of Databases. Addison-Wesley Pub. Co., Reading (1996)

    Google Scholar 

  2. Alcântara, J., Damásio, C.V., Pereira, L.M.: An encompassing framework for paraconsistent logic programs. J. Applied Logic 3(1), 67–95 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  3. Antoniou, G., van Harmelen, F.: A Semantic Web Primer. The MIT Press, Cambridge (2004)

    Google Scholar 

  4. Arieli, O.: Paraconsistent declarative semantics for extended logic programs. Ann. Math. Artif. Intell. 36(4), 381–417 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  5. Baumgartner, R., Gottlob, G.: On the complexity of model checking for propositional default logics: New results and tractable cases. In: IJCAI, pp. 64–69 (1999)

    Google Scholar 

  6. Belnap, N.D.: A useful four-valued logic. In: Eptein, G., Dunn, J.M. (eds.) Modern Uses of Many Valued Logic, pp. 8–37. Reidel, Dordrechtz (1977)

    Google Scholar 

  7. Besnard, P.: An Introduction to Default Logic. Springer, Heidelberg (1989)

    Book  MATH  Google Scholar 

  8. Blair, H.A., Subrahmanian, V.S.: Paraconsistent logic programming. Theor. Comput. Sci. 68(2), 135–154 (1989)

    Article  MathSciNet  MATH  Google Scholar 

  9. Bolc, L., Borowik, P.: Many-Valued Logics, 1. Theoretical Foundations. Springer, Berlin (1992)

    Book  MATH  Google Scholar 

  10. Brewka, G.: Non-Monotonic Reasoning: Logical Foundations of Commonsense. Cambridge University Press, Cambridge (1991)

    MATH  Google Scholar 

  11. Cadoli, M., Eiter, T., Gottlob, G.: Complexity of propositional nested circumscription and nested abnormality theories. ACM Trans. Comput. Log. 6(2), 232–272 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  12. Cadoli, M., Schaerf, M.: A survey on complexity results for non-monotonic logics. Journal Logic Programming 17, 127–160 (1993)

    Article  MathSciNet  MATH  Google Scholar 

  13. Damásio, C.V., Pereira, L.M.: A survey of paraconsistent semantics for logic programs. In: Handbook of Defeasible Reasoning and Uncertainty Management Systems, pp. 241–320 (1998)

    Google Scholar 

  14. de Amo, S., Pais, M.S.: A paraconsistent logic approach for querying inconsistent databases. International Journal of Approximate Reasoning 46, 366–386 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  15. Doherty, P., Kachniarz, J., Szałas, A.: Using contextually closed queries for local closed-world reasoning in rough knowledge databases. In: Pal, S.K., Polkowski, L., Skowron, A. (eds.) Rough-Neural Computing: Techniques for Computing with Words, Cognitive Technologies, pp. 219–250. Springer, Heidelberg (2004)

    Chapter  Google Scholar 

  16. Doherty, P., Łukaszewicz, W., Skowron, A., Szałas, A.: Knowledge representation techniques. A rough set approach. Studies in Fuziness and Soft Computing, vol. 202. Springer, Heidelberg (2006)

    MATH  Google Scholar 

  17. Doherty, P., Łukaszewicz, W., Szałas, A.: Computing circumscription revisited. Journal of Automated Reasoning 18(3), 297–336 (1997); See also 14th International Joint Conference on AI (IJCAI 1995). Morgan Kaufmann Pub. Inc., San Francisco (1995)

    Article  MathSciNet  MATH  Google Scholar 

  18. Doherty, P., Łukaszewicz, W., Szałas, A.: Efficient reasoning using the local closed-world assumption. In: Cerri, S.A., Dochev, D. (eds.) AIMSA 2000. LNCS (LNAI), vol. 1904, pp. 49–58. Springer, Heidelberg (2000)

    Chapter  Google Scholar 

  19. Dubois, D.: On ignorance and contradiction considered as truth-values. Logic Journal of the IGPL 16(2), 195–216 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  20. Eiter, T., Gottlob, G.: Propositional circumscription and extended closed-world reasoning are ΠP 2-complete. Theoretical Computer Science 114(2), 231–245 (1993)

    Article  MathSciNet  MATH  Google Scholar 

  21. Etzioni, O., Golden, K., Weld, D.S.: Sound and efficient closed-world reasoning for planning. Artificial Intelligence 89, 113–148 (1997)

    Article  MathSciNet  MATH  Google Scholar 

  22. Fages, F.: Consistency of Clark’s completion and existence of stable models. Methods of Logic in Computer Science 1, 51–60 (1994)

    Google Scholar 

  23. Fitting, M.C.: Fixpoint semantics for logic programming. A survey. Theoretical Computer Science 278(1-2), 25–51 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  24. Gabbay, D.M., Schmidt, R., Szałas, A.: Second-Order Quantifier Elimination. Foundations, Computational Aspects and Applications. Studies in Logic, vol. 12. College Publications (2008)

    Google Scholar 

  25. Gelfond, M., Lifschitz, V.: Classical negation in logic programs and disjunctive databases. New Generation Comput. 9(3/4), 365–386 (1991)

    Article  MATH  Google Scholar 

  26. Ginsberg, M.: Multi-valued logics. In: Proceedings of AAAI 1986, Fifth National Conference on Artificial Intelligence, pp. 243–247 (1986)

    Google Scholar 

  27. Gottlob, G.: Complexity results for nonmonotonic logics. Journal of Logic and Computation 2(3), 397–425 (1992)

    Article  MathSciNet  MATH  Google Scholar 

  28. Kifer, M., Lozinski, E.L.: A logic for reasoning with inconsistency. J. Autom. Reasoning 9(2), 179–215 (1992)

    Article  MathSciNet  MATH  Google Scholar 

  29. Lifschitz, V.: Circumscription. In: Gabbay, D.M., Hogger, C.J., Robinson, J.A. (eds.) Handbook of Artificial Intelligence and Logic Programming, vol. 3, pp. 297–352. Oxford University Press, Oxford (1991)

    Google Scholar 

  30. Łukaszewicz, W.: Non-Monotonic Reasoning - Formalization of Commonsense Reasoning. Ellis Horwood Series in Artificial Intelligence. Ellis Horwood, England (1990)

    Google Scholar 

  31. Małuszyński, J., Szałas, A.: Logical foundations and complexity of 4QL, a query language with unrestricted negation (2010) (to appear); Journal of Applied Non-Classical Logics, http://arxiv.org/abs/1011.5105

  32. Małuszyński, J., Szałas, A., Vitória, A.: Paraconsistent logic programs with four-valued rough sets. In: Chan, C.-C., Grzymala-Busse, J.W., Ziarko, W.P. (eds.) RSCTC 2008. LNCS (LNAI), vol. 5306, pp. 41–51. Springer, Heidelberg (2008)

    Chapter  Google Scholar 

  33. Marek, V.W., Truszczyński, M.: Nonmonotonic Logic. Springer, Heidelberg (1993)

    Book  MATH  Google Scholar 

  34. McCarthy, J.: Circumscription: A form of non-monotonic reasoning. Artificial Intelligence Journal 13, 27–39 (1980)

    Article  MathSciNet  MATH  Google Scholar 

  35. Moore, R.C.: Possible-world semantics for autoepistemic logic. In: Proc. 1st Nonmonotonic Reasoning Workshop, New Paltz, NY, pp. 344–354 (1984)

    Google Scholar 

  36. Nute, D.: Defeasible logic. In: Handbook of Logic in Artificial Intelligence and Logic Programming, pp. 353–395 (1994)

    Google Scholar 

  37. Pawlak, Z.: Rough Sets. Theoretical Aspects of Reasoning about Data. Kluwer Academic Publishers, Dordrecht (1991)

    MATH  Google Scholar 

  38. Reiter, R.: On closed world data bases. In: Gallaire, H., Minker, J. (eds.) Logic and Data Bases, pp. 55–76. Plenum Press, New York (1978)

    Chapter  Google Scholar 

  39. Reiter, R.: A logic for default reasoning. Artificial Intelligence Journal 13, 81–132 (1980)

    Article  MathSciNet  MATH  Google Scholar 

  40. Sakama, C., Inoue, K.: Paraconsistent stable semantics for extended disjunctive programs. J. Log. Comput. 5(3), 265–285 (1995)

    Article  MathSciNet  MATH  Google Scholar 

  41. Vitória, A.: Reasoning with Rough Sets and Paraconsistent Rough Sets. University of Linköping, Ph.D. Thesis (2010), http://urn.kb.se/resolve?urn=urn:nbn:se:liu:diva-60794

  42. Vitória, A., Małuszyński, J., Szałas, A.: Modeling and reasoning with paraconsistent rough sets. Fundamenta Informaticae 97(4), 405–438 (2009)

    MathSciNet  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Computer and Information Science, Linköping University, S-581 83, Linköping, Sweden

    Jan Małuszyński & Andrzej Szałas

  2. Institute of Informatics, Warsaw University, 02-097, Warsaw, Poland

    Andrzej Szałas

Authors
  1. Jan Małuszyński
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Andrzej Szałas
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Department of Computer Science, Oxford University, Wolfson Building, Parks Road, OX1 3QD, Oxford, UK

    Oege de Moor

  2. Department of Computer Science, University of Oxford, UK

    Georg Gottlob , Tim Furche  & Andrew Sellers ,  & 

Rights and permissions

Reprints and permissions

Copyright information

© 2011 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Małuszyński, J., Szałas, A. (2011). Living with Inconsistency and Taming Nonmonotonicity. In: de Moor, O., Gottlob, G., Furche, T., Sellers, A. (eds) Datalog Reloaded. Datalog 2.0 2010. Lecture Notes in Computer Science, vol 6702. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-24206-9_22

Download citation

  • DOI: https://doi.org/10.1007/978-3-642-24206-9_22

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-642-24205-2

  • Online ISBN: 978-3-642-24206-9

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation