Conference item
Estimating the cardinality of conjunctive queries over RDF data using graph summarisation
- Abstract:
-
Estimating the cardinality (i.e., the number of answers) of conjunctive queries is particularly difficult in RDF systems: queries over RDF data are navigational and thus tend to involve many joins. We present a new, principled cardinality estimation technique based on graph summarisation. We interpret a summary of an RDF graph using a possible world semantics and formalise the estimation problem as computing the expected cardinality over all RDF graphs represented by the summary, and we present a closed-form formula for computing the expectation of arbitrary queries. We also discuss approaches to RDF graph summarisation. Finally, we show empirically that our cardinality technique is more accurate and more consistent, often by orders of magnitude, than the state of the art.
- Publication status:
- Published
- Peer review status:
- Reviewed (other)
Actions
Access Document
- Files:
-
-
(Preview, Version of record, pdf, 1.3MB, Terms of use)
-
- Publisher copy:
- 10.1145/3178876.3186003
Authors
- Publisher:
- International World Wide Web Conference Committee
- Host title:
- Proceedings of the 2018 World Wide Web Conference
- Journal:
- Web Conference (WWW 2018) More from this journal
- Publication date:
- 2018-04-10
- Acceptance date:
- 2017-12-22
- Event location:
- Lyon, France
- DOI:
- ISBN:
- 9781450356398
- Pubs id:
-
pubs:817592
- UUID:
-
uuid:4cef8f3c-296b-4508-b82a-d5c614997903
- Local pid:
-
pubs:817592
- Source identifiers:
-
817592
- Deposit date:
-
2018-01-11
Terms of use
- Copyright holder:
- International World Wide Web Conference Committee
- Copyright date:
- 2018
- Notes:
- This is a conference paper from The Web Conference, Lyon, France, 23-27 April 2018.
- Licence:
- CC Attribution (CC BY)
If you are the owner of this record, you can report an update to it here: Report update to this record