Τα συστήματα διαχείρισης βάσεων δεδομένων γραφημάτων έχουν αποκτήσει σημαντική
δημοτικότητα λόγω της εγγενούς τους ικανότητας να αναπαριστούν πληροφορίες από διάφορους τομείς με τη μορφή γράφων. Τα συστήματα διαχείρισης βάσεων δεδομένων γραφημάτων διευκολύνουν την αναπαράσταση δεδομένων που σχετίζονται με κοινωνικά δίκτυα, χημικές ενώσεις και γράφους γνώσης, χρησιμοποιώντας κόμβους, ακμές, ετικέτες και ιδιότητες. Τα συστήματα διαχείρισης βάσεων δεδομένων γραφημάτων που ακολουθούν ένα εγγενές μοντέλο αποθήκευσης γράφων επιδεικνύουν εξαιρετική αποδοτικότητα τόσο στην αποθήκευση δεδομένων όσο και στην απόκριση σε επερωτήματα διάσχισης μέσα σε βάσεις δεδομένων γράφων. Παρόλα αυτά, προκύπτει μια πρόκληση κατά το χειρισμό σύνθετων αναλυτικών επερωτημάτων, γεγονός που καθιστά αναγκαία την ανάπτυξη νέων τεχνικών για την επιτάχυνση της εκτέλεσής τους. Στην παρούσα μελέτη, αντιμετωπίζουμε το ζήτημα της υλοποίησης όψεων για την επιτάχυνση της απάντησης αναλυτικών-ερωτημάτων σε εγγενείς βάσεις δεδομένων γραφημάτων. Πιο συγκεκριμένα, εστιάζουμε στον προσδιορισμό των τύπων όψεων που δύναται να υλοποιηθούν για να επιταχύνουμε την εκτέλεση επερωτημάτων που χαρακτηρίζονται από επαναλαμβανόμενα μοτίβα. Παρουσιάζουμε διάφορες εναλλακτικές όψεις για την βελτίωση του αρχικού μας γράφου και παρέχουμε τεχνικές αναδιατύπωσης ερωτημάτων για την απάντηση σε επερχόμενα επερωτήματα με τη χρήση αυτών των προ-υπολογισμένων προβολών. Η έρευνά μας επικεντρώνεται στα χαρακτηριστικά των επαναλαμβανόμενων μοτίβων εντός του φόρτου εργασίας των επερωτημάτων και διερευνά τη σχέση μεταξύ των χαρακτηριστικών των όψεων και των δίαφορων τύπων ερωτημάτων.
Για να εξετάσουμε την προαναφερθείσα αντιστοιχία, κατασκευάσαμε ένα πρωτότυπο σύ-
στημα που αναγνωρίζει μοτίβα επερωτημάτων χρησιμοποιώντας τεχνικές εξόρυξης συ-
χνών μοτίβων, ενώ παράλληλα χρησιμοποιεί παραλλαγές του προβλήματος Knapsack
για να επιλέξει τις καλύτερες όψεις για ένα δεδομένο φόρτο εργασίας επερωτήματος.
Τα πειράματά μας υπογράμμισαν την υποαπόδοση του επικρατέστερου τύπου όψεων σε
συστήματα διαχείρισης βάσεων δεδομένων γραφημάτων, σε διάφορους τύπους επερω-
τημάτων. Εισάγοντας εναλλακτικές προσεγγίσεις, επιτύχαμε μια αξιοσημείωτη βελτίωση
έως και 4,45 φορές στην αποδοτικότητα εκτέλεσης επερωτημάτων και πάνω από 2 φορές
μείωση του κόστους αποθήκευσης. Αυτό υποδηλώνει ότι η υιοθέτηση ενός πιο ευέλικτου μοντέλου όψεων και ευρετηρίασης μπορεί να αποφέρει σημαντικές βελτιώσεις στην απόδοση των επερωτημάτων και την αποδοτικότητα της αποθήκευσης των όψεων.
(EL)
Graph Database Management Systems (GDMSs) have gained significant popularity due
to their inherent capability to represent information from diverse domains in the form of
graphs. GDMSs facilitate the representation of data related to social networks, chemical compounds, and knowledge graphs, utilizing nodes, edges, labels, and properties. GDMSs that adhere to a native graph storage model demonstrate exceptional efficiency
in both data storage and response to traversal queries within graph databases. Never-
theless, a challenge emerges when handling complex analytical queries within these sys-
tems, necessitating the development of novel techniques to accelerate their execution.
In this study, we tackle the issue of view materialization to expedite analytical-query an-
swering in property-graph databases. More specifically, our focus is on identifying the
types of views that should be materialized to accelerate the execution of queries featuring
recurring patterns. We introduce various view alternatives to augment our initial graph and
provide query rewriting techniques for responding to upcoming queries using these pre-
computed views. Our research centers on the characteristics of recurrent patterns within
the query workload and explores the relationship between view characteristics and query
types. To examine the aforementioned correspondence, we have built a prototype system that identifies query patterns using frequent pattern mining techniques while employing variations of the Knapsack problem to select the best views for a query workload.
Our experimentation underscored the underperformance of subgraph materialization, the
prevailing view type in GDMSs, across various query types. However, by introducing
alternative approaches, we achieved a remarkable enhancement of up to 4.45 times in
query execution efficiency and over a 2x reduction in storage costs. This suggests that
adopting a more flexible view and indexing model can yield significant improvements in
performance and storage efficiency.
(EN)
Εθνικό και Καποδιστριακό Πανεπιστήμιο Αθηνών
