Cardinality Estimation using Label Probability Propagation for Subgraph Matching in Property Graph Databases
Dateien
Datum
Autor:innen
Herausgeber:innen
ISSN der Zeitschrift
Electronic ISSN
ISBN
Bibliografische Daten
Verlag
Schriftenreihe
Auflagebezeichnung
URI (zitierfähiger Link)
DOI (zitierfähiger Link)
Internationale Patentnummer
Link zur Lizenz
Angaben zur Forschungsförderung
Projekt
Open Access-Veröffentlichung
Sammlungen
Core Facility der Universität Konstanz
Titel in einer weiteren Sprache
Publikationstyp
Publikationsstatus
Erschienen in
Zusammenfassung
Estimating query result cardinality is a central task of cost-based database query optimizers, enabling them to identify and avoid excessively large intermediate results. While cardinality estimation has been studied extensively in relational databases, research in the setting of graph databases has been more limited. In this paper, we address the problem of cardinality estimation for subgraph matching on property graph databases. Our novel cardinality estimation technique starts from a small amount of statistical information about node labels and relationship types, which is propagated along the graph query pattern in terms of label probabilities. Additionally, estimation quality can be improved by providing information about labels or properties to our technique, if available. In our experimental evaluation, we compare our approach to state-of-the-art cardinality estimation techniques for subgraph matching for property graph, RDF, and relational databases, and we demonstrate that our technique offers the best trade-off between accuracy and efficiency.
Zusammenfassung in einer weiteren Sprache
Fachgebiet (DDC)
Schlagwörter
Konferenz
Rezension
Zitieren
ISO 690
WÖRTELER, Leonard, Moritz RENFTLE, Theodoros CHONDROGIANNIS, Michael GROSSNIKLAUS, 2022. Cardinality Estimation using Label Probability Propagation for Subgraph Matching in Property Graph Databases. 25th International Conference on Extending Database Technology (EDBT 2022). Edinburgh, UK, 29. März 2022 - 1. Apr. 2022. In: Proceedings 25th International Conference on Extending Database Technology (EDBT 2022). Konstanz: University of Konstanz, 2022, pp. 285-297. Advances in Database Technology. 25,2. eISSN 2367-2005. ISBN 978-3-89318-085-7. Available under: doi: 10.48786/edbt.2022.16BibTex
@inproceedings{Worteler2022Cardi-59450, year={2022}, doi={10.48786/edbt.2022.16}, title={Cardinality Estimation using Label Probability Propagation for Subgraph Matching in Property Graph Databases}, number={25,2}, isbn={978-3-89318-085-7}, publisher={University of Konstanz}, address={Konstanz}, series={Advances in Database Technology}, booktitle={Proceedings 25th International Conference on Extending Database Technology (EDBT 2022)}, pages={285--297}, author={Wörteler, Leonard and Renftle, Moritz and Chondrogiannis, Theodoros and Grossniklaus, Michael} }
RDF
<rdf:RDF xmlns:dcterms="http://purl.org/dc/terms/" xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#" xmlns:bibo="http://purl.org/ontology/bibo/" xmlns:dspace="http://digital-repositories.org/ontologies/dspace/0.1.0#" xmlns:foaf="http://xmlns.com/foaf/0.1/" xmlns:void="http://rdfs.org/ns/void#" xmlns:xsd="http://www.w3.org/2001/XMLSchema#" > <rdf:Description rdf:about="https://kops.uni-konstanz.de/server/rdf/resource/123456789/59450"> <dc:language>eng</dc:language> <dc:creator>Wörteler, Leonard</dc:creator> <dc:contributor>Wörteler, Leonard</dc:contributor> <dc:creator>Chondrogiannis, Theodoros</dc:creator> <dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/> <dcterms:abstract xml:lang="eng">Estimating query result cardinality is a central task of cost-based database query optimizers, enabling them to identify and avoid excessively large intermediate results. While cardinality estimation has been studied extensively in relational databases, research in the setting of graph databases has been more limited. In this paper, we address the problem of cardinality estimation for subgraph matching on property graph databases. Our novel cardinality estimation technique starts from a small amount of statistical information about node labels and relationship types, which is propagated along the graph query pattern in terms of label probabilities. Additionally, estimation quality can be improved by providing information about labels or properties to our technique, if available. In our experimental evaluation, we compare our approach to state-of-the-art cardinality estimation techniques for subgraph matching for property graph, RDF, and relational databases, and we demonstrate that our technique offers the best trade-off between accuracy and efficiency.</dcterms:abstract> <dc:contributor>Renftle, Moritz</dc:contributor> <dc:contributor>Chondrogiannis, Theodoros</dc:contributor> <dc:creator>Renftle, Moritz</dc:creator> <dcterms:issued>2022</dcterms:issued> <bibo:uri rdf:resource="https://kops.uni-konstanz.de/handle/123456789/59450"/> <dc:creator>Grossniklaus, Michael</dc:creator> <dcterms:title>Cardinality Estimation using Label Probability Propagation for Subgraph Matching in Property Graph Databases</dcterms:title> <dcterms:rights rdf:resource="https://rightsstatements.org/page/InC/1.0/"/> <dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2022-12-08T10:03:29Z</dc:date> <dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2022-12-08T10:03:29Z</dcterms:available> <dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/> <dspace:hasBitstream rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/59450/1/Woerteler_2-cakfs3hm4rhy8.pdf"/> <dc:contributor>Grossniklaus, Michael</dc:contributor> <void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/> <foaf:homepage rdf:resource="http://localhost:8080/"/> <dc:rights>terms-of-use</dc:rights> <dcterms:hasPart rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/59450/1/Woerteler_2-cakfs3hm4rhy8.pdf"/> </rdf:Description> </rdf:RDF>