Please use this identifier to cite or link to this item:
http://hdl.handle.net/1942/29993
Full metadata record
DC Field | Value | Language |
---|---|---|
dc.contributor.author | HELLINGS, Jelle | - |
dc.contributor.author | GYSSENS, Marc | - |
dc.contributor.author | Van Gucht, Dirk | - |
dc.contributor.author | Wu, Yuqing | - |
dc.date.accessioned | 2019-11-18T08:29:15Z | - |
dc.date.available | 2019-11-18T08:29:15Z | - |
dc.date.issued | 2019 | - |
dc.identifier.citation | ANNALS OF MATHEMATICS AND ARTIFICIAL INTELLIGENCE, 87(1-2), p. 109-136 | - |
dc.identifier.issn | 1012-2443 | - |
dc.identifier.uri | http://hdl.handle.net/1942/29993 | - |
dc.description.abstract | Many data sources can be represented easily by collections of sets of objects. For several practical queries on such collections of sets of objects, the answer does not depend on the precise composition of these sets, but only on the number of sets to which each object belongs. This is the case k= 1 for the more general situation where the query answer only depends on the number of sets to which each collection of at most k objects belongs. We call such queries k-counting-only. Here, we focus on k-SyCALC, i.e., k-counting-only queries that are first-order definable. As k-SyCALC is semantically defined, however, it is not surprising that it is already undecidable whether a first-order query is in 1-SyCALC. Therefore, we introduce SimpleCALC-k, a syntactically defined (strict) fragment of k-SyCALC. It turns out that many practical queries in k-SyCALC can already be expressed in SimpleCALC- k. We also define the query language GCount- k, which expresses counting-only queries directly by using generalized counting terms, and show that this language is equivalent to SimpleCALC-k. We prove that the k-counting-only queries form a non-collapsing hierarchy: for every k, there exist (k+ 1)-counting-only queries that are not k-counting-only. This result specializes to both SimpleCALC- k and k-SyCALC. Finally, we establish a strong dichotomy between 1-SyCALC and SimpleCALC- k on the one hand and 2-SyCALC on the other hand by showing that satisfiability, validity, query containment, and query equivalence are decidable for the former two languages, but not for the latter one. | - |
dc.description.sponsorship | This material is based on work supported by the National Science Foundation under Grant No. NSF 1438990. | - |
dc.language.iso | en | - |
dc.publisher | SPRINGER | - |
dc.rights | Springer Nature Switzerland AG 2019 | - |
dc.subject.other | Bag of sets; Counting-only query; First-order definable query; Satisfiability | - |
dc.subject.other | Bag of sets; Counting-only query; First-order definable query; Satisfiability | - |
dc.title | First-order definable counting-only queries | - |
dc.type | Journal Contribution | - |
dc.identifier.epage | 136 | - |
dc.identifier.issue | 1-2 | - |
dc.identifier.spage | 109 | - |
dc.identifier.volume | 87 | - |
local.format.pages | 28 | - |
local.bibliographicCitation.jcat | A1 | - |
dc.description.notes | [Hellings, Jelle] Univ Calif Davis, Dept Comp Sci, Exploratory Syst Lab, Davis, CA 95616 USA. [Hellings, Jelle; Gyssens, Marc] Hasselt Univ, Fac Sci, Martelarenlaan 42, B-3500 Hasselt, Belgium. [Van Gucht, Dirk] Indiana Univ, Sch Informat Comp & Engn, 919 E 10th St, Bloomington, IN 47408 USA. [Wu, Yuqing] Pomona Coll, 185 E 6th St, Claremont, CA 91711 USA. | - |
local.publisher.place | DORDRECHT | - |
local.type.refereed | Refereed | - |
local.type.specified | Article | - |
dc.identifier.doi | 10.1007/s10472-019-09652-8 | - |
dc.identifier.isi | 000491609600005 | - |
item.validation | ecoom 2020 | - |
item.contributor | HELLINGS, Jelle | - |
item.contributor | GYSSENS, Marc | - |
item.contributor | Van Gucht, Dirk | - |
item.contributor | Wu, Yuqing | - |
item.accessRights | Open Access | - |
item.fullcitation | HELLINGS, Jelle; GYSSENS, Marc; Van Gucht, Dirk & Wu, Yuqing (2019) First-order definable counting-only queries. In: ANNALS OF MATHEMATICS AND ARTIFICIAL INTELLIGENCE, 87(1-2), p. 109-136. | - |
item.fulltext | With Fulltext | - |
crisitem.journal.issn | 1012-2443 | - |
crisitem.journal.eissn | 1573-7470 | - |
Appears in Collections: | Research publications |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
hellings 1.pdf Restricted Access | Published version | 757.82 kB | Adobe PDF | View/Open Request a copy |
paper-revised2.pdf | Peer-reviewed author version | 443.82 kB | Adobe PDF | View/Open |
Page view(s)
162
checked on Sep 7, 2022
Download(s)
252
checked on Sep 7, 2022
Google ScholarTM
Check
Altmetric
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.