Article

Converging to the Chase -- A Tool for Finite Controllability

Authors:

Tomasz Gogacz,

Jerzy MarcinkowskiAuthors Info & Claims

LICS '13: Proceedings of the 2013 28th Annual ACM/IEEE Symposium on Logic in Computer Science

Pages 540 - 549

https://doi.org/10.1109/LICS.2013.61

Published: 25 June 2013 Publication History

Get Access

Abstract

We solve a problem, stated in [CGP10], showing that Sticky Datalog exists, defined in the cited paper as an element of the Datalog pm project, has the finite controllability property. In order to do that, we develop a technique, which we believe can have further applications, of approximating Chase(D, cal T), for a database instance D and a set of tuple generating dependencies and data log rules cal T, by an infinite sequence of finite structures, all of them being models of cal T and D.

References

[1]

V. Barany, G. Gottlob, and M. Otto; Querying the guarded fragment; Proceedings LICS 2010 pp. 1-10, 2010.

Digital Library

Google Scholar

[2]

A. Cali, G. Gottlob, and T. Lukasiewicz; A general datalog-based framework for tractable query answering over ontologies; Proceedings of PODS 2009.

Digital Library

Google Scholar

[3]

A. Cali, G. Gottlob, and A. Pieris; Advanced processing for ontological queries; Proceedings of VLDB-10, 3(1):554-565, 2010.

Digital Library

Google Scholar

[4]

A. Cali, G. Gottlob, and A. Pieris; Query Answering under Non-guarded Rules in Datalog+/- ; Web Reasoning and Rule Systems Lecture Notes in Computer Science, 2010, Volume 6333, pp 1-17.

Digital Library

Google Scholar

[5]

T. Gogacz, J. Marcinkowski; On the BDD/FC conjecture; Proceedings PODS 2013, to appear.

Digital Library

Google Scholar

[6]

D. S. Johnson and A. C. Klug; Testing containment of conjunctive queries under functional and inclusion dependencies; JCSS 28(1):167-189, 1984.

Crossref

Google Scholar

[7]

J. Marcinkowski; Undecidability of the Horn clause finite implication problem; Annual Conference on Computer Science Logic, CSL 1995, preprint.

Google Scholar

[8]

J. Marcinkowski, L. Pacholski: Thue trees; Ann. Pure Appl. Logic 119(1-3): 19-59 (2003).

Crossref

Google Scholar

[9]

R. Rosati; On the decidability and finite controllability of query processing in databases with incomplete information; in Proc. PODS 2006, pp. 356-365.

Digital Library

Google Scholar

[10]

S. Rudolph and M. Krötzsch and P. Hitzler; All Elephants are Bigger than All Mice; 21st Description Logic Workshop Dresden, Germany, 2008.

Google Scholar

Cited By

View all

Leone NManna MTerracina GVeltri P(2019)Fast Query Answering over Existential RulesACM Transactions on Computational Logic10.1145/330844820:2(1-48)Online publication date: 27-Mar-2019
https://dl.acm.org/doi/10.1145/3308448
Barcelo PGottlob GPieris AMilo TTan W(2016)Semantic Acyclicity Under ConstraintsProceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems10.1145/2902251.2902302(343-354)Online publication date: 15-Jun-2016
https://dl.acm.org/doi/10.1145/2902251.2902302
Gogacz TMarcinkowski JMilo TTan W(2016)Red Spider Meets a RainwormProceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems10.1145/2902251.2902288(121-134)Online publication date: 15-Jun-2016
https://dl.acm.org/doi/10.1145/2902251.2902288
Show More Cited By

Converging to the Chase -- A Tool for Finite Controllability
1. Theory of computation

Recommendations

On the finite controllability of conjunctive query answering in databases under open-world assumption

In this paper we study queries over relational databases with integrity constraints (ICs). The main problem we analyze is OWA query answering, i.e., query answering over a database with ICs under open-world assumption. The kinds of ICs that we consider ...
Efficiently Enumerating Answers to Ontology-Mediated Queries
PODS '22: Proceedings of the 41st ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems

We study the enumeration of answers to ontology-mediated queries (OMQs) where the ontology is a set of guarded TGDs or formulated in the description logic ELI and the query is a conjunctive query (CQ). In addition to the traditional notion of an answer, ...
Finite Open-world Query Answering with Number Restrictions

Open-world query answering is the problem of deciding, given a set of facts, conjunction of constraints, and query, whether the facts and constraints imply the query. This amounts to reasoning over all instances that include the facts and satisfy the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

LICS '13: Proceedings of the 2013 28th Annual ACM/IEEE Symposium on Logic in Computer Science

June 2013

597 pages

ISBN:9780769550206

Publisher

IEEE Computer Society

United States

Publication History

Published: 25 June 2013

Check for updates

Author Tags

Qualifiers

Article

Acceptance Rates

Overall Acceptance Rate 215 of 622 submissions, 35%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5
Total Citations
View Citations
40
Total Downloads

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

Reflects downloads up to 24 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Leone NManna MTerracina GVeltri P(2019)Fast Query Answering over Existential RulesACM Transactions on Computational Logic10.1145/330844820:2(1-48)Online publication date: 27-Mar-2019
https://dl.acm.org/doi/10.1145/3308448
Barcelo PGottlob GPieris AMilo TTan W(2016)Semantic Acyclicity Under ConstraintsProceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems10.1145/2902251.2902302(343-354)Online publication date: 15-Jun-2016
https://dl.acm.org/doi/10.1145/2902251.2902302
Gogacz TMarcinkowski JMilo TTan W(2016)Red Spider Meets a RainwormProceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems10.1145/2902251.2902288(121-134)Online publication date: 15-Jun-2016
https://dl.acm.org/doi/10.1145/2902251.2902288
Gottlob GLukasiewicz TPieris A(2014)Datalog+/-Proceedings of the Fourteenth International Conference on Principles of Knowledge Representation and Reasoning10.5555/3031929.3032026(682-685)Online publication date: 20-Jul-2014
https://dl.acm.org/doi/10.5555/3031929.3032026
Ibañez-García YLutz CSchneider T(2014)Finite model reasoning in horn description logicsProceedings of the Fourteenth International Conference on Principles of Knowledge Representation and Reasoning10.5555/3031929.3031965(288-297)Online publication date: 20-Jul-2014
https://dl.acm.org/doi/10.5555/3031929.3031965

View Options

Login options

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

Cited By

Recommendations

On the finite controllability of conjunctive query answering in databases under open-world assumption

Efficiently Enumerating Answers to Ontology-Mediated Queries

Finite Open-world Query Answering with Number Restrictions