Σε αυτό το άρθρο θα μιλήσουμε για λειτουργικές εξαρτήσεις σε βάσεις δεδομένων - τι είναι, πού χρησιμοποιούνται και ποιοι αλγόριθμοι υπάρχουν για να τις βρουν.
Θα εξετάσουμε τις λειτουργικές εξαρτήσεις στο πλαίσιο των σχεσιακών βάσεων δεδομένων. Για να το θέσω πολύ χοντρικά, σε τέτοιες βάσεις δεδομένων οι πληροφορίες αποθηκεύονται με τη μορφή πινάκων. Στη συνέχεια, χρησιμοποιούμε κατά προσέγγιση έννοιες που δεν είναι εναλλάξιμες στην αυστηρή θεωρία σχέσεων: θα ονομάσουμε τον ίδιο τον πίνακα σχέση, τις στήλες - χαρακτηριστικά (το σύνολο τους - ένα σχήμα σχέσης) και το σύνολο τιμών γραμμής σε ένα υποσύνολο χαρακτηριστικών - μια πλειάδα.
Για παράδειγμα, στον παραπάνω πίνακα, (Benson, M, M όργανο) είναι μια πλειάδα χαρακτηριστικών (Ασθενής, Παύλος, Γιατρός).
Πιο επίσημα, αυτό γράφεται ως εξής: [Ασθενής, Φύλο, Γιατρός] = (Benson, M, M όργανο).
Τώρα μπορούμε να εισαγάγουμε την έννοια της λειτουργικής εξάρτησης (FD):
Ορισμός 1. Η σχέση R ικανοποιεί τον ομοσπονδιακό νόμο X → Y (όπου X, Y ⊆ R) εάν και μόνο εάν για οποιεσδήποτε πλειάδες , ∈ Το R ισχύει: αν [X] = [X], λοιπόν [Y] = [Y]. Σε αυτή την περίπτωση, λέμε ότι το X (ο ορίζων ή το καθοριστικό σύνολο χαρακτηριστικών) καθορίζει λειτουργικά το Y (το εξαρτημένο σύνολο).
Με άλλα λόγια, η παρουσία ομοσπονδιακού νόμου Χ → Υ σημαίνει ότι αν έχουμε δύο πλειάδες μέσα R και ταιριάζουν σε ιδιότητες X, τότε θα συμπίπτουν στις ιδιότητες Y.
Και τώρα, με τη σειρά. Ας δούμε τις ιδιότητες Ασθενής и Φύλο για τα οποία θέλουμε να μάθουμε αν υπάρχουν εξαρτήσεις μεταξύ τους ή όχι. Για ένα τέτοιο σύνολο χαρακτηριστικών, ενδέχεται να υπάρχουν οι ακόλουθες εξαρτήσεις:
- Ασθενής → Φύλο
- Φύλο → Ασθενής
Όπως ορίζεται παραπάνω, για να διατηρείται η πρώτη εξάρτηση, κάθε μοναδική τιμή στήλης Ασθενής μόνο μία τιμή στήλης πρέπει να ταιριάζει Φύλο. Και για τον πίνακα του παραδείγματος αυτό είναι πράγματι έτσι. Ωστόσο, αυτό δεν λειτουργεί προς την αντίθετη κατεύθυνση, δηλαδή, η δεύτερη εξάρτηση δεν ικανοποιείται και η ιδιότητα Φύλο δεν είναι καθοριστικό για Υπομονετικος. Ομοίως, αν πάρουμε την εξάρτηση Γιατρός → Ασθενής, μπορείτε να δείτε ότι παραβιάζεται, αφού η τιμή κοκκινολαίμης αυτό το χαρακτηριστικό έχει πολλές διαφορετικές έννοιες - Έλις και Γκράχαμ.
Έτσι, οι λειτουργικές εξαρτήσεις καθιστούν δυνατό τον προσδιορισμό των υπαρχουσών σχέσεων μεταξύ συνόλων χαρακτηριστικών πίνακα. Από εδώ και πέρα θα εξετάσουμε τις πιο ενδιαφέρουσες συνδέσεις, ή μάλλον τέτοιες Χ → Υτί είναι:
- μη τετριμμένο, δηλαδή, η δεξιά πλευρά της εξάρτησης δεν είναι υποσύνολο της αριστερής (Y ̸⊆ X);
- ελάχιστη, δηλαδή δεν υπάρχει τέτοια εξάρτηση Ζ → ΥΌτι Z ⊂ X.
Οι εξαρτήσεις που θεωρήθηκαν μέχρι αυτό το σημείο ήταν αυστηρές, δηλαδή δεν προέβλεπαν παραβιάσεις στο τραπέζι, αλλά εκτός από αυτές, υπάρχουν και εκείνες που επιτρέπουν κάποια ασυνέπεια μεταξύ των τιμών των πλειάδων. Τέτοιες εξαρτήσεις τοποθετούνται σε μια ξεχωριστή κλάση, που ονομάζεται κατά προσέγγιση, και επιτρέπεται να παραβιάζονται για έναν ορισμένο αριθμό πλειάδων. Αυτό το ποσό ρυθμίζεται από την ένδειξη μέγιστου σφάλματος emax. Για παράδειγμα, το ποσοστό σφάλματος = 0.01 μπορεί να σημαίνει ότι η εξάρτηση μπορεί να παραβιαστεί κατά 1% των διαθέσιμων πλειάδων στο εξεταζόμενο σύνολο χαρακτηριστικών. Δηλαδή, για 1000 εγγραφές, το πολύ 10 πλειάδες μπορεί να παραβιάζουν τον ομοσπονδιακό νόμο. Θα εξετάσουμε μια ελαφρώς διαφορετική μέτρηση, με βάση τις κατά ζεύγη διαφορετικές τιμές των πλειάδων που συγκρίνονται. Για τον εθισμό Χ → Υ στη στάση r θεωρείται ως εξής:
Ας υπολογίσουμε το σφάλμα για Γιατρός → Ασθενής από το παραπάνω παράδειγμα. Έχουμε δύο πλειάδες των οποίων οι τιμές διαφέρουν στο χαρακτηριστικό Ασθενής, αλλά συμπίπτουν στις Γιατρός: [Γιατρός, ασθενής] = (Ρόμπιν, Έλις) Και [Γιατρός, ασθενής] = (Ρόμπιν, Γκράχαμ). Μετά τον ορισμό του σφάλματος, πρέπει να λάβουμε υπόψη όλα τα ζεύγη που βρίσκονται σε σύγκρουση, πράγμα που σημαίνει ότι θα υπάρχουν δύο από αυτά: (, ) και η αντιστροφή του (, ). Ας το αντικαταστήσουμε στον τύπο και πάρουμε:
Τώρα ας προσπαθήσουμε να απαντήσουμε στην ερώτηση: "Γιατί είναι όλα αυτά;" Στην πραγματικότητα, οι ομοσπονδιακοί νόμοι είναι διαφορετικοί. Ο πρώτος τύπος είναι εκείνες οι εξαρτήσεις που καθορίζονται από τον διαχειριστή στο στάδιο του σχεδιασμού της βάσης δεδομένων. Συνήθως είναι λίγα σε αριθμό, αυστηρά και η κύρια εφαρμογή είναι η κανονικοποίηση δεδομένων και ο σχεδιασμός σχεσιακών σχημάτων.
Ο δεύτερος τύπος είναι οι εξαρτήσεις, οι οποίες αντιπροσωπεύουν «κρυφά» δεδομένα και προηγουμένως άγνωστες σχέσεις μεταξύ των χαρακτηριστικών. Δηλαδή, τέτοιες εξαρτήσεις δεν είχαν σκεφτεί τη στιγμή του σχεδιασμού και βρίσκονται για το υπάρχον σύνολο δεδομένων, έτσι ώστε αργότερα, με βάση τους πολλούς αναγνωρισμένους ομοσπονδιακούς νόμους, να εξαχθούν συμπεράσματα σχετικά με τις αποθηκευμένες πληροφορίες. Με αυτές ακριβώς τις εξαρτήσεις εργαζόμαστε. Αντιμετωπίζονται από ένα ολόκληρο πεδίο εξόρυξης δεδομένων με διάφορες τεχνικές αναζήτησης και αλγόριθμους που χτίζονται στη βάση τους. Ας καταλάβουμε πώς οι εξαρτήσεις λειτουργίας που βρέθηκαν (ακριβείς ή κατά προσέγγιση) σε οποιαδήποτε δεδομένα μπορούν να είναι χρήσιμες.
Σήμερα, μία από τις κύριες εφαρμογές των εξαρτήσεων είναι ο καθαρισμός δεδομένων. Περιλαμβάνει την ανάπτυξη διαδικασιών για τον εντοπισμό «βρώμικων δεδομένων» και στη συνέχεια τη διόρθωσή τους. Εξέχοντα παραδείγματα "βρώμικων δεδομένων" είναι διπλότυπα, λάθη δεδομένων ή τυπογραφικά λάθη, τιμές που λείπουν, παλιά δεδομένα, επιπλέον κενά και παρόμοια.
Παράδειγμα σφάλματος δεδομένων:
Παράδειγμα διπλότυπων δεδομένων:
Για παράδειγμα, έχουμε έναν πίνακα και ένα σύνολο ομοσπονδιακών νόμων που πρέπει να εκτελεστούν. Ο καθαρισμός δεδομένων σε αυτήν την περίπτωση περιλαμβάνει αλλαγή των δεδομένων έτσι ώστε οι ομοσπονδιακοί νόμοι να γίνουν σωστοί. Σε αυτήν την περίπτωση, ο αριθμός των τροποποιήσεων θα πρέπει να είναι ελάχιστος (αυτή η διαδικασία έχει τους δικούς της αλγόριθμους, στους οποίους δεν θα εστιάσουμε σε αυτό το άρθρο). Παρακάτω είναι ένα παράδειγμα τέτοιου μετασχηματισμού δεδομένων. Αριστερά είναι η αρχική σχέση, στην οποία, προφανώς, δεν πληρούνται τα απαραίτητα FL (ένα παράδειγμα παραβίασης ενός από τα FL επισημαίνεται με κόκκινο χρώμα). Στα δεξιά είναι η ενημερωμένη σχέση, με τα πράσινα κελιά να δείχνουν τις αλλαγμένες τιμές. Μετά από αυτή τη διαδικασία άρχισαν να διατηρούνται οι απαραίτητες εξαρτήσεις.
Μια άλλη δημοφιλής εφαρμογή είναι ο σχεδιασμός βάσεων δεδομένων. Εδώ αξίζει να υπενθυμίσουμε τις κανονικές μορφές και την κανονικοποίηση. Η κανονικοποίηση είναι η διαδικασία της συμμόρφωσης μιας σχέσης με ένα συγκεκριμένο σύνολο απαιτήσεων, καθεμία από τις οποίες ορίζεται από την κανονική μορφή με τον δικό της τρόπο. Δεν θα περιγράψουμε τις απαιτήσεις διαφόρων κανονικών μορφών (αυτό γίνεται σε οποιοδήποτε βιβλίο σε ένα μάθημα βάσης δεδομένων για αρχάριους), αλλά θα σημειώσουμε μόνο ότι καθένα από αυτά χρησιμοποιεί την έννοια των λειτουργικών εξαρτήσεων με τον δικό του τρόπο. Εξάλλου, τα FL είναι εγγενώς περιορισμοί ακεραιότητας που λαμβάνονται υπόψη κατά το σχεδιασμό μιας βάσης δεδομένων (στο πλαίσιο αυτής της εργασίας, τα FL ονομάζονται μερικές φορές υπερκλειδιά).
Ας εξετάσουμε την αίτησή τους για τις τέσσερις κανονικές μορφές στην παρακάτω εικόνα. Θυμηθείτε ότι η κανονική φόρμα Boyce-Codd είναι πιο αυστηρή από την τρίτη μορφή, αλλά λιγότερο αυστηρή από την τέταρτη. Δεν εξετάζουμε το τελευταίο προς το παρόν, καθώς η διατύπωσή του απαιτεί κατανόηση εξαρτήσεων πολλαπλών τιμών, οι οποίες δεν μας ενδιαφέρουν σε αυτό το άρθρο.
Ένας άλλος τομέας στον οποίο οι εξαρτήσεις έχουν βρει την εφαρμογή τους είναι η μείωση της διάστασης του χώρου χαρακτηριστικών σε εργασίες όπως η κατασκευή ενός απλού ταξινομητή Bayes, ο εντοπισμός σημαντικών χαρακτηριστικών και η επαναπαραμετροποίηση ενός μοντέλου παλινδρόμησης. Στα αρχικά άρθρα, αυτή η εργασία ονομάζεται προσδιορισμός περιττής και συνάφειας χαρακτηριστικών [5, 6] και επιλύεται με την ενεργή χρήση των εννοιών της βάσης δεδομένων. Με την εμφάνιση τέτοιων έργων, μπορούμε να πούμε ότι σήμερα υπάρχει ζήτηση για λύσεις που μας επιτρέπουν να συνδυάσουμε τη βάση δεδομένων, την ανάλυση και την υλοποίηση των παραπάνω προβλημάτων βελτιστοποίησης σε ένα εργαλείο [7, 8, 9].
Υπάρχουν πολλοί αλγόριθμοι (και σύγχρονοι και όχι τόσο σύγχρονοι) για την αναζήτηση ομοσπονδιακών νόμων σε ένα σύνολο δεδομένων. Τέτοιοι αλγόριθμοι μπορούν να χωριστούν σε τρεις ομάδες:
- Αλγόριθμοι που χρησιμοποιούν διέλευση αλγεβρικών δικτυωμάτων (Λαττιδικοί αλγόριθμοι διέλευσης)
- Αλγόριθμοι που βασίζονται στην αναζήτηση συμφωνημένων τιμών (αλγόριθμοι διαφοράς και συνόλου συμφωνιών)
- Αλγόριθμοι που βασίζονται σε συγκρίσεις κατά ζεύγη (Αλγόριθμοι επαγωγής εξάρτησης)
Μια σύντομη περιγραφή κάθε τύπου αλγορίθμου παρουσιάζεται στον παρακάτω πίνακα:
Μπορείτε να διαβάσετε περισσότερα για αυτήν την ταξινόμηση [4]. Ακολουθούν παραδείγματα αλγορίθμων για κάθε τύπο:
Επί του παρόντος, εμφανίζονται νέοι αλγόριθμοι που συνδυάζουν διάφορες προσεγγίσεις για την εύρεση λειτουργικών εξαρτήσεων. Παραδείγματα τέτοιων αλγορίθμων είναι τα Pyro [2] και HyFD [3]. Μια ανάλυση της δουλειάς τους αναμένεται στα επόμενα άρθρα αυτής της σειράς. Σε αυτό το άρθρο, θα εξετάσουμε μόνο τις βασικές έννοιες και τα λήμματα που είναι απαραίτητα για την κατανόηση των τεχνικών ανίχνευσης εξαρτήσεων.
Ας ξεκινήσουμε με ένα απλό σύνολο - διαφορά και συμφωνία, που χρησιμοποιείται στον δεύτερο τύπο αλγορίθμων. Το σύνολο διαφορών είναι ένα σύνολο πλειάδων που δεν έχουν τις ίδιες τιμές, ενώ το σύνολο συμφωνιών, αντίθετα, είναι πλειάδες που έχουν τις ίδιες τιμές. Αξίζει να σημειωθεί ότι σε αυτή την περίπτωση εξετάζουμε μόνο την αριστερή πλευρά της εξάρτησης.
Μια άλλη σημαντική έννοια που συναντήθηκε παραπάνω είναι το αλγεβρικό πλέγμα. Δεδομένου ότι πολλοί σύγχρονοι αλγόριθμοι λειτουργούν με αυτήν την έννοια, πρέπει να έχουμε μια ιδέα για το τι είναι.
Για να εισαγάγουμε την έννοια του πλέγματος, είναι απαραίτητο να ορίσουμε ένα μερικώς διατεταγμένο σύνολο (ή μερικώς διατεταγμένο σύνολο, συντομευμένο ως poset).
Ορισμός 2. Ένα σύνολο S λέγεται ότι είναι μερικώς διατεταγμένο από τη δυαδική σχέση ⩽ εάν για όλα τα a, b, c ∈ S ικανοποιούνται οι ακόλουθες ιδιότητες:
- Ανακλαστικότητα, δηλαδή ένα ⩽ α
- Αντισυμμετρία, δηλαδή αν a ⩽ b και b ⩽ a, τότε a = b
- Μεταβατικότητα, δηλαδή, για a ⩽ b και b ⩽ c προκύπτει ότι a ⩽ c
Μια τέτοια σχέση ονομάζεται σχέση μερικής τάξης (χαλαρή) και το ίδιο το σύνολο ονομάζεται μερικώς διατεταγμένο σύνολο. Επίσημος συμβολισμός: ⟨S, ⩽⟩.
Ως το απλούστερο παράδειγμα ενός μερικώς διατεταγμένου συνόλου, μπορούμε να πάρουμε το σύνολο όλων των φυσικών αριθμών N με τη συνήθη σχέση τάξης ⩽. Είναι εύκολο να επαληθευτεί ότι πληρούνται όλα τα απαραίτητα αξιώματα.
Ένα πιο ουσιαστικό παράδειγμα. Θεωρήστε το σύνολο όλων των υποσυνόλων {1, 2, 3}, ταξινομημένα με τη σχέση συμπερίληψης ⊆. Πράγματι, αυτή η σχέση ικανοποιεί όλες τις συνθήκες μερικής παραγγελίας, επομένως το ⟨P ({1, 2, 3}), ⊆⟩ είναι ένα μερικώς διατεταγμένο σύνολο. Το παρακάτω σχήμα δείχνει τη δομή αυτού του συνόλου: εάν ένα στοιχείο μπορεί να προσεγγιστεί με βέλη σε ένα άλλο στοιχείο, τότε βρίσκονται σε σχέση τάξης.
Θα χρειαστούμε δύο ακόμη απλούς ορισμούς από τον τομέα των μαθηματικών - supremum και infimum.
Ορισμός 3. Έστω ⟨S, ⩽⟩ ένα μερικώς διατεταγμένο σύνολο, A ⊆ S. Το άνω όριο του A είναι ένα στοιχείο u ∈ S τέτοιο ώστε ∀x ∈ S: x ⩽ u. Έστω U το σύνολο όλων των άνω ορίων του S. Αν υπάρχει ένα μικρότερο στοιχείο στο U, τότε αυτό ονομάζεται υπέρτατο και συμβολίζεται sup A.
Παρομοίως εισάγεται η έννοια του ακριβούς κάτω ορίου.
Ορισμός 4. Έστω ⟨S, ⩽⟩ ένα μερικώς διατεταγμένο σύνολο, A ⊆ S. Το infimum του A είναι ένα στοιχείο l ∈ S τέτοιο ώστε ∀x ∈ S: l ⩽ x. Έστω L το σύνολο όλων των κάτω ορίων του S. Αν υπάρχει ένα μεγαλύτερο στοιχείο στο L, τότε αυτό ονομάζεται infimum και συμβολίζεται ως inf A.
Εξετάστε ως παράδειγμα το παραπάνω μερικώς διατεταγμένο σύνολο ⟨P ({1, 2, 3}), ⊆⟩ και βρείτε το supremum και το infimum σε αυτό:
Τώρα μπορούμε να διατυπώσουμε τον ορισμό ενός αλγεβρικού πλέγματος.
Ορισμός 5. Έστω ⟨P,⩽⟩ ένα μερικώς διατεταγμένο σύνολο έτσι ώστε κάθε υποσύνολο δύο στοιχείων να έχει ένα άνω και κάτω όριο. Τότε το P ονομάζεται αλγεβρικό πλέγμα. Σε αυτήν την περίπτωση, το sup{x, y} γράφεται ως x ∨ y, και το inf {x, y} ως x ∧ y.
Ας ελέγξουμε ότι το παράδειγμα εργασίας μας ⟨P ({1, 2, 3}), ⊆⟩ είναι ένα πλέγμα. Πράγματι, για κάθε a, b ∈ P ({1, 2, 3}), a∨b = a∪b και a∧b = a∩b. Για παράδειγμα, εξετάστε τα σύνολα {1, 2} και {1, 3} και βρείτε το infimum και το supremum τους. Αν τα τέμνουμε, θα πάρουμε το σύνολο {1}, το οποίο θα είναι το infimum. Λαμβάνουμε το υπέρτατο συνδυάζοντάς τα - {1, 2, 3}.
Σε αλγόριθμους για τον εντοπισμό φυσικών προβλημάτων, ο χώρος αναζήτησης συχνά αναπαρίσταται με τη μορφή πλέγματος, όπου σύνολα ενός στοιχείου (διαβάστε το πρώτο επίπεδο του πλέγματος αναζήτησης, όπου η αριστερή πλευρά των εξαρτήσεων αποτελείται από ένα χαρακτηριστικό) αντιπροσωπεύουν κάθε χαρακτηριστικό της αρχικής σχέσης.
Αρχικά, εξετάζουμε τις εξαρτήσεις της μορφής ∅ → Ενιαία ιδιότητα. Αυτό το βήμα σάς επιτρέπει να προσδιορίσετε ποια χαρακτηριστικά είναι πρωτεύοντα κλειδιά (για τέτοια χαρακτηριστικά δεν υπάρχουν ορίζοντες και επομένως η αριστερή πλευρά είναι κενή). Επιπλέον, τέτοιοι αλγόριθμοι κινούνται προς τα πάνω κατά μήκος του πλέγματος. Αξίζει να σημειωθεί ότι δεν μπορεί να διασχιστεί ολόκληρο το πλέγμα, δηλαδή εάν το επιθυμητό μέγιστο μέγεθος της αριστερής πλευράς περάσει στην είσοδο, τότε ο αλγόριθμος δεν θα προχωρήσει περισσότερο από ένα επίπεδο με αυτό το μέγεθος.
Το παρακάτω σχήμα δείχνει πώς μπορεί να χρησιμοποιηθεί ένα αλγεβρικό πλέγμα στο πρόβλημα εύρεσης ενός FZ. Εδώ κάθε άκρη (Χ, ΧΥ) αντιπροσωπεύει μια εξάρτηση Χ → Υ. Για παράδειγμα, έχουμε περάσει το πρώτο επίπεδο και γνωρίζουμε ότι ο εθισμός διατηρείται Α → Β (θα το εμφανίσουμε ως πράσινη σύνδεση μεταξύ των κορυφών A и B). Αυτό σημαίνει ότι περαιτέρω, όταν ανεβαίνουμε κατά μήκος του πλέγματος, ενδέχεται να μην ελέγξουμε την εξάρτηση Α, Γ → Β, γιατί δεν θα είναι πλέον minimal. Ομοίως, δεν θα το ελέγξαμε εάν διατηρούνταν η εξάρτηση Γ → Β.
Επιπλέον, κατά κανόνα, όλοι οι σύγχρονοι αλγόριθμοι για την αναζήτηση ομοσπονδιακών νόμων χρησιμοποιούν μια δομή δεδομένων όπως ένα διαμέρισμα (στην αρχική πηγή - απογυμνωμένο διαμέρισμα [1]). Ο επίσημος ορισμός ενός διαμερίσματος είναι ο εξής:
Ορισμός 6. Έστω X ⊆ R ένα σύνολο χαρακτηριστικών για τη σχέση r. Ένα σύμπλεγμα είναι ένα σύνολο δεικτών πλειάδων στο r που έχουν την ίδια τιμή για το X, δηλαδή c(t) = {i|ti[X] = t[X]}. Ένα διαμέρισμα είναι ένα σύνολο συστάδων, εξαιρουμένων των συστάδων μοναδιαίου μήκους:
Με απλά λόγια, ένα διαμέρισμα για ένα χαρακτηριστικό X είναι ένα σύνολο λιστών, όπου κάθε λίστα περιέχει αριθμούς γραμμών με τις ίδιες τιμές για X. Στη σύγχρονη βιβλιογραφία, η δομή που αντιπροσωπεύει τις κατατμήσεις ονομάζεται δείκτης λίστας θέσης (PLI). Τα συμπλέγματα μήκους μονάδας εξαιρούνται για σκοπούς συμπίεσης PLI επειδή είναι συμπλέγματα που περιέχουν μόνο έναν αριθμό εγγραφής με μια μοναδική τιμή που θα είναι πάντα εύκολο να αναγνωριστεί.
Ας δούμε ένα παράδειγμα. Ας επιστρέψουμε στον ίδιο πίνακα με τους ασθενείς και ας δημιουργήσουμε διαμερίσματα για τις στήλες Ασθενής и Φύλο (μια νέα στήλη εμφανίστηκε στα αριστερά, στην οποία σημειώνονται οι αριθμοί των γραμμών του πίνακα):
Επιπλέον, σύμφωνα με τον ορισμό, το διαμέρισμα για τη στήλη Ασθενής θα είναι στην πραγματικότητα κενή, αφού τα μεμονωμένα συμπλέγματα εξαιρούνται από το διαμέρισμα.
Οι κατατμήσεις μπορούν να ληφθούν από διάφορα χαρακτηριστικά. Και υπάρχουν δύο τρόποι για να το κάνετε αυτό: περνώντας από τον πίνακα, δημιουργήστε ένα διαμέρισμα χρησιμοποιώντας όλα τα απαραίτητα χαρακτηριστικά ταυτόχρονα ή δημιουργήστε το χρησιμοποιώντας τη λειτουργία τομής κατατμήσεων χρησιμοποιώντας ένα υποσύνολο χαρακτηριστικών. Οι αλγόριθμοι αναζήτησης ομοσπονδιακού νόμου χρησιμοποιούν τη δεύτερη επιλογή.
Με απλά λόγια, για να πάρετε, για παράδειγμα, ένα διαμέρισμα ανά στήλες ABC, μπορείτε να πάρετε κατατμήσεις για AC и B (ή οποιοδήποτε άλλο σύνολο ασύνδετων υποσυνόλων) και τέμνονται μεταξύ τους. Η λειτουργία τομής δύο κατατμήσεων επιλέγει συστάδες με το μεγαλύτερο μήκος που είναι κοινά και στα δύο διαμερίσματα.
Ας δούμε ένα παράδειγμα:
Στην πρώτη περίπτωση, λάβαμε ένα κενό διαμέρισμα. Εάν κοιτάξετε προσεκτικά τον πίνακα, τότε πράγματι, δεν υπάρχουν πανομοιότυπες τιμές για τα δύο χαρακτηριστικά. Εάν τροποποιήσουμε ελαφρώς τον πίνακα (η θήκη στα δεξιά), θα έχουμε ήδη μια μη κενή διασταύρωση. Επιπλέον, οι γραμμές 1 και 2 περιέχουν στην πραγματικότητα τις ίδιες τιμές για τα χαρακτηριστικά Φύλο и Γιατρός.
Στη συνέχεια, θα χρειαστούμε μια τέτοια έννοια όπως το μέγεθος του διαμερίσματος. Επίσημα:
Με απλά λόγια, το μέγεθος του διαμερίσματος είναι ο αριθμός των συμπλεγμάτων που περιλαμβάνονται στο διαμέρισμα (θυμηθείτε ότι τα μεμονωμένα συμπλέγματα δεν περιλαμβάνονται στο διαμέρισμα!):
Τώρα μπορούμε να ορίσουμε ένα από τα βασικά λήμματα, το οποίο για συγκεκριμένες κατατμήσεις μας επιτρέπει να προσδιορίσουμε εάν μια εξάρτηση διατηρείται ή όχι:
Λήμμα 1. Η εξάρτηση A, B → C ισχύει εάν και μόνο εάν
Σύμφωνα με το λήμμα, για να καθοριστεί εάν ισχύει μια εξάρτηση, πρέπει να εκτελεστούν τέσσερα βήματα:
- Υπολογίστε το διαμέρισμα για την αριστερή πλευρά της εξάρτησης
- Υπολογίστε το διαμέρισμα για τη δεξιά πλευρά της εξάρτησης
- Υπολογίστε το γινόμενο του πρώτου και του δεύτερου βήματος
- Συγκρίνετε τα μεγέθη των χωρισμάτων που αποκτήθηκαν στο πρώτο και το τρίτο βήμα
Ακολουθεί ένα παράδειγμα ελέγχου του εάν η εξάρτηση ισχύει σύμφωνα με αυτό το λήμμα:
Σε αυτό το άρθρο, εξετάσαμε έννοιες όπως λειτουργική εξάρτηση, κατά προσέγγιση λειτουργική εξάρτηση, εξετάσαμε πού χρησιμοποιούνται, καθώς και ποιοι αλγόριθμοι για την αναζήτηση φυσικών συναρτήσεων υπάρχουν. Εξετάσαμε επίσης λεπτομερώς τις βασικές αλλά σημαντικές έννοιες που χρησιμοποιούνται ενεργά σε σύγχρονους αλγόριθμους για την αναζήτηση ομοσπονδιακών νόμων.
Βιβλιογραφικές αναφορές:
- Huhtala Y. et al. TANE: Ένας αποτελεσματικός αλγόριθμος για την ανακάλυψη λειτουργικών και κατά προσέγγιση εξαρτήσεων //The computer journal. – 1999. – Τ. 42. – Αρ. 2. – σσ. 100-111.
- Kruse S., Naumann F. Αποτελεσματική ανακάλυψη των κατά προσέγγιση εξαρτήσεων // Proceedings of the VLDB Endowment. – 2018. – Τ. 11. – Αρ. 7. – σσ. 759-772.
- Papenbrock T., Naumann F. Μια υβριδική προσέγγιση στην ανακάλυψη λειτουργικών εξαρτήσεων //Πρακτικά του Διεθνούς Συνεδρίου 2016 για τη Διαχείριση Δεδομένων. – ACM, 2016. – σσ. 821-833.
- Papenbrock Τ. et al. Ανακάλυψη λειτουργικής εξάρτησης: Μια πειραματική αξιολόγηση επτά αλγορίθμων //Πρακτικά του VLDB Endowment. – 2015. – Τ. 8. – Αρ. 10. – σσ. 1082-1093.
- Kumar A. et al. Να συμμετάσχετε ή να μην συμμετάσχετε;: Σκέφτεστε δύο φορές για τις ενώσεις πριν από την επιλογή χαρακτηριστικών //Πρακτικά του Διεθνούς Συνεδρίου 2016 για τη Διαχείριση Δεδομένων. – ACM, 2016. – σσ. 19-34.
- Abo Khamis Μ. et al. Εκμάθηση εντός βάσης δεδομένων με αραιούς τανυστές //Πρακτικά του 37ου Συμποσίου ACM SIGMOD-SIGACT-SIGAI για τις αρχές των συστημάτων βάσεων δεδομένων. – ACM, 2018. – σσ. 325-340.
- Hellerstein J. M. et al. Η βιβλιοθήκη αναλυτικών στοιχείων MADlib: ή δεξιότητες MAD, η SQL //Πρακτικά του VLDB Endowment. – 2012. – Τ. 5. – Αρ. 12. – σσ. 1700-1711.
- Qin C., Rusu F. Εικαστικές προσεγγίσεις για βελτιστοποίηση κατανεμημένης κλίσης σε κλίμακα terascale //Πρακτικά του τέταρτου εργαστηρίου για την ανάλυση δεδομένων στο Cloud. – ACM, 2015. – Σελ. 1.
- Οι Meng X. et al. Mllib: Μηχανική μάθηση σε apache spark //The Journal of Machine Learning Research. – 2016. – Τ. 17. – Αρ. 1. – σσ. 1235-1241.
Συντάκτες του άρθρου: , ερευνητής στο , и , ερευνητής στο
Πηγή: www.habr.com