research-article

Well-founded semantics for extended datalog and ontological reasoning

Authors:

André Hernich,

Clemens Kupke,

Thomas Lukasiewicz,

Georg GottlobAuthors Info & Claims

PODS '13: Proceedings of the 32nd ACM SIGMOD-SIGACT-SIGAI symposium on Principles of database systems

Pages 225 - 236

https://doi.org/10.1145/2463664.2465229

Published: 22 June 2013 Publication History

Get Access

Abstract

The Datalog± family of expressive extensions of Datalog has recently been introduced as a new paradigm for query answering over ontologies, which captures and extends several common description logics. It extends plain Datalog by features such as existentially quantified rule heads and, at the same time, restricts the rule syntax so as to achieve decidability and tractability. In this paper, we continue the research on Datalog±. More precisely, we generalize the well-founded semantics (WFS), as the standard semantics for nonmonotonic normal programs in the database context, to Datalog± programs with negation under the unique name assumption (UNA). We prove that for guarded Datalog± with negation under the standard WFS, answering normal Boolean conjunctive queries is decidable, and we provide precise complexity results for this problem, namely, in particular, completeness for PTIME (resp., 2-EXPTIME) in the data (resp., combined) complexity.

References

[1]

C. Baral and V. S. Subrahmanian. Dualities between alternative semantics for logic programming and nonmonotonic reasoning. J. Autom. Reasoning, 10(3):399--420, 1993.

Crossref

Google Scholar

[2]

A. Calì, G. Gottlob, and M. Kifer. Taming the infinite chase: Query answering under expressive relational constraints. In Proc. KR-2008, pp. 70--80, 2008. Revised version: http://dbai.tuwien.ac.at/staff/gottlob/CGK.pdf.

Google Scholar

[3]

A. Calì, G. Gottlob, and T. Lukasiewicz. A general Datalog-based framework for tractable query answering over ontologies. J. Web Sem., 14:57--83, 2012.

Digital Library

Google Scholar

[4]

A. Calì, G. Gottlob, T. Lukasiewicz,B. Marnette, and A. Pieris: Datalog±: A family of logical knowledge representation and query languages for new applications. In Proc. LICS-2010, pp. 228--242, 2010.

Digital Library

Google Scholar

[5]

D. Calvanese, G. De Giacomo, D. Lembo, M. Lenzerini, and R. Rosati. Tractable reasoning and efficient query answering in description logics: The DL-Lite family. J. Autom. Reasoning, 39(3):385--429, 2007.

Digital Library

Google Scholar

[6]

G. Gottlob, A. Hernich, C. Kupke, and T. Lukasiewicz. Equality-friendly well-founded semantics and applications to description logics. In Proc. AAAI-2012, pp. 757--764, 2012.

Google Scholar

[7]

E. Grädel and I. Walukiewicz. Guarded fixed point logic. In Proc. LICS-1999, pp. 45--54, 1999.

Digital Library

Google Scholar

[8]

C. H. Papadimitriou. Computational Complexity. Addison-Wesley, 1994.

Google Scholar

[9]

A. Poggi, D. Lembo, D. Calvanese, G. De Giacomo, M. Lenzerini, and R. Rosati. Linking data to ontologies. J. Data Semantics, 10:133--173, 2008.

Digital Library

Google Scholar

[10]

J. S. Schlipf. The expressive powers of the logic programming semantics. J.\ Comput. Syst. Sci., 51(1):64--86, 1995.

Digital Library

Google Scholar

[11]

A. van Gelder, K. A. Ross, and J. S. Schlipf. The well-founded semantics for general logic programs. J. ACM, 38(3):620--650, 1991.

Digital Library

Google Scholar

Cited By

View all

Gottlob GHernich AKupke CLukasiewicz T(2021)Stable Model Semantics for Guarded Existential Rules and Description Logics: Decidability and ComplexityJournal of the ACM10.1145/344750868:5(1-87)Online publication date: 22-Oct-2021
https://dl.acm.org/doi/10.1145/3447508
BORGWARDT SFORKEL WKOVTUNOVA A(2021)Temporal Minimal-World Query Answering over Sparse ABoxesTheory and Practice of Logic Programming10.1017/S147106842100011922:2(193-228)Online publication date: 11-Aug-2021
https://doi.org/10.1017/S1471068421000119
Barceló PBerger GGottlob GPieris A(2021)Guarded Ontology-Mediated QueriesHajnal Andréka and István Németi on Unity of Science10.1007/978-3-030-64187-0_2(27-52)Online publication date: 1-Jun-2021
https://doi.org/10.1007/978-3-030-64187-0_2
Show More Cited By

Index Terms

Well-founded semantics for extended datalog and ontological reasoning
1. Information systems
  1. Data management systems
2. Theory of computation
  1. Randomness, geometry and discrete structures
  2. Theory and algorithms for application domains
    1. Database theory
      1. Database query processing and optimization (theory)

Recommendations

Comparisons and computation of well-founded semantics for disjunctive logic programs

Much work has been done on extending the well-founded semantics to general disjunctive logic programs and various approaches have been proposed. However, these semantics are different from each other and no consensus is reached about which semantics is ...
Logical foundations of well-founded semantics
KR'06: Proceedings of the Tenth International Conference on Principles of Knowledge Representation and Reasoning

We propose a solution to a long-standing problem in the foundations of well-founded semantics (WFS) for logic programs. The problem addressed is this: which (non-modal) logic can be considered adequate for well-founded semantics in the sense that its ...
Interdefinability of defeasible logic and logic programming under the well-founded semantics

We provide a method of translating theories of Nute's defeasible logic into logic programs, and a corresponding translation in the opposite direction. Under certain natural restrictions, the conclusions of defeasible theories under the ambiguity ...

Comments

Information & Contributors

Information

Published In

PODS '13: Proceedings of the 32nd ACM SIGMOD-SIGACT-SIGAI symposium on Principles of database systems

June 2013

334 pages

ISBN:9781450320665

DOI:10.1145/2463664

General Chair:
Richard Hull
IBM T.J. Watson Research Center, USA
,
Program Chair:
Wenfei Fan
University of Edinburgh, UK

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]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 22 June 2013

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

SIGMOD/PODS'13

Sponsor:

SIGMOD

SIGMOD/PODS'13: International Conference on Management of Data

June 22 - 27, 2013

New York, New York, USA

Acceptance Rates

PODS '13 Paper Acceptance Rate 24 of 97 submissions, 25%;

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

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

16
Total Citations
View Citations
269
Total Downloads

Downloads (Last 12 months)3
Downloads (Last 6 weeks)0

Reflects downloads up to 01 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Gottlob GHernich AKupke CLukasiewicz T(2021)Stable Model Semantics for Guarded Existential Rules and Description Logics: Decidability and ComplexityJournal of the ACM10.1145/344750868:5(1-87)Online publication date: 22-Oct-2021
https://dl.acm.org/doi/10.1145/3447508
BORGWARDT SFORKEL WKOVTUNOVA A(2021)Temporal Minimal-World Query Answering over Sparse ABoxesTheory and Practice of Logic Programming10.1017/S147106842100011922:2(193-228)Online publication date: 11-Aug-2021
https://doi.org/10.1017/S1471068421000119
Barceló PBerger GGottlob GPieris A(2021)Guarded Ontology-Mediated QueriesHajnal Andréka and István Németi on Unity of Science10.1007/978-3-030-64187-0_2(27-52)Online publication date: 1-Jun-2021
https://doi.org/10.1007/978-3-030-64187-0_2
Bellomarini LLaurenza ESallinger ESherkhonov E(2020)Reasoning Under Uncertainty in Knowledge GraphsRules and Reasoning10.1007/978-3-030-57977-7_9(131-139)Online publication date: 29-Jun-2020
https://dl.acm.org/doi/10.1007/978-3-030-57977-7_9
Borgwardt SForkel W(2019)Closed-World Semantics for Conjunctive Queries with Negation over $$\mathcal {ELH}_\bot $$ OntologiesLogics in Artificial Intelligence10.1007/978-3-030-19570-0_24(371-386)Online publication date: 6-May-2019
https://doi.org/10.1007/978-3-030-19570-0_24
Arenas MGottlob GPieris A(2018)Expressive Languages for Querying the Semantic WebACM Transactions on Database Systems10.1145/323830443:3(1-45)Online publication date: 16-Nov-2018
https://dl.acm.org/doi/10.1145/3238304
Behrend AGriefahn UVoigt HSchmiegelt P(2015)Optimizing continuous queries using update propagation with varying granularitiesProceedings of the 27th International Conference on Scientific and Statistical Database Management10.1145/2791347.2791368(1-12)Online publication date: 29-Jun-2015
https://dl.acm.org/doi/10.1145/2791347.2791368
Alviano MPieris AMilo TCalvanese D(2015)Default Negation for Non-Guarded Existential RulesProceedings of the 34th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems10.1145/2745754.2745758(79-90)Online publication date: 20-May-2015
https://dl.acm.org/doi/10.1145/2745754.2745758
Gottlob GMorak MPieris A(2015)Recent Advances in Datalog$$^\pm $$Reasoning Web. Web Logic Rules10.1007/978-3-319-21768-0_8(193-217)Online publication date: 11-Jul-2015
https://doi.org/10.1007/978-3-319-21768-0_8
Milani MBertossi L(2015)Ontology-Based Multidimensional Contexts with Applications to Quality Data Specification and ExtractionRule Technologies: Foundations, Tools, and Applications10.1007/978-3-319-21542-6_18(277-293)Online publication date: 12-Jul-2015
https://doi.org/10.1007/978-3-319-21542-6_18
Show More Cited By

View Options

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

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Abstract

References

Cited By

Index Terms

Recommendations

Comparisons and computation of well-founded semantics for disjunctive logic programs

Logical foundations of well-founded semantics

Interdefinability of defeasible logic and logic programming under the well-founded semantics

Comments

Information

Published In

Sponsors

Publisher

Publication History

Permissions

Check for updates

Author Tags

Qualifiers

Conference

Acceptance Rates

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

Login options

Full Access

View options

PDF

eReader

Share

Share this Publication link

Share on social media

Affiliations