Semantics of Disjunctive Databases

Jose Alberto Fernandez and Jack Minker

Computer Science Department,
University of Maryland
College Park

The complete paper is available in:

Abstract

A review is presented of work on disjunctive deductive databases. The semantic approach to disjunctive deductive databases as developed by Fernandez and Minker is explored. The method is applied to stratified and stable model semantics for disjunctive deductive databases. The semantics for updating a subclass of disjunctive deductive databases is described.

Bibliography

[ABW88] K.R. Apt, H.A. Blair, and A. Walker. Towards a Theory of Declarative Knowledge. In J. Minker, editor, Foundations of Deductive Databases and Logic Pro- gramming, pages 89-148. Morgan Kaufmann Pub., Washington, D.C., 1988.
[AvE82] K.R. Apt and M.H. van Emden. Contributions to the Theory of Logic Programming. J.ACM, 29(3):841-862, 1982.
[BE89] A. Borgida and D.W. Etherington. Hierarchical knowledge bases and efficient disjunction. In Proc. of the First Intl. Conf. on Principle of Knowledge Representation and Reasoning (KR-89), pages 33-43, Toronto, Canada, 1989.
[Bis81a] J. Biskup. A formal approach to null values in database relations. In J. MinkerH. Gallaire and J. M. Nicolas, editors, Advances in Data Base Theory, volume 1, pages 299-341. Plenum Press, New York, 1981.
[Bis81b] J. Biskup. A foundation of Codd's relational maybe-operations. University Park, 1981. Pennsylvania State Univ.
[BLM89a] C. Baral, J. Lobo, and J. Minker. Generalized disjunctive well-founded semantics for logic programs. Technical report, Dept of Computer Science, Univ. of Maryland, College ParkMd 20742, 1989. To appear in Annals of Math. and AI.
[BLM89b] C. Baral, J. Lobo, and J. Minker. Generalized well-founded semantics for logic programs. In M. E. Stickel, editor, Proc. of Tenth Intl. Conf. on Automated Deduction, pages 102-116, Kaiserslautern, Germany, Jul. 1989. Springer-Verlag.
[BLM90a] C. Baral, J. Lobo, and J. Minker. Generalized disjunctive well-founded semantics for logic programs: Declarative semantics. In M. Zemankova Z. W. Ras and M. L. Emrich, editors, Proc. of Fifth Intl. Symposium on Methodologies for Intelligent Systems, pages 465-473, Charlotte, NC, 1990. North-Holland.
[BLM90b] C. Baral, J. Lobo, and J. Minker. Generalized disjunctive well-founded semantics for logic programs: Procedural semantics. In M. Zemankova Z. W. Ras and M. L. Emrich, editors, Proc. of Fifth Intl. Symposium on Methodologies for Inelligent Systems, pages 456-464, Charlotte, NC, 1990. North-Holland.
[BLM91] C. Baral, J. Lobo, and J. Minker. WF3: A semantics for negation in normal disjunctive logic programs. In Proc. of the 6th Intl. Symposium on Methodologies for Intelligent Systems, Charlotte, NC, 1991.
[BS85] G. Bossu and P. Siegel. Saturation, nonmonotonic reasoning and the closedworld assumption. Artificial Intelligence, 25(1):13-63, Jan. 1985.
[CH85] A. Chandra and D. Harel. Horn clause queries and generalizations. Journal of Logic Programming, 2(1):1-15, Apr. 1985.
[CH88] S. Chi and L. Henschen. Recursive query answering with non-Horn clauses. In E. Lusk and R. Overbeek, editors, Proc. 9th Intl. Conf. on Automated Deduction, pages 294-312, Argonne, IL, May 1988.
[Cha89] E. Chan. A possible world semantics for non-Horn databases, 1989. Univ. of Waterloo, Canada.
[Cla78] K. L. Clark. Negation as Failure. In H. Gallaire and J. Minker, editors, Logic and Data Bases, pages 293-322. Plenum Press, New York, 1978.
[Cod79] E. F. Codd. Extending the database relational model to capture more meaning. Trans. Database Systems, 4(4):397-434, 1979.
[CS90] J. Chomicki and V.S. Subrahmanian. Generalized closed world assumption is ss02-complete. Information Processing Letters, 34:289-291, 1990.
[Dal92] M. Dalal. Some tractable classes of disjunctive logic programs. Technical report, Rutgers Univ., 1992.
[Dec91a] H. Decker. On alternative models, fixpoints and consistency of disjunctive databases, May 1991.
[Dec91b] H. Decker. On the declarative, operational and procedural semantics of disjunctive computational theories. In Proc. of the 2th Intl. Workshop on the Deductive Approach to Information Systems and Databases, Aiguablava, Spain, Sept. 1991. Invited paper.
[FLMS91] J. A. Fernandez, J. Lobo, J. Minker, and V.S. Subrahmanian. Disjunctive LP + integrity constraints = stable models semantics. In L. Lakshmanan, editor, Proc. of the ILPS'91 Workshop on Deductive Databases, pages 110-117, San Diego, CA, Oct. 1991. A full version has been submitted to Annals of Mathematics and Artifitial Intelligence.
[FM91a] J. A. Fernandez and J. Minker. Bottom-up evaluation of Hierarchical Disjunctive Deductive Databases. In K. Furukawa, editor, Logic Programming Proceed- ings of the Eighth International Conference. MIT Press, 1991.
[FM91b] J. A. Fernandez and J. Minker. Computing perfect models of disjunctive stratified databases. In D. Loveland, J. Lobo, and A. Rajasekar, editors, Proc. of the ILPS'91 Workshop on Disjunctive Logic Programs, pages 110-117, San Diego, CA, Oct. 1991. An extended version has been submitted to Annals of Math. and AI.
[FUV83] R. Fagin, J.D. Ullman, and M.Y. Vardi. On the semantics of updates in databases. In Proc. 7th ACM SIGACT/SIGMOD Symposium on Principles of Database Systems, pages 352-365, 1983.
[FUV89] R. Fagin, J. Ullman, and M. Vardi. Contributions to the view update problem. In Proc. of the Sixth Intl. Conf. on Logic Programming, pages 398-415, 1989.
[GHLM92] J. Grant, J. Horty, J. Lobo, and J. Minker. On the semantics of updates in databases. Presented at the Second Intl. Symposium on Artificial Intelligence and Mathematics, Jan. 1992.
[GL88] M. Gelfond and V. Lifschitz. The stable model semantics for logic programming. In Proc. of the 5th Logic Programming Symposium, pages 1070-1080, Assoc. for Logic Programming, MIT Press, Cambridge, Mass, 1988.
[GL90a] M. Gelfond and V. Lifschitz. Logic programs with classical negation. In D.H.D. Warren and P. Szeredi, editors, Logic Programming - Proc. of the Seventh Intl. Conf., pages 579-597. MIT Press, 1990.
[GL90b] A. Guessoum and J. Lloyd. Updating knowledge bases. New Generation Computing, 8:71-89, 1990.
[GL91] A. Guessoum and J. Lloyd. Updating knowledge bases ii. New Generation Computing, 10:73-100, 1991.
[GM78] H. Gallaire and J. Minker, editors. Logic and Databases. Plenum Press, New York, Apr. 1978.
[GMN84] H. Gallaire, J. Minker, and J-M. Nicolas. Logic and databases: A deductive approach. ACM Computing Surveys, 16(2):153-185, Jun. 1984.
[GPP86] M. Gelfond, H. Przymusinska, and T.C. Przymusinski. The extended closed world assumption and its relation to parallel circumscription. Proc. Fifth ACM SIGACT-SIGMOD Symposium on Principles of Database Systems, pages 133- 139, 1986.
[GPP89] M. Gelfond, H. Przymusinska, and T.C. Przymusinski. On the Relationship between Circumscription and Negation as Failure. Artificial Intelligence, 38:75- 94, 1989.
[Gra77] J. Grant. Null values in a relational data base. Information Processing Letters, 6(5):156-157, 1977.
[Hil74] R. Hill. Lush resolution and its completeness. Technical Report DCL Memo 78, Department of Artificial Intelligence, Univ. of Edinburgh, Aug. 1974.
[HP88] L.J. Henschen and H. Park. Compiling the GCWA in Indefinite Databases. In J. Minker, editor, Foundations of Deductive Databases and Logic Programming, pages 395-438. Morgan Kaufmann Pub., Washington, D.C., 1988.
[IL84] T. Imielinski and W. Lipski. Incomplete information in relational databases. J. ACM, 31(4):761-791, 1984.
[Imi91] T. Imielinski. Incomplete deductive databases. Annals of Math. and AI., 3:259- 293, 1991.
[IV89] T. Imielinski and K. Vadaparty. Complexity of Query Processing in Databases with OR-Objects. In Proc. 7th ACM SIGACT/SIGMOD Symposium on Principles of Database Systems, pages 51-65, Phil., PA, Mar. 29-31 1989.
[Kow78] R.A. Kowalski. Logic for data description. In H. Gallaire J. Minker, editor, Logic and Data Bases, pages 77-102. Plenum Press, New York, 1978.
[Lif86] V. Lifschitz. Pointwise circumscription: A preliminary report. AAAI, pages 406-410, 1986.
[Lip81] W. Lipski. On databases with incomplete information. volume 28, pages 41-70. ACM, New York, 1981.
[Llo87] J.W. Lloyd. Foundations of Logic Programming. Springer-Verlag, second edition, 1987.
[LMR92] J. Lobo, J. Minker, and A. Rajasekar. Fundations of Disjunctive Logic Programming. MIT Press, 1992.
[LS90a] K.C. Liu and R. Sunderraman. Indefinite and maybe information in relational databases. ACM Transactions on Database Systems, 15(1):1-39, 1990.
[LS90b] K.-C. Liu and R. Sunderraman. On representing indefinite and maybe information in relational databases: A generalization. In Proc. of IEEE Data Engi- neering, pages 495-502, Los Angeles, Feb. 1990.
[LYW92] J. Lobo, C. Yu, and G. Wang. Computing the transitive closure in disjunctive databases. Technical report, Department of Electrical Engineering and Computer Science, Univ. of Illinois at Chicago, 1992.
[McC80] J. McCarthy. Circumscription - a form of non-monotonic reasoning. Artificial Intelligence, 13(1 and 2):27-39, 1980.
[MG86] J. Minker and J. Grant. Answering queries in indefinite databases and the null value problem. In P. Kanellakis, editor, Advances in Computing Research, pages 247-267. 1986.
[Min82] J. Minker. On indefinite databases and the closed world assumption. In Proc. of 6th Conf. on Automated Deduction, pages 292-308, New York, 1982.
[Min86] J. Minker. Proc. of workshop on foundations of deductive databases and logic programming, Aug. 1986.
[Min88] J. Minker. Perspectives in deductive databases. Journal of Logic Programming, 5:33-60, 1988.
[Min89] J. Minker. Toward a foundation of disjunctive logic programming. In E.L. Lusk and R.A. Overbeek, editors, Proc. North American Conf. on Logic Programming, pages 1215-1235, 1989.
[MR87] J. Minker and A. Rajasekar. A Fixpoint Semantics for Non-Horn Logic Programs. Technical Report CS-TR-1869, Department of Computer Science Univ. of Maryland, College Park, 1987.
[MR90] J. Minker and A. Rajasekar. A fixpoint semantics for disjunctive logic programs. Journal of Logic Programming, 1990.
[Prz88] T. C. Przymusinski. On the declarative semantics of deductive databases and logic programming. In J. Minker, editor, Foundations of Deductive Databases and Logic Programming, chapter 5, pages 193-216. Morgan Kaufmann Pub., Washington, D.C., 1988.
[Prz90a] T. Przymusinski. Stationary semantics for disjunctive logic programs and deductive databases. In S. Debray and M. Hermenegildo, editors, Proc. of the North American Conf. on Logic Programming, pages 40-62, Austin, TX, Oct. 1990.
[Prz90b] T. C. Przymusinski. Extended stable semantics for normal and disjunctive programs. In Proc. of the 7th Intl. Logic Programming Conf., pages 459-477, Jerusalem, 1990. MIT Press. Extended Abstract.
[Rei78] R. Reiter. On Closed World Data Bases. In H. Gallaire and J. Minker, editors, Logic and Data Bases, pages 55-76. Plenum Press, New York, 1978.
[Rei84] R. Reiter. Towards a Logical Reconstruction of Relational Database Theory. Springer-Verlag Pub., New York, 1984.
[Rei86] R. Reiter. A sound and sometimes complete query evaluation algorithm for relational databases with null values. J.ACM, 33(2):349-370, Apr. 1986.
[Rei90] R. Reiter. What should a database know? In Proc. of the 7th Intl. Conf. on Logic Programming, page 765, Jerusalem, 1990. Abstract of Invited Talk.
[Ros89] K. Ross. Well-founded semantics for disjunctive logic programs. In Proc. of the first Intl. Conf. on Deductive and Object Oriented Databases, pages 352-369, Kyoto, Japan, Dec. 1989.
[Sak89] C. Sakama. Possible model semantics for disjunctive databases. In Proc. First Intl. Conf. on Deductive and Object Oriented Databases, pages 337-351, 1989.
[Suc89] M. Such. Minimal models for closed world databases. In Z.W. Ras, editor, Proc. of ISMIS 4, pages 515-522, 1989.
[Ull88a] J. D. Ullman. Principles of Database and Knowledge-Base Systems I. Principles of Computer Science Series. Computer Science Press, Rockville, MD 20850, 1988.
[Ull88b] J. D. Ullman. Principles of Database and Knowledge-Base Systems II. Principles of Computer Science Series. Computer Science Press, Rockville, MD 20850, 1988.
[Van88] A. Van Gelder. Negation as Failure Using Tight Derivations for General Logic Programs. In J. Minker, editor, Foundations of Deductive Databases and Logic Programming, pages 1149-176. Morgan Kaufmann, 1988.
[Var82] M.Y. Vardi. The complexity of relational query languages. pages 137-146, May 1982.
[Vas79] Y. Vassiliou. Null values in data base management: A denotational semantics approach. pages 162-169, Boston, MA, 1979. ACM, New York.
[vEK76] M.H. van Emden and R.A. Kowalski. The Semantics of Predicate Logic as a Programming Language. J.ACM, 23(4):733-742, 1976.
[VRS88] A. Van Gelder, K. Ross, and J.S. Schlipf. Unfounded Sets and Well-founded Semantics for General Logic Programs. In Proc. 7th Symposium on Principles of Database Systems, pages 221-230, 1988.
[YC89] L. Y. Yuan and D.-A. Chiang. A sound and complete query evaluation algorithm for relational databases with disjunctive information. In Proc. of the Eighth Symposium on Principles of Database Systems, pages 66-74. ACM Press, Mar. 1989.
[YH85] A. Yahya and L.J. Henschen. Deduction in Non-Horn Databases. J. Automated Reasoning, 1(2):141-160, 1985.
[Zan84] C. Zaniolo. Database relations with null values. J. Comp. Sys. Sci., 28:142-166, 1984. This article was processed using the LaTEX macro package with LLNCS style