Abstract
A natural way to formalize certain incomplete information in databases is through the use of disjunctions, for example A ∨ B. Typically, the meaning of such indefinite information is based on the classical interpretation of the connective ∨, We argue in this paper that this treatment is not strong enough for dealing with a large class of indefinite information. Instead, we propose an intuitively more meaningful definition in which asserting a disjunction also invaliudates any subsumed disjunction, hence exhibiting a non-monotonic behavior. First, we examine a class of databases that can be stratified in a way similar to [1]. For this class of databases, we derive a meaning that coincides with the above motivation. Next, we present an algorithm for transforming an arbitrary database P to a set of stratifiable databases from which the meaning of P is obtained. It turns out that computing answers under this semantics can be done in polynomial time.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
K.R. Apt, H.A. Blair, A. Walker, Towards a Theory of Declarative Knowledge, in: Foundations of Deductive Databases and Logic Programming (J. Minker ed.), 1988.
C. Baral, J. Lobo, and J. Minker, Generalized Disjunctive Well-founded Semantics for Logic Programs, Technical Report, University of Maryland, 1989.
T. Imielinski, K. Vadaparty, Complexity of Query Processing in Databases with OR-Objects, in: Proceedings of the 8th ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Databases Systems, 51–65, 1989.
G. Gottlob, R. Zicari, Closed World Databases Opened Through Null Values, in: Proceedings of the 14th VLDB, 50–61, 1988.
T. Imielinski, Incomplete Deductive Databases, Annals of Mathematics and Artificial4 Intelligence, 3(2–4), 259–293, 1991.
Y. Liu, Null Values in Definite Programs, in: Proceedings of The North American Conference on Logic Programming, 273–288, 1990.
J.W. Lloyd, Foundations of Logic Programming. Springer-Verlag, 1987.
J. Minker, On Indefinite Databases and the Closed World Assumption, in: Proceedings of the 6th International Conference on Automated Deduction, LNCS 138, Springer, 292–308, 1982.
J. Minker, A. Rajasekar, A Fixpoint Semantics for Disjunctive Logic Programs, in: Journal of Logic Programming, 9, 45–74, 1990.
T.C. Przymusinski, Stationary Semantics for Disjunctive Logic Programs and Deductive Databases, Logic Programming: Proceedings of the 1990 North American Conference, (S. Debray and M. Hermenegildo eds.), 40–59.
S. Read, Relevant Logic, Basil Blackwell, 1989.
K.A. Ross, R.W. Topor, Inferring Negative Information from Disjunctive Databases, in: Journal of Automated Reasoning, 4, 397–424, 1988.
M.H. van Emden and R.A. Kowalski, The Semantics of Predicate Logic as a Programming Language, JACM, 23(4), T23–742, 1976.
A. Van Gelder, K. Ross, J.S. Schlipf, The Well-Founded Semantics for General Logic Programs in: JACM, 38(3), 620–650, 1991.
C. Zaniolo, Database Relations with Null Values, in: Journal of Computer and System Sciences, 28, 1984.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1992 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Barback, M.D., Lobo, J., Lu, J.J. (1992). Minimizing indefinite information in disjunctive deductive databases. In: Biskup, J., Hull, R. (eds) Database Theory — ICDT '92. ICDT 1992. Lecture Notes in Computer Science, vol 646. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-56039-4_45
Download citation
DOI: https://doi.org/10.1007/3-540-56039-4_45
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-56039-5
Online ISBN: 978-3-540-47360-2
eBook Packages: Springer Book Archive