The semantics of incomplete databases as an expression of preferences. (English) Zbl 0716.68029
Summary: We address the problem of incomplete information in deductive databases from a semantic point of view. We want to treat the problem in a homogeneous way, using a formalism which can handle different types of incompleteness. We argue that it is convenient to define an incomplete database as a double entity: an underlying incomplete database together with selection criteria, formally some preference relation on the set of models of the underlying database, intended to reduce the incompleteness. Such an idea has been already exploited in the Perfect Model semantics of Negation as Failure in the stratified databases. We propose another notion of preference which induces a stronger selection of models and captures an intuitive process of “making choices” in disjunctive databases. We study both the declarative and the operational semantics for this notion of preference.
References:
| [1] | Apt, K.; Blair, H.; Walker, A., Towards a theory of declarative knowledge, (Proc. Workshop on Foundations of Deductive Databases (1986)) |
| [2] | Bancilhon, F.; Maier, D., Magic sets and other strange ways to implement logic programs, (Proc. Symp. on Principles of Database Systems (1986)) |
| [3] | Besnard, P.; Siegel, P., The preferential-models approach to non-monotonic logics, (Non-Standard Logics for Automated Reasoning (1988), Academic Press: Academic Press New York), 135-161 |
| [4] | Bidoit, N.; Froidevaux, C., Minimalism subsumes default logic and circumscription, (Proc. Logic in Computer Science (1987), IEEE: IEEE New York) |
| [5] | Bidoit, N.; Froidevaux, C., More on stratified default theories, (Proc. Europ. Conf. on Artificial Intelligence. Proc. Europ. Conf. on Artificial Intelligence, Munich (1988)) |
| [6] | Bossu, G.; Siegel, P., Saturation, non-monotonic reasoning and the closed world assumption, Artificial Intelligence, 25, 1 (1985) · Zbl 0569.68078 |
| [7] | Brown, A.; Shoham, Y., New results on semantical nonmonotonic reasoning, (Proc. 2nd Workshop on Non-Monotonic Reasoning. Proc. 2nd Workshop on Non-Monotonic Reasoning, Grassau. Proc. 2nd Workshop on Non-Monotonic Reasoning. Proc. 2nd Workshop on Non-Monotonic Reasoning, Grassau, Lecture Notes in Artificial Intelligence, 346 (1988), Springer: Springer Berlin), 19-41 · Zbl 0675.03008 |
| [8] | Chang, C. L.; Lee, R., Symbolic Logic and Mechanical Theorem Proving, (Computer Science and Applied Mathematics (1973), Academic Press: Academic Press New York) · Zbl 0263.68046 |
| [9] | Clark, K. L., Negation as Failure, ((1978), Plenum: Plenum New York), 293-322 |
| [10] | Demolombe, R., An efficient strategy for non-Horn deductive databases, (Proc. IFIP. Proc. IFIP, San Francisco (1989)) · Zbl 0716.68027 |
| [11] | Gelfond, M.; Przymusinska, H.; Przymusinski, T., On the relationship between circumscription and negation as failure, Artificial Intelligence, 38, 75-94 (1989) · Zbl 0663.68097 |
| [12] | Kerisit, J. M., La Méthode Alexandre: une Méthode de Déduction, Thèse Université Paris, 7 (1988) |
| [13] | Kowalski, R.; Van Emden, M. H., The semantics of predicate logic as a programming language, J. ACM, 23, 4 (1976) · Zbl 0339.68004 |
| [14] | Lifschitz, V., Closed world databases and circumscription, Artificial Intelligence, 27 (1985) · Zbl 0596.68062 |
| [15] | Lifschitz, V., Circumscriptive theories: a logic-based framework for knowledge representation, (Proc. AAAI, vol. 1 (1987)) |
| [16] | MacCarthy, J., Circumscription: a form of non-monotonic reasoning, Artificial Intelligence, 13, 1,2, 27-39 (1980) · Zbl 0435.68073 |
| [17] | MacCarthy, J., Applications of circumscription to formalizing common-sense knowledge, Artificial Intelligence, 28 (1986) |
| [18] | Makinson, D., General theory of cumulative inference, (Proc. 2nd Workshop on Non-Monotonic Reasoning. Proc. 2nd Workshop on Non-Monotonic Reasoning, Grassau. Proc. 2nd Workshop on Non-Monotonic Reasoning. Proc. 2nd Workshop on Non-Monotonic Reasoning, Grassau, Lecture Notes in Artificial Intelligence, 346 (1988), Springer Verlag: Springer Verlag Berlin), 1-18 · Zbl 0675.03007 |
| [19] | Minker, J., On indefinite databases and the closed world assumption, (Proc. 6th Conf. on Automated Deduction (1982)) · Zbl 0481.68087 |
| [20] | Minker, J.; Rajasekar, A., A fixpoint semantics for non-Horn logic programs, (Technical Report UMIACS-TR-87-24 (1987), University of Maryland, IACS) · Zbl 0713.68016 |
| [21] | Minker, J.; Rajasekar, A., Procedural interpretation of non-Horn logic programs, (Proc. Conf. on Automated Deduction (1988)) · Zbl 0667.68111 |
| [22] | Przymusinski, T., On the declarative semantics of stratified deductive databases, (Proc. Foundations of Deductive Databases and Logic Programming. Proc. Foundations of Deductive Databases and Logic Programming, Washington (1986)) · Zbl 0726.68067 |
| [23] | Przymusinski, T., On the declarative and procedural semantics of logic programs, J. Automat. Reason., 5, 167-205 (1989) · Zbl 0681.68109 |
| [24] | Przymusinski, T., An algorithm to compute circumscription, Artificial Intelligence, 38, 1, 49-74 (1989) · Zbl 0663.68098 |
| [25] | Reiter, R., A logic for default reasoning, Artificial Intelligence, 13, 1,2 (1980) · Zbl 0435.68069 |
| [26] | Rohmer, J.; Lescoeur, R.; Kerisit, J. M., The Alexander Method: a technique for the processing of recursive axioms in deductive databases, New Generation Comput., 3, 4 (1986) · Zbl 0615.68062 |
| [27] | Royer, V., Modeling preference choices in incomplete deductive databases, (Proc. IFIP. Proc. IFIP, San Francisco (1989)) |
| [28] | Royer, V., Backward chaining evaluation in stratified disjunctive databases, Technical Report Esprit Project ESTEAM 316 (Oct. 1989), final deliverable |
| [29] | Shoham, Y., Nonmonotonic logics: meaning and utility, (IJCAI 10. IJCAI 10, Milan (1987)) |
| [30] | Shoham, Y., Reasoning About Change: Time and Causation from the Standpoint of Artificial Intelligence (1988), MIT Press: MIT Press Cambridge, MA |
| [31] | Stoy, J. E., Denotational Semantics: The Scott-Strachey Approach to Programming Language Theory (1977), MIT Press: MIT Press Cambridge, MA · Zbl 0503.68059 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
