Cardinality Estimation using Label Probability Propagation for Subgraph Matching in Property Graph Databases

Lade...
Vorschaubild
Dateien
Woerteler_2-cakfs3hm4rhy8.pdf
Woerteler_2-cakfs3hm4rhy8.pdfGröße: 845.08 KBDownloads: 224
Datum
2022
Herausgeber:innen
Kontakt
ISSN der Zeitschrift
Electronic ISSN
ISBN
Bibliografische Daten
Verlag
Schriftenreihe
Auflagebezeichnung
ArXiv-ID
Internationale Patentnummer
Angaben zur Forschungsförderung
Projekt
Open Access-Veröffentlichung
Open Access Bookpart
Core Facility der Universität Konstanz
Gesperrt bis
Titel in einer weiteren Sprache
Publikationstyp
Beitrag zu einem Konferenzband
Publikationsstatus
Published
Erschienen 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.16
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)
004 Informatik
Schlagwörter
Konferenz
25th International Conference on Extending Database Technology (EDBT 2022), 29. März 2022 - 1. Apr. 2022, Edinburgh, UK
Rezension
undefined / . - undefined, undefined
Forschungsvorhaben
Organisationseinheiten
Zeitschriftenheft
Datensätze
Zitieren
ISO 690WÖ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.16
BibTex
@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>
Interner Vermerk
xmlui.Submission.submit.DescribeStep.inputForms.label.kops_note_fromSubmitter
Kontakt
URL der Originalveröffentl.
Prüfdatum der URL
Prüfungsdatum der Dissertation
Finanzierungsart
Kommentar zur Publikation
Allianzlizenz
Corresponding Authors der Uni Konstanz vorhanden
Internationale Co-Autor:innen
Universitätsbibliographie
Ja
Begutachtet
Diese Publikation teilen