ACHILLES, TURTLE, AND UNDECIDABLE BOUNDEDNESS PROBLEMS FOR SMALL DATALOG PROGRAMS.
Saved in:
| Title: | ACHILLES, TURTLE, AND UNDECIDABLE BOUNDEDNESS PROBLEMS FOR SMALL DATALOG PROGRAMS. |
|---|---|
| Authors: | Marcinkowski, Jerzy1 jma@tcs.uni.wroc.pl |
| Source: | SIAM Journal on Computing. 1999, Vol. 29 Issue 1, p231. 27p. |
| Subjects: | Logic programming languages, Query languages (Computer science), Decidability (Mathematical logic), Mathematical optimization |
| Abstract: | DATALOG is the language of logic programs without function symbols. It is considered to be the paradigmatic database query language. If it is possible to eliminate recursion from a DATALOG program then it is bounded. Since bounded programs can be executed in parallel constant time, the possibility of automatized boundedness detecting is believed to be an important issue and has been studied in many papers. Boundedness was proved to be undecidable for different kinds of semantical assumptions and syntactical restrictions. Many different proof techniques were used. In this paper we propose a uniform proof method based on the discovery of, as we call it, the Achilles-Turtle machine, and make strong improvements on most of the known undecidability results. In particular we solve the famous open problem of Kanellakis showing that uniform boundedness is undecidable for single rule programs (called also sirups). This paper is the full version of [J. Marcinkowski, Proc. 13th STACS, Lecture Notes in Computer Science 1046, pp. 427-438], and [J. Marcinkowski, 11th IEEE Symposium on Logic in Computer Science, pp. 13-24]. Key words: DATALOG; query optimization; decidability [ABSTRACT FROM AUTHOR] |
| Copyright of SIAM Journal on Computing is the property of Society for Industrial & Applied Mathematics and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.) | |
| Database: | Engineering Source |
| FullText | Links: – Type: pdflink Text: Availability: 0 |
|---|---|
| Header | DbId: egs DbLabel: Engineering Source An: 10699318 AccessLevel: 6 PubType: Academic Journal PubTypeId: academicJournal PreciseRelevancyScore: 0 |
| IllustrationInfo | |
| Items | – Name: Title Label: Title Group: Ti Data: ACHILLES, TURTLE, AND UNDECIDABLE BOUNDEDNESS PROBLEMS FOR SMALL DATALOG PROGRAMS. – Name: Author Label: Authors Group: Au Data: <searchLink fieldCode="AR" term="%22Marcinkowski%2C+Jerzy%22">Marcinkowski, Jerzy</searchLink><relatesTo>1</relatesTo><i> jma@tcs.uni.wroc.pl</i> – Name: TitleSource Label: Source Group: Src Data: <searchLink fieldCode="JN" term="%22SIAM+Journal+on+Computing%22">SIAM Journal on Computing</searchLink>. 1999, Vol. 29 Issue 1, p231. 27p. – Name: Subject Label: Subjects Group: Su Data: <searchLink fieldCode="DE" term="%22Logic+programming+languages%22">Logic programming languages</searchLink><br /><searchLink fieldCode="DE" term="%22Query+languages+%28Computer+science%29%22">Query languages (Computer science)</searchLink><br /><searchLink fieldCode="DE" term="%22Decidability+%28Mathematical+logic%29%22">Decidability (Mathematical logic)</searchLink><br /><searchLink fieldCode="DE" term="%22Mathematical+optimization%22">Mathematical optimization</searchLink> – Name: Abstract Label: Abstract Group: Ab Data: DATALOG is the language of logic programs without function symbols. It is considered to be the paradigmatic database query language. If it is possible to eliminate recursion from a DATALOG program then it is bounded. Since bounded programs can be executed in parallel constant time, the possibility of automatized boundedness detecting is believed to be an important issue and has been studied in many papers. Boundedness was proved to be undecidable for different kinds of semantical assumptions and syntactical restrictions. Many different proof techniques were used. In this paper we propose a uniform proof method based on the discovery of, as we call it, the Achilles-Turtle machine, and make strong improvements on most of the known undecidability results. In particular we solve the famous open problem of Kanellakis showing that uniform boundedness is undecidable for single rule programs (called also sirups). This paper is the full version of [J. Marcinkowski, Proc. 13th STACS, Lecture Notes in Computer Science 1046, pp. 427-438], and [J. Marcinkowski, 11th IEEE Symposium on Logic in Computer Science, pp. 13-24]. Key words: DATALOG; query optimization; decidability [ABSTRACT FROM AUTHOR] – Name: AbstractSuppliedCopyright Label: Group: Ab Data: <i>Copyright of SIAM Journal on Computing is the property of Society for Industrial & Applied Mathematics and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract.</i> (Copyright applies to all Abstracts.) |
| PLink | https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=egs&AN=10699318 |
| RecordInfo | BibRecord: BibEntity: Identifiers: – Type: doi Value: 10.1137/S0097539797322140 Languages: – Code: eng Text: English PhysicalDescription: Pagination: PageCount: 27 StartPage: 231 Subjects: – SubjectFull: Logic programming languages Type: general – SubjectFull: Query languages (Computer science) Type: general – SubjectFull: Decidability (Mathematical logic) Type: general – SubjectFull: Mathematical optimization Type: general Titles: – TitleFull: ACHILLES, TURTLE, AND UNDECIDABLE BOUNDEDNESS PROBLEMS FOR SMALL DATALOG PROGRAMS. Type: main BibRelationships: HasContributorRelationships: – PersonEntity: Name: NameFull: Marcinkowski, Jerzy IsPartOfRelationships: – BibEntity: Dates: – D: 01 M: 08 Text: 1999 Type: published Y: 1999 Identifiers: – Type: issn-print Value: 00975397 Numbering: – Type: volume Value: 29 – Type: issue Value: 1 Titles: – TitleFull: SIAM Journal on Computing Type: main |
| ResultId | 1 |
