More Web Proxy on the site http://driver.im/

Article

Free access

Complexity aspects of various semantics for disjunctive databases

Authors:

Georg GottlobAuthors Info & Claims

PODS '93: Proceedings of the twelfth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems

Pages 158 - 167

https://doi.org/10.1145/153850.153864

Published: 01 August 1993 Publication History

Abstract

This paper addresses complexity issues for important problems arising with disjunctive databases. In particular, the complexity of inference of a literal and a formula from a propositional disjunctive database under a variety of well-known disjunctive database semantics is investigated, as well deciding whether a disjunctive database has a model under a particular semantics. The problems are located in appropriate slots of the polynomial hierarchy.

References

[1]

K. Apt, H. Blair, and A. Walker. Towards a Theory of Declarative Knowledge. In Minker {17}, pages 89-148.

Digital Library

[2]

N. Bidoit and C. Froidevaux. Negation by default and unstratifiable programs. Theoretical Computer Science, 78:85-112, 1991.

Digital Library

[3]

M. Cadoli and M. Lenzerini. The Complexity of Closed World Reasoning and Circumscription. In Proceedings AAAI-90, pages 550-555, 1990.

[4]

M. Cadoli and M. Schaerf. A Survey on Complexity Results for Non-monotonic Logics. Technical report, Dipartimento di Informatica e Sistemistica, Universit#t di Roma "La Sapienza", 1992. Journal of Logic Programming, to appear.

[5]

E. Chart. A Possible Worlds Semantics for Disjunctive Databases. IEEE Transactions on Data and Knowledge Engineering, 1991. To appear.

[6]

A. Chandra and D. Harel. Horn Clause Queries and Generalizations. Journal of Logic Programming, 2:1- 15, 1985.

[7]

T. Eiter and G. Gottlob. Propositional Circumscription and Extended Closed World Reasoning are IIP- complete. Technical Report CD-TR 91/20, Christian Doppler Laboratory for Expert Systems, Vienna University of Technology, Austria, May 1991. To appear in Theoretical Computer Science.

[8]

T. Eiter and G. Gottlob. On the Computational Cost of Disjunctive Logic Programming: Propositional Case. Manuscript, March 1993.

[9]

J. Fern~ndez and J. Minker. Semantics of Disjunctive Deductive Databases. In Proceedings ICDT-9#, pages 21-50, Berlin, October 1992.

Digital Library

[10]

M. Gelfond and V. Lifschitz. The Stable Model Semantics for Logic Programming. In Proceedings Fifth Logic Programming Symposium, pages 1070-1080, C#tmbridge Mass., 1988. MIT Press.

[11]

M. Gelfond and H. Przymusinska. Negation as Failure: Careful Closure Procedure. Artificial Intelligence, 30:273-287, 1986.

Digital Library

[12]

M. Gelfond, H. Przymusinska, and T. Przymusinski. On the Relationship Between Circumscription and Negation as Failure. Artificial Intelligence, 38:75-94, 1989.

Digital Library

[13]

D. S. Johnson. A Catalog of Complexity Classes. In J. van Leeuwen, editor, Handbook of Theoretical Computer Science, volume A, chapter 2. Elsevier Science Publishers B.V. (North-Holl#nd), 1990.

Digital Library

[14]

V. Lifschitz. Computing Circumscription. In Proceedings IJCAI-85, pages 121-127, 1985.

[15]

W. Marek and M. Truszczyfiski. Autoepistemic Logic. Journal of the A CM, 38(3):588-619, 1991.

Digital Library

[16]

J. Minker. On Indefinite Data Bases and the Closed World Assumption. In Proceedings of the 6th Conference on Automated Deduction (CADE}, pages 292- 308, 1982.

Digital Library

[17]

J. Minker, editor. Foundations of Deductive Databases and Logic Programming. Morgan Kaufman, Washington DC, 1988.

Digital Library

[18]

C. H. Papadimitriou and M. Yannakakis. The Complexity of Facets (And Some Facets of Complexity). Journal of Computer and System Sciences, 28:244-259, 1984.

[19]

T. Przymusinski. On the Declarative and Procedural Semantics of Stratified Deductive Databases. In Minker {17}, pages 193-216.

[20]

T. Przymusinski. Stable Semantics for Disjunctive Programs. New Generation Computing, 9:401-424, 1991.

Digital Library

[21]

A. Rajasekar, J. Lobo, and J. Minker. Weak Generalized Closed World Assumption. Journal of Automated Reasoning, 5:293-307, 1989.

Digital Library

[22]

R. Reiter. On Closed-World Databases. In H. Gallaire and J. Minker, editors, Logic and Data Bases, pages 55-76. Plenum Press, New York, 1978.

[23]

K. Ross and R. Topor. Inferring Negative Information From Disjunctive Databases. Journal of Automated Reasoning, 4(2):397-424, 1988.

Digital Library

[24]

C. Sakama. Possible Model Semantics for Disjunctive Databases. In Proceedings 1st lntl. Conf. DOOD-89, pages 337-351, Kyoto Japan, 1989.

[25]

M. Schaerf. Logic Programming and Autoepistemic Logics: New Relations and Complexity Results. Submitted, December 1992.

[26]

M. Schaerf. Negation and Minimality in Non-Horn Databases. In Proceedings PODS-93, 1993.

Digital Library

[27]

J. Schlipf. A Survey of Complexity and Undecidability Results in Logic Programming. In H. Blair, W. Marek, A. Nerode, and J. Remmel, editors, lnfor. real Proceedings of the Workshop on Structural Gomplezity and Recursion-Theoretic Methods in Logic Pro- 9ramming, pages 93-102, Washington DC, November 13 1992. Cornell University, Mathematical Sciences institute.

[28]

A. van Gelder. Negation as Failure Using Tight Derivations for General Logic Programs. In Minker {17}, pages 1149-1176.

Digital Library

[29]

A. van Gelder, K. Ross, and J. Schlipf. The Well- Founded Semantics for General Logic Programs. Journal o{ the A GM, 38(3):620-650, 1991.

Digital Library

[30]

A. Yahya and L. Henschen. Deduction in Non-Horn Databases. Journal o/ A utomated Reasoning, 1(2):141- 160, 1985.

Cited By

Gottlob G(2022)Adventures with Datalog: Walking the Thin Line Between Theory and PracticeAIxIA 2022 – Advances in Artificial Intelligence10.1007/978-3-031-27181-6_34(489-500)Online publication date: 28-Nov-2022
https://dl.acm.org/doi/10.1007/978-3-031-27181-6_34
Grant JMinker J(2007)Deductive DatabasesWiley Encyclopedia of Computer Science and Engineering10.1002/9780470050118.ecse105Online publication date: 14-Dec-2007
https://doi.org/10.1002/9780470050118.ecse105
Minker J(2005)Logic and databases: A 20 year retrospectiveLogic in Databases10.1007/BFb0031734(1-57)Online publication date: 26-Jun-2005
https://doi.org/10.1007/BFb0031734
Show More Cited By

Index Terms

Complexity aspects of various semantics for disjunctive databases
1. Information systems
  1. Data management systems
    1. Database design and models
    2. Database management system engines
2. Theory of computation
  1. Logic
    1. Constraint and logic programming
  2. Semantics and reasoning
    1. Program semantics

Recommendations

A New Partial Semantics for Disjunctive Deductive Databases

We propose a new partial semantics for disjunctive deductive databases that we call disjunctive well-founded semantics. This semantics extends the classical well-founded semantics of normal databases for disjunctive databases. We give a declarative ...
A New Partial Semantics for Disjunctive Deductive Databases

We propose a new partial semantics for disjunctive deductive databases that we call disjunctive well-founded semantics. This semantics extends the classical well-founded semantics of normal databases for disjunctive databases. We give a declarative ...
Using clausal deductive databases for defining semantics in disjunctive deductive databases

This paper investigates the novel concept of i>clausal deductive databases (cd-databases), which are special normal deductive databases - i.e., deductive databases which may contain default negation in rule bodies - over a typed meta-language i>L^...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

PODS '93: Proceedings of the twelfth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems

August 1993

312 pages

ISBN:0897915933

DOI:10.1145/153850

Chairman:
Catriel Beeri

Copyright © 1993 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 August 1993

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

SIGMOD/PODS93

Sponsor:

SIGMOD/PODS93: Joint ACM SIGMOD International Conference on Management of Data and ACM SIGMOD

May 25 - 28, 1993

D.C., Washington, USA

Acceptance Rates

PODS '93 Paper Acceptance Rate 26 of 115 submissions, 23%;

Overall Acceptance Rate 642 of 2,707 submissions, 24%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

26
Total Citations
View Citations
340
Total Downloads

Downloads (Last 12 months)71
Downloads (Last 6 weeks)20

Reflects downloads up to 15 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Gottlob G(2022)Adventures with Datalog: Walking the Thin Line Between Theory and PracticeAIxIA 2022 – Advances in Artificial Intelligence10.1007/978-3-031-27181-6_34(489-500)Online publication date: 28-Nov-2022
https://dl.acm.org/doi/10.1007/978-3-031-27181-6_34
Grant JMinker J(2007)Deductive DatabasesWiley Encyclopedia of Computer Science and Engineering10.1002/9780470050118.ecse105Online publication date: 14-Dec-2007
https://doi.org/10.1002/9780470050118.ecse105
Minker J(2005)Logic and databases: A 20 year retrospectiveLogic in Databases10.1007/BFb0031734(1-57)Online publication date: 26-Jun-2005
https://doi.org/10.1007/BFb0031734
Ruiz CMinker J(2005)Computing stable and partial stable models of extended disjunctive logic programsNon-Monotonic Extensions of Logic Programming10.1007/BFb0030666(205-229)Online publication date: 20-Jun-2005
https://doi.org/10.1007/BFb0030666
Eiter TGottlob GMannila H(2005)Expressive power and complexity of disjunctive datalog under the stable model semanticsManagement and Processing of Complex Data Structures10.1007/3-540-57802-1_5(83-103)Online publication date: 28-May-2005
https://doi.org/10.1007/3-540-57802-1_5
Brewka GDix J(2005)Knowledge Representation with Logic ProgramsHandbook of Philosophical Logic10.1007/1-4020-3092-4_1(1-85)Online publication date: 2005
https://doi.org/10.1007/1-4020-3092-4_1
Bravo LBertossi LWildberger MHalasz MLufiyya HSinger J(2004)Consistent query answering under inclusion dependenciesProceedings of the 2004 conference of the Centre for Advanced Studies on Collaborative research10.5555/1034914.1034930(202-216)Online publication date: 4-Oct-2004
https://dl.acm.org/doi/10.5555/1034914.1034930
Furfaro FGreco GGreco S(2004)Minimal founded semantics for disjunctive logic programs and deductive databasesTheory and Practice of Logic Programming10.1017/S14710684030017044:2(75-93)Online publication date: 1-Jan-2004
https://dl.acm.org/doi/10.1017/S1471068403001704
Loveland DYahya A(2003)SATCHMOREBID: SATCHMO(RE) with BIDirectional relevancyNew Generation Computing10.1007/BF0303747321:3(177-207)Online publication date: 1-Sep-2003
https://dl.acm.org/doi/10.1007/BF03037473
Gelfond M(2002)Representing Knowledge in A-PrologComputational Logic: Logic Programming and Beyond10.1007/3-540-45632-5_16(413-451)Online publication date: 17-Jul-2002
https://doi.org/10.1007/3-540-45632-5_16
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents