Please use this identifier to cite or link to this item:
http://hdl.handle.net/1942/26657
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 | 2018-08-08T10:22:52Z | - |
dc.date.available | 2018-08-08T10:22:52Z | - |
dc.date.issued | 2018 | - |
dc.identifier.citation | Ferrarotti, Flavio; Woltran, Stefan (Ed.). Foundations of Information and Knowledge Systems 10th International Symposium, FoIKS 2018, Budapest, Hungary, May 14–18, 2018, Proceedings, Springer International Publishing AG,p. 225-243 | - |
dc.identifier.isbn | 9783319900490 | - |
dc.identifier.issn | 0302-9743 | - |
dc.identifier.uri | http://hdl.handle.net/1942/26657 | - |
dc.description.abstract | For several practical queries on bags 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 group of at most k objects belongs. We call such queries k-counting-only. Here, we focus on k-SyCALC, k-counting-only queries that are first-order definable. As kSyCALC 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 prove that the k-countingonly 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 International Publishing AG | - |
dc.relation.ispartofseries | Lecture Notes in Computer Science | - |
dc.title | First-order definable counting-only queries | - |
dc.type | Proceedings Paper | - |
local.bibliographicCitation.authors | Ferrarotti, Flavio | - |
local.bibliographicCitation.authors | Woltran, Stefan | - |
local.bibliographicCitation.conferencedate | 14-18/05/2018 | - |
local.bibliographicCitation.conferencename | 10th International Symposium on Foundations of Information and Knowledge Systems (FolKS 2018) | - |
local.bibliographicCitation.conferenceplace | Budapest, Hungary | - |
dc.identifier.epage | 243 | - |
dc.identifier.spage | 225 | - |
dc.identifier.volume | 10833 | - |
local.bibliographicCitation.jcat | C1 | - |
local.publisher.place | Cham, Switzerland | - |
local.type.refereed | Refereed | - |
local.type.specified | Proceedings Paper | - |
local.relation.ispartofseriesnr | 1083 | - |
dc.identifier.doi | 10.1007/978-3-319-90050-6_13 | - |
dc.identifier.isi | 000546329500013 | - |
dc.identifier.eissn | - | |
local.provider.type | Web of Science | - |
local.bibliographicCitation.btitle | Foundations of Information and Knowledge Systems 10th International Symposium, FoIKS 2018, Budapest, Hungary, May 14–18, 2018, Proceedings | - |
item.fullcitation | HELLINGS, Jelle; GYSSENS, Marc; Van Gucht, Dirk & Wu, Yuqing (2018) First-order definable counting-only queries. In: Ferrarotti, Flavio; Woltran, Stefan (Ed.). Foundations of Information and Knowledge Systems 10th International Symposium, FoIKS 2018, Budapest, Hungary, May 14–18, 2018, Proceedings, Springer International Publishing AG,p. 225-243. | - |
item.fulltext | With Fulltext | - |
item.validation | ecoom 2021 | - |
item.contributor | HELLINGS, Jelle | - |
item.contributor | GYSSENS, Marc | - |
item.contributor | Van Gucht, Dirk | - |
item.contributor | Wu, Yuqing | - |
item.accessRights | Open Access | - |
Appears in Collections: | Research publications |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
foiks2018_2_paper.pdf | Peer-reviewed author version | 444.1 kB | Adobe PDF | View/Open |
SCOPUSTM
Citations
2
checked on Sep 2, 2020
WEB OF SCIENCETM
Citations
2
checked on Sep 21, 2024
Page view(s)
126
checked on Sep 7, 2022
Download(s)
244
checked on Sep 7, 2022
Google ScholarTM
Check
Altmetric
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.