An alternating well-founded semantics for query answering in disjunctive databases | SpringerLink
Skip to main content
Springer Nature Link
Log in

An alternating well-founded semantics for query answering in disjunctive databases

  • Conference paper
  • First Online:
Flexible Query Answering Systems (FQAS 1998)

Part of the book series: Lecture Notes in Computer Science ((LNAI,volume 1495))

Included in the following conference series:

  • 100 Accesses

Abstract

The well-founded semantics has been introduced for normal databases (i.e. databases that may have default negation in their rule bodies, but do not have disjunctions). In this paper we propose an extension of the well-founded semantics to the disjunctive case. For this purpose we investigate the alternating fixpoint approach of Van Gelder, Ross and Schlipf [16], and develop a suitable generalization to the case of disjunctive rule heads.

Given a disjunctive database P, the new alternating well-founded semantics derives a set Adwfs p of partial Herbrand interpretations of P. This set coincides with the set of minimal models if there are no default negations in the database. For general disjunctive databases it is always not empty (if all rule heads are non-empty), i.e. Adwfs p is consistent. The alternating well-founded semantics is very useful for query answering in disjunctive databases. During a fixpoint computation the final set Adwfs p is approximated by a sequence (I n )n∈∕0 of sets I n of partial Herbrand interpretations. At any step of the fixpoint computation it holds: If the query already holds in I n then the query will also hold in Adwfs p, and the computation can be terminated.

For other semantics like the semantics of stable and partial stable models, so far no computations are known that have this property.

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

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

References

  1. S. Brass, J. Dix: Characterizations of the Disjunctive Stable Semantics by Partial Evaluation, Proc. Third Intl. Conf. on Logic Programming an Non-Monotonic Reasoning (LPNMR'95), Springer LNAI 928, 1995, pp. 85–98, and: Journal of Logic Programming, vol. 32(3), 1997, pp. 207–228.

    MathSciNet  Google Scholar 

  2. T. Eiter, N. Leone, D. Sacca: On the Partial Semantics for Disjunctive Deductive Databases, Annals of Mathematics and Artificial Intelligence, to appear.

    Google Scholar 

  3. B.A. Davey, H.A. Priestley: Introduction to Lattices and Order, Cambridge University Press, 1990.

    Google Scholar 

  4. M. Fitting: Bilattices and the Semantics of Logic Programs, Journal of Logic Programming, vol. 11, 1991, pp. 91–116.

    Article  MATH  MathSciNet  Google Scholar 

  5. M. Gelfond, V. Lifschitz: The Stable Model Semantics for Logic Programming, Proc. Fifth Intl. Conference and Symposium on Logic Programming (ICSLP'88), MIT Press, 1988, pp. 1070–1080.

    Google Scholar 

  6. M. Gelfond, V. Lifschitz: Classical Negation in Logic Programs and Disjunctive Databases, New Generation Computing, vol. 9, 1991, pp. 365–385.

    MATH  Google Scholar 

  7. J. W. Lloyd: Foundations of Logic Programming, second edition, Springer, 1987.

    Google Scholar 

  8. J. Lobo, J. Minker, A. Rajasekar: Foundations of Disjunctive Logic Programming, MIT Press, 1992.

    Google Scholar 

  9. T.C. Przymusinski: On the declarative semantics of Deductive Databases and Logic Programming, in: Foundations of Deductive Databases and Logic Programming, J. Minker ed., 1988, pp. 193–216.

    Google Scholar 

  10. T.C. Przymusinski: Extended Stable Semantics for Normal and Disjunctive Programs, Proc. Seventh Intl. Conference on Logic Programming, 1990, pp. 459–477.

    Google Scholar 

  11. T.C. Przymusinski: Stable Semantics for Disjunctive Programs, New Generation Computing, vol. 9, 1991, pp. 401–424.

    Article  MATH  Google Scholar 

  12. D. Seipel:DisLog — A Disjunctive Deductive Database Prototype, Proc. Twelfth Workshop on Logic Programming (WLP'97), 1997, pp. 136–143. DisLog is available on the WWW at ”http://www-infol.informatik.uni-wuerzburg.de/databases/DisLog”.

    Google Scholar 

  13. D. Seipel, J. Minker, C. Ruiz: Model Generation and State Generation for Disjunctive Logic Programs, Journal of Logic Programming, vol. 32(1), 1997, pp. 48–69.

    Article  MathSciNet  Google Scholar 

  14. D. Seipel, J. Minker, C. Ruiz: A Characterization of Partial Stable Models for Disjunctive Deductive Databases, Proc. Intl. Logic Programming Symposium (ILPS'97), MIT Press, 1997, pp. 245–259.

    Google Scholar 

  15. D. Seipel: Partial Evidential Stable Models For Disjunctive Databases, Proc. Workshop on Logic Programming and Knowledge Representation (LPKR'97) at the International Symposium on Logic Programming 1997 (ILPS'97), 1997.

    Google Scholar 

  16. A. Van Gelder, K.A. Ross, J.S. Schlipf:, Unfounded Sets and Well-Founded Semantics for General Logic Programs, Proc. Seventh ACM Symposium on Principles of Database Systems, 1988, pp. 221–230.

    Google Scholar 

  17. C. Witteveen, G. Brewka: Skeptical Reason Maintenance and Belief Revision, Journal of Artificial Intelligence, vol. 61, 1993, pp. 1–36.

    Article  MATH  MathSciNet  Google Scholar 

  18. J.H. You, L. Y. Yuan: Three-Valued Formalisms of Logic Programming: Is It Needed?, Proc. Ninth ACM Symposium on Principles of Database Systems (PODS'90), 1990, pp. 172–182.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. University of Würzburg, Am Hubland, D - 97074, Würzburg, Germany

    Dietmar Seipel

Authors
  1. Dietmar Seipel
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Troels Andreasen Henning Christiansen Henrik Legind Larsen

Rights and permissions

Reprints and permissions

Copyright information

© 1998 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Seipel, D. (1998). An alternating well-founded semantics for query answering in disjunctive databases. In: Andreasen, T., Christiansen, H., Larsen, H.L. (eds) Flexible Query Answering Systems. FQAS 1998. Lecture Notes in Computer Science, vol 1495. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0056015

Download citation

  • DOI: https://doi.org/10.1007/BFb0056015

  • Published:

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-65082-9

  • Online ISBN: 978-3-540-49655-7

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics

Search

Navigation