nikolaos_ Δημοσ. 6 Ιουλίου 2010 Δημοσ. 6 Ιουλίου 2010 Με κεφαλαία οι πίνακές μου σε μια βάση δεδομένων: Έχω έναν πίνακα ΕΠΙΒΑΤΩΝ που εκτός από Ονοματεπώνυμο έχει και τις στήλες Αφετηρία και Προορισμός, όπου παίρνουν τιμές ένα ΛΙΜΑΝΙ, π.χ. "Πειραιάς", "Χίος", "Μυτιλήνη", "Σύρος", "Μύκονος", "Ηράκλειο" κλπ. Έχω επίσης έναν πίνακα (ακτοπλοϊκών ΣΥΝΔΕΣΕΩΝ) που λέει ποιο ΠΛΟΙΟ πηγαίνει απευθείας από ποιο σε ποιο ΛΙΜΑΝΙ, π.χ. μια γραμμή του πίνακα λέει ότι το "Λισσός" πηγαίνει από "Πειραιά" προς "Χιο", στη συνέχεια σε μια άλλη γραμμή είναι το "Λισσός" από "Χίο" προς "Μυτιλήνη", στη συνέχεια σε άλλη γραμμή το ίδιο πλοίο "Λισσός" πηγαίνει από "Μυτιλήνη" προς "Καβάλα". Αλλού στον ίδιο πίνακα γράφει π.χ. το "Φαιστός Παλάς" πηγαίνει "Πειραιά"-"Ηράκλειο" κλπ. Θέλω μια SQL αναζήτηση που να μπορεί να εντοπίζει όλα τα σχετικά δρομολόγια από ένα λιμάνι προς ένα άλλο, μελετώντας τους ενδιάμεσους σταθμούς του πλοίου, π.χ. αν έχω τον επιβάτη που θέλει να πάει από "Πειραιά" προς "Μυτιλήνη", να εντοπίζει τις δυο συνδέσεις του "Λισσός" που ανέφερα προηγουμένως, δηλ. να δίνει αποτέλεσμα "Λισσός, Πειραιάς, Χίος", "Λισσός, Χίος, Μυτιλήνη". ή, αν ο επιβάτης πάει από "Χίο" προς "Καβάλα" να εντοπίζει το "Χίο - Μυτιλήνη - Καβάλα". Ένα πρόβλημα είναι βέβαια να αποφεύγει κύκλους του στυλ "Χίο-Πειραιά-Χίο-Μυτιλήνη-Καβάλα". Αν υπάρχει και κανένα link?
frikoulo Δημοσ. 6 Ιουλίου 2010 Δημοσ. 6 Ιουλίου 2010 καλημέρα! μια ερώτηση, θέλεις να βλέπεις το δρομολόγιο που διάλεξε ο επιβάτης, που να περιλαμβάνει τους ενδοιάμεσους προορισμούς, ή θες απλά να βλέπεις το κάθε δρομολόγιο ποιούς ενδοιάμεσους προορισμούς έχει (αν έχει) ?
nikolaos_ Δημοσ. 6 Ιουλίου 2010 Μέλος Δημοσ. 6 Ιουλίου 2010 Όχι, ο επιβάτης διαλέγει μόνο αφετηρία και προορισμό, δυο λιμάνια. Εγώ έχω ένα πίνακα με απευθείας συνδέσεις μεταξύ των λιμανιών και θέλω να βρίσκω ποιες από αυτές τις συνδέσεις ανταποκρίνονται στην αφετηρία και τον προορισμό του πελάτη, χωρίς να γίνονται κύκλοι. Π.χ. έχω μόνο μια γραμμή για πελάτη: > +------------------+----------------+------------+ | ONOMATEPONYMO | AFETHRIA | PROORISMOS | +------------------+----------------+------------+ | Kostas Panou | PEIRAIAS | MYTILHNH | +------------------+----------------+------------+ και πολλές γραμμές με απευθείας συνδέσεις δυο λιμανιών >(Πίνακας απευθείας συνδέσεων) +---------+----------------+----------------+ | PLOIO | ANAXORHSH | AFIXH | +---------+----------------+----------------+ | LISSOS | PEIRAIAS | XIOS | | LISSOS | XIOS | MYTILHNH | | LISSOS | MYTILHNH | LHMNOS | | LISSOS | LHMNOS | KAVALA | | LISSOS | KAVALA | LHMNOS | | LISSOS | LHMNOS | ALEXANDROYPOLH | | LISSOS | ALEXANDROYPOLH | LHMNOS | | LISSOS | LHMNOS | PEIRAIAS | | MARINA | PEIRAIAS | SYROS | | MARINA | SYROS | IKARIA | | ALKEOS | IKARIA | XIOS | +---------+----------------+----------------+ Η αναζήτηση θέλω να βρίσκει και τις διαδρομές α) "Μαρίνα" μέχρι Χίο μέσω Σύρου - Ικαρίας και μετά "Αλκαίος" και "Λισσός" για το Χίο - Μυτιλήνη β) Το "Λισσός" για Μυτιλήνη μέσω Χίου. κάτι σαν τούτο δηλαδή, που συγκεντρώνει όλα τα δρομολόγια: > | LISSOS | PEIRAIAS | XIOS | | LISSOS | XIOS | MYTILHNH | | MARINA | PEIRAIAS | SYROS | | MARINA | SYROS | IKARIA | | ALKEOS | IKARIA | XIOS | Με ενδιαφέρει δηλαδή 1) καταρχήν ένα κατεβατό από απευθείας συνδέσεις που δείχνουν πώς είναι δυνατό να πάει εκεί που θέλει ο επιβάτης 2) Ένα κατάλληλο σορτάρισμα αυτού του κατεβατού Το ιδανικό είναι να μου πει όλες τις δυνατές λύσεις: ποια πλοία στη σειρά να πάρει ο πελάτης για να φτάσει από εκεί που είναι εκεί που θέλει. Λύση 1: Με το πλοιο Α: Πειραιάς - Χίος - Μυτιλήνη Λύση 2: Με το πλοίο Α: Πειραιάς - Σύρος - Ικαρία, αλλάζεις πλοίο, μπαίνεις στο Β, Ικαρία - Χίος, αλλάζεις πλοίο, μπαίνεις στο Γ, Χίος - Μυτιλήνη Λύση 3: Με το πλοίο Α: Πειραιάς - Λήμνος - Καβάλα, αλλάζεις πλοίο μπαίνεις στο Β, Καβάλα - Μυτιλήνη !! κλπ. Θέλω να μην μπλέκει σε κύκλους. Για να μην μπλέξω με τις λύσεις που έχουν μεγάλα χρονικά διαστήματα, έχω μια στήλη με ημερομηνίες για τις συνδέσεις και τις περιορίζω ανάμεσα σε δυο ημερομηνίες, οπότε έχω ένα μικρό σχετικά πίνακα συνδέσεων.
_tasos Δημοσ. 6 Ιουλίου 2010 Δημοσ. 6 Ιουλίου 2010 Δεν είμαι σίγουρος ότι μπορείς να πετύχεις όλα αυτά με sql μόνο. Το πρόβλημα που θέλεις να αντιμετωπίσεις είναι η εύρεση συντομότερης διαδρομής σε γράφημα. Οι αλγόριθμοι για εύρεση βέλτιστης διαδρομής είναι αρκετά πολύπλοκοι κ δεν είναι καλή ιδέα η υλοποίηση τους με sql. Ίσως να καταφέρεις να γράψεις κάποιο stored procedure, αλλά εγώ θα έγραφα κώδικα με κάποια high level γλώσσα για να το υλοποιήσω. Θα πρέπει να διαβάσεις λίγο για τέτοιους αλγόριθμους, όπως π.χ. ο αλγόριθμος του Dijkstra, και από εκεί να φτιάξεις κάτι.
mvaggel Δημοσ. 6 Ιουλίου 2010 Δημοσ. 6 Ιουλίου 2010 Θες μια συνάρτηση της μορφής Find(Ploio,Apo,Pros,Before) που θα σου επιστρέφει μια λίστα (Dataset, πες την όπως θες). Αυτή εκτελεί ένα "Select PLOIO as P1,AFIXH as A1 from SYNDESEIS WHERE ANAXORHSH=Apo AND PLOIO=Ploio[αν οχι κενό] AND AFIXH not in (Before)" Μετά κανει έναν έλεγχο αν έχει αποτέλεσμα με AFIXH=Pros. Αν ναι, αδειαζει όλα τα άλλα αποτελέσματα και επιστρέφει αυτό. Αν όχι, τότε για κάθε αποτέλεσμα καλεί την Find(την ίδια δηλαδή) με ορίσματα Find(P1,A1,Pros,Before+A1). Την πρώτη φορά, καλείς την Find ως εξής "Find('',PEIRAIAS,MYTILHNH,PEIRAIAS)" που σημαίνει "Βρες τη διαδρομή ,με όποιο πλοίο,από PEIRAIAS για MYTILHNH , όχι ομως μέσω PEIRAIAS" Στη συνέχεια, αν θες να συνεχίζεις με το ίδιο πλοίο, τότε περνάς το όνομα στο πρώτο όρισμα, αν δεν σε ενδιαφέρει να είναι το ίδιο απλά αφήνεις το πρώτο όρισμα κενό. Αυτός πάνω κάτω είναι ο αλγόριθμος, απλός και θα δουλέψει για πεπερασμένο πλήθος στοιχείων (πλοίων και λιμανιών) Προφανώς όλο το παραπάνω δεν βγαίνει με ένα query αλλά θέλει κώδικα είτε σε stored procedure, είτε cursor, είτε κάποια άλλη high level γλώσσα. Επίσης πρέπει να βρεις ένα τρόπο να παρουσιάζεις μια διαδρομή με ενδιάμεσους προορισμούς και πιθανότατα με αλλαγές πλοίων στην πορεία. Καλά ταξίδια ;-)
nikolaos_ Δημοσ. 7 Ιουλίου 2010 Μέλος Δημοσ. 7 Ιουλίου 2010 Δεν είμαι σίγουρος ότι μπορείς να πετύχεις όλα αυτά με sql μόνο. Το πρόβλημα που θέλεις να αντιμετωπίσεις είναι η εύρεση συντομότερης διαδρομής σε γράφημα. Οι αλγόριθμοι για εύρεση βέλτιστης διαδρομής είναι αρκετά πολύπλοκοι κ δεν είναι καλή ιδέα η υλοποίηση τους με sql. Ίσως να καταφέρεις να γράψεις κάποιο stored procedure, αλλά εγώ θα έγραφα κώδικα με κάποια high level γλώσσα για να το υλοποιήσω. Θα πρέπει να διαβάσεις λίγο για τέτοιους αλγόριθμους, όπως π.χ. ο αλγόριθμος του Dijkstra, και από εκεί να φτιάξεις κάτι. Όντως είναι αναζήτηση διαδρομής σε γράφημα, αλλά όχι αλγόριθμος Dijkstra, δηλαδή δεν αναζητώ τη συντομότερη μόνο, αλλά όλες τις (άκυκλες) διαδρομές σε ένα γράφημα που πάνε από ένα κόμβο σε έναν άλλο. ---------- Προσθήκη στις 16:31 ---------- Προηγούμενο μήνυμα στις 13:18 ---------- Λοιπόν, έχω καταφέρει κάτι με σκέτες SQL-αναζητήσεις, και θα το μοιραστώ μαζί σας μήπως και βελτιωθεί. Πριν από αυτό, θα κάνω λίγο πιο συγκεκριμένο το πρόβλημα, δίνοντας με συμπληρωμένα δεδομένα τη βάση. (1) Ο πίνακας των επιβατών, για την ακρίβεια ΠΕΛΑΤΩΝ, αφού οι ίδιοι επιβάτες έχουν διαφορετικές επιθυμίες ταξιδιών σε κάθε γραμμή. Υπάρχουν και οι ημερομηνίες αλλά δεν τις λαμβάνω υπόψη για να μη μπλέξουν τα πράγματα. > mysql> [b]SELECT ONOMATEPONYMO, AFETHRIA, PROORISMOS FROM PELATHS;[/b] +------------------+----------------+------------+ | ONOMATEPONYMO | AFETHRIA | PROORISMOS | +------------------+----------------+------------+ | Kostas P. | PEIRAIAS | MYTILHNH | | Sofia P. | PEIRAIAS | HRAKLEIO | | Panagiotis Z. | PEIRAIAS | MYTILHNH | | Kostas F. | MYTILHNH | XANIA | | Jim M. | ALEXANDROYPOLH | LHMNOS | | Nikos N. | LHMNOS | MYTILHNH | | Kyriaki K. | HRAKLEIO | PEIRAIAS | | Nikos A. | PEIRAIAS | MYTILHNH | | Nikos A. | PEIRAIAS | LHMNOS | | Kostas F. | XANIA | MYTILHNH | +------------------+----------------+------------+ Ο πίνακας (1) δηλώνει ότι ο πελάτης θέλει να πάει από την αφετηρία του στον [/b](τελικό)[/b] προορισμό του, δεν έχει σημασία γι' αυτούς αν θα υπάρχουν ενδιάμεσοι σταθμοί. (2) Ο πίνακας των συνδέσεων είναι μπόλικος. Δείχνει τα απευθείας δρομολόγια των πλοίων. Και εδώ υπάρχουν ημερομηνίες, αλλά είπαμε δε θα τις μπερδέψω μέσα: > mysql> [b]SELECT KODIKOS, PLOIO, ANAXORHSH, AFIXH FROM SYNDESH;[/b] +---------+---------------+----------------+----------------+ | KODIKOS | PLOIO | ANAXORHSH | AFIXH | +---------+---------------+----------------+----------------+ | 1 | KEVIN 9 | PEIRAIAS | XANIA | | 2 | LISSOS | PEIRAIAS | XIOS | | 3 | LISSOS | XIOS | MYTILHNH | | 4 | LISSOS | MYTILHNH | LHMNOS | | 5 | LISSOS | LHMNOS | KAVALA | | 6 | LISSOS | KAVALA | LHMNOS | | 7 | LISSOS | LHMNOS | ALEXANDROYPOLH | | 8 | LISSOS | ALEXANDROYPOLH | LHMNOS | | 9 | LISSOS | LHMNOS | PEIRAIAS | | 10 | NHSOS XIOS | PEIRAIAS | SYROS | | 11 | NHSOS XIOS | SYROS | MYKONOS | | 12 | NHSOS XIOS | MYKONOS | XIOS | | 13 | NHSOS XIOS | XIOS | MYTILHNH | | 14 | NHSOS XIOS | MYTILHNH | XIOS | | 15 | NHSOS XIOS | XIOS | MYKONOS | | 16 | NHSOS XIOS | MYKONOS | SYROS | | 17 | NHSOS XIOS | SYROS | PEIRAIAS | | 18 | FESTOS PALACE | PEIRAIAS | HRAKLEIO | | 19 | FESTOS PALACE | HRAKLEIO | PEIRAIAS | | 20 | FESTOS PALACE | PEIRAIAS | HRAKLEIO | | 21 | FESTOS PALACE | HRAKLEIO | PEIRAIAS | | 22 | TAXIARCHIS | PEIRAIAS | LHMNOS | | 23 | TAXIARCHIS | LHMNOS | KAVALA | | 24 | TAXIARCHIS | KAVALA | LHMNOS | | 25 | TAXIARCHIS | LHMNOS | ALEXANDROYPOLH | | 26 | TAXIARCHIS | ALEXANDROYPOLH | SAMOTHRAKH | | 27 | TAXIARCHIS | SAMOTHRAKH | LHMNOS | | 28 | TAXIARCHIS | LHMNOS | MYTILHNH | +---------+---------------+----------------+----------------+ Με μια πρώτη ματιά, φαίνεται π.χ. ότι: (α) ο πελάτης Kostas P. θα πάρει το LISSOS και θα φτάσει Μυτιλήνη μέσω Χίου, ή εναλλακτικά το NHSOS XIOS με τις συνδέσεις 10, 11, 12, 13. (β) ο πελάτης Sofia P. θα πάρει το FESTOS PALACE για Ηράκλειο, είτε με το 18, είτε με το 20. Δεν έχει ενδιάμεσους σταθμούς. Πώς αυτά που βλέπω με το μάτι μπορούν να αποτυπωθούν; *1* Βρίσκω καταρχήν τα απευθείας δρομολόγια: > mysql> [b]SELECT P.ONOMATEPONYMO, S.PLOIO, S.ANAXORHSH, S.AFIXH, S.KODIKOS -> FROM PELATHS P, SYNDESH S -> WHERE (S.ANAXORHSH=P.AFETHRIA) AND (S.AFIXH=P.PROORISMOS);[/b] +------------------+---------------+----------------+----------+---------+ | ONOMATEPONYMO | PLOIO | ANAXORHSH | AFIXH | KODIKOS | +------------------+---------------+----------------+----------+---------+ | Sofia P. | FESTOS PALACE | PEIRAIAS | HRAKLEIO | 18 | | Sofia P. | FESTOS PALACE | PEIRAIAS | HRAKLEIO | 20 | | Jim M. | LISSOS | ALEXANDROYPOLH | LHMNOS | 8 | | Nikos N. | TAXIARCHIS | LHMNOS | MYTILHNH | 28 | | Kyriaki K. | FESTOS PALACE | HRAKLEIO | PEIRAIAS | 19 | | Kyriaki K. | FESTOS PALACE | HRAKLEIO | PEIRAIAS | 21 | | Nikos A. | TAXIARCHIS | PEIRAIAS | LHMNOS | 22 | +------------------+---------------+----------------+----------+---------+ οπότε φαίνεται στον πίνακα ποιοι πελάτες θα πάρουν ποια δρομολόγια για να πάνε απευθείας από την αφετηρία τους στον προορισμό τους. Εύκολο φυσικά διότι η query βρίσκει ποιων τα πλοία η άφιξη και η αναχώρηση συνταυτίζονται με τον προορισμό και την αφετηρία κάθε πελάτη, αντίστοιχα. *2* Δοκίμασα μετά από πειραματισμούς, στη συνέχεια, το εξής query: > mysql> [b]SELECT P.ONOMATEPONYMO, P.AFETHRIA, S.ANAXORHSH AS ENAS_PRIN_PROORISMOS, P.PROORISMOS, S.KODIKOS -> FROM PELATHS P, SYNDESH S -> WHERE (S.AFIXH=P.PROORISMOS) AND NOT (P.AFETHRIA=S.ANAXORHSH);[/b] +------------------+----------------+----------------------+------------+---------+ | ONOMATEPONYMO | AFETHRIA | ENAS_PRIN_PROORISMOS | PROORISMOS | KODIKOS | +------------------+----------------+----------------------+------------+---------+ | Kostas P. | PEIRAIAS | XIOS | MYTILHNH | 3 | | Kostas P. | PEIRAIAS | XIOS | MYTILHNH | 13 | | Kostas P. | PEIRAIAS | LHMNOS | MYTILHNH | 28 | | Panagiotis Z. | PEIRAIAS | XIOS | MYTILHNH | 3 | | Panagiotis Z. | PEIRAIAS | XIOS | MYTILHNH | 13 | | Panagiotis Z. | PEIRAIAS | LHMNOS | MYTILHNH | 28 | | Kostas F. | MYTILHNH | PEIRAIAS | XANIA | 1 | | Jim M. | ALEXANDROYPOLH | MYTILHNH | LHMNOS | 4 | | Jim M. | ALEXANDROYPOLH | KAVALA | LHMNOS | 6 | | Jim M. | ALEXANDROYPOLH | PEIRAIAS | LHMNOS | 22 | | Jim M. | ALEXANDROYPOLH | KAVALA | LHMNOS | 24 | | Jim M. | ALEXANDROYPOLH | SAMOTHRAKH | LHMNOS | 27 | | Nikos N. | LHMNOS | XIOS | MYTILHNH | 3 | | Nikos N. | LHMNOS | XIOS | MYTILHNH | 13 | | Kyriaki K. | HRAKLEIO | LHMNOS | PEIRAIAS | 9 | | Kyriaki K. | HRAKLEIO | SYROS | PEIRAIAS | 17 | | Nikos A. | PEIRAIAS | XIOS | MYTILHNH | 3 | | Nikos A. | PEIRAIAS | XIOS | MYTILHNH | 13 | | Nikos A. | PEIRAIAS | LHMNOS | MYTILHNH | 28 | | Nikos A. | PEIRAIAS | MYTILHNH | LHMNOS | 4 | | Nikos A. | PEIRAIAS | KAVALA | LHMNOS | 6 | | Nikos A. | PEIRAIAS | ALEXANDROYPOLH | LHMNOS | 8 | | Nikos A. | PEIRAIAS | KAVALA | LHMNOS | 24 | | Nikos A. | PEIRAIAS | SAMOTHRAKH | LHMNOS | 27 | | Kostas F. | XANIA | XIOS | MYTILHNH | 3 | | Kostas F. | XANIA | XIOS | MYTILHNH | 13 | | Kostas F. | XANIA | LHMNOS | MYTILHNH | 28 | +------------------+----------------+----------------------+------------+---------+ Αυτός ο πίνακας εκφράζει τι: -- βρίσκει για κάθε πελάτη πού πάει, την αφετηρία, τον τελικό προορισμό του, που δεν ταιριάζουν με απευθείας συνδέσεις των πλοίων[/b], -- βρίσκει τις συνδέσεις που φτάνουν στον προορισμό του πελάτη και βάζει τις αναχωρήσεις τους στην καινούργια στήλη (δε μπορεί να προβλέψει ότι οι πελάτες μπορούν να εξυπηρετηθούν με άλλα δρομολόγια, βλ. Kyriaki K. που πάει από Ηράκλειο προς Πειραιά και μέσω Λήμνου!) *3* Πάντως ο πίνακας με ONOMATEPONYMO, AFETHRIA, ENAS_PRIN_PROORISMOS είναι στην μορφή του πίνακα (1) ! Οπότε, μπορώ να εφαρμόσω ένα σύνθετο query όπως στον πίνακα (1) για να βρω τις απευθείας συνδέσεις πλοίων μεταξύ AFETHRIA και ENAS_PRIN_PROORISMOS: > mysql> [b]SELECT P1.ONOMATEPONYMO, S1.PLOIO, S1.ANAXORHSH, S1.AFIXH AS ENAS_PRIN_PROORISMOS, S1.KODIKOS -> FROM -> (SELECT P.ONOMATEPONYMO, P.AFETHRIA, S.ANAXORHSH AS ENAS_PRIN_PROORISMOS FROM SYNDESH S, PELATHS P WHERE S.AFIXH=P.PROORISMOS) AS P1, -> SYNDESH S1 -> WHERE (S1.ANAXORHSH=P1.AFETHRIA) AND (S1.AFIXH=P1.ENAS_PRIN_PROORISMOS);[/b] +------------------+------------+----------------+----------------------+---------+ | ONOMATEPONYMO | PLOIO | ANAXORHSH | ENAS_PRIN_PROORISMOS | KODIKOS | +------------------+------------+----------------+----------------------+---------+ | Kostas P. | LISSOS | PEIRAIAS | XIOS | 2 | | Kostas P. | LISSOS | PEIRAIAS | XIOS | 2 | | Kostas P. | TAXIARCHIS | PEIRAIAS | LHMNOS | 22 | | Panagiotis Z. | LISSOS | PEIRAIAS | XIOS | 2 | | Panagiotis Z. | LISSOS | PEIRAIAS | XIOS | 2 | | Panagiotis Z. | TAXIARCHIS | PEIRAIAS | LHMNOS | 22 | | Jim M. | TAXIARCHIS | ALEXANDROYPOLH | SAMOTHRAKH | 26 | | Nikos A. | LISSOS | PEIRAIAS | XIOS | 2 | | Nikos A. | LISSOS | PEIRAIAS | XIOS | 2 | | Nikos A. | TAXIARCHIS | PEIRAIAS | LHMNOS | 22 | +------------------+------------+----------------+----------------------+---------+ Δηλαδή, με το μάτι, μπορείς να δεις ότι ο Kostas P. πρέπει να πάρει τις συνδέσεις 2 και 3 για να φτάσει Μυτιλήνη μέσω Χίου, ή τις 22 και 28 κλπ. Δεν έχω ακόμη φτιάξει ένα query για αυτή τη δουλειά. Πάντως με ένα σύνθετο query μάλλον μπορεί να δείξει τι να πάρει ο πελάτης με ποια πλοία θα φτάσει στον τελικό προορισμό του. Δεν βάζει μέσα το NHSOS XIOS, οπότε πρέπει να μην πάει κάτι καλά. Θα συνεχίσω την προσπάθεια...
bnvdarklord Δημοσ. 7 Ιουλίου 2010 Δημοσ. 7 Ιουλίου 2010 Δεν ξερεις παντως ποσοι ενδιάμεσοι σταθμοί θα υπάρξουν οποτε καθαρά με SQL νομίζω δεν μπορείς να το κάνεις...
MitsakosGR Δημοσ. 11 Ιουλίου 2010 Δημοσ. 11 Ιουλίου 2010 Κοίτα λίγο αυτό. Έχει πάρα πολλά πράγματα για mySQL αλλά στο συγκεκριμένο παράδειγμα έχει τον αλγόριθμο Dijkstra υλοποιημένο σε mySQL. Δες πώς το κάνει μήπως βγάλεις κάποιο συμπέρασμα για το πώς γίνεται αυτό που θέλεις αλλά και η επαναληπτική διαδικασία κτλ.
nikolaos_ Δημοσ. 1 Ιουλίου 2011 Μέλος Δημοσ. 1 Ιουλίου 2011 Επανέρχομαι με μια καινούργια απορία αναζήτησης. Έχω έναν πίνακα που θα τον ονομάζω v και σας δείχνω τα ονόματα από τις στήλες και ένα μέρος από τα στοιχεία που έχει: > tid | gid | result | prosimo -----+-----+-------------------+--------- 223 | 1 | 0.55921077538823 | -1 227 | 2 | 0.584616604911498 | -1 230 | 2 | 0.527023373993936 | -1 249 | 16 | 0.598756812894298 | -1 252 | 17 | 0.620207010255029 | -1 254 | 17 | 0.606138001016681 | -1 257 | 17 | 0.542893662735155 | -1 293 | 18 | 0.547231420196952 | -1 295 | 18 | 0.499488013903342 | -1 302 | 21 | 0.538635071779546 | -1 305 | 21 | 0.454375541222251 | -1 247 | 22 | 0.787566166192448 | -1 274 | 24 | 1.88955070988031 | -1 292 | 25 | 5.11000336609501 | -1 277 | 26 | 5.13492443879736 | -1 248 | 28 | 5.22490501207468 | -1 224 | 29 | 5.11959355553873 | -1 298 | 30 | 5.20561942139269 | -1 314 | 31 | 0.52035611040872 | -1 246 | 32 | 3.69442158748402 | -1 245 | 33 | 3.70970289068028 | -1 240 | 33 | 3.69052005779374 | -1 237 | 33 | 3.61684488496706 | -1 301 | 34 | 5.14909422627562 | -1 304 | 35 | 3.67146682215599 | -1 300 | 35 | 3.52355369922127 | -1 318 | 36 | 5.05301283112031 | -1 239 | 37 | 0.561262960007222 | -1 241 | 37 | 0.545030667392126 | -1 243 | 37 | 0.4720921879177 | -1 260 | 38 | 0.561110707020054 | -1 262 | 38 | 0.546761144710915 | -1 264 | 38 | 0.509045491044267 | -1 267 | 38 | 0.352563467379567 | -1 265 | 39 | 3.71242139193729 | -1 263 | 39 | 3.70492107998442 | -1 261 | 39 | 3.67889624112289 | -1 258 | 39 | 3.56106977268494 | -1 307 | 40 | 0.559815541758115 | -1 Όπως φαίνεται, το tid είναι το primary key, ενώ τα gid ομαδοποιούν τα results, τα οποία σε κάθε ομάδα (κοινό gid) ταξινομούνται σε φθίνουσα σειρά. Π.χ. στην ομάδα gid=38 φαίνεται ότι το 0.5611 είναι το πρώτο και μεγαλύτερο και ακολουθούν άλλα μικρότερα. Θέλω να προσθέσω μια στήλη που να κάνει την κατάταξη (grade) των αποτελεσμάτων σε κάθε μια από τις 40 ομάδες που εμφανίζονται στον παραπάνω πίνακα. Με το χέρι έφτιαξα τα επιθυμητά αποτελέσματα: > tid | gid | grad | result | prosimo -----+-----+------+-------------------+--------- 223 | 1 | 1 | 0.55921077538823 | -1 227 | 2 | 1 | 0.584616604911498 | -1 230 | 2 | 2 | 0.527023373993936 | -1 249 | 16 | 1 | 0.598756812894298 | -1 252 | 17 | 1 | 0.620207010255029 | -1 254 | 17 | 2 | 0.606138001016681 | -1 257 | 17 | 3 | 0.542893662735155 | -1 293 | 18 | 1 | 0.547231420196952 | -1 295 | 18 | 2 | 0.499488013903342 | -1 302 | 21 | 1 | 0.538635071779546 | -1 305 | 21 | 2 | 0.454375541222251 | -1 247 | 22 | 1 | 0.787566166192448 | -1 274 | 24 | 1 | 1.88955070988031 | -1 292 | 25 | 1 | 5.11000336609501 | -1 277 | 26 | 1 | 5.13492443879736 | -1 248 | 28 | 1 | 5.22490501207468 | -1 224 | 29 | 1 | 5.11959355553873 | -1 298 | 30 | 1 | 5.20561942139269 | -1 314 | 31 | 1 | 0.52035611040872 | -1 246 | 32 | 1 | 3.69442158748402 | -1 245 | 33 | 1 | 3.70970289068028 | -1 240 | 33 | 2 | 3.69052005779374 | -1 237 | 33 | 3 | 3.61684488496706 | -1 301 | 34 | 1 | 5.14909422627562 | -1 304 | 35 | 1 | 3.67146682215599 | -1 300 | 35 | 2 | 3.52355369922127 | -1 318 | 36 | 1 | 5.05301283112031 | -1 239 | 37 | 1 | 0.561262960007222 | -1 241 | 37 | 2 | 0.545030667392126 | -1 243 | 37 | 3 | 0.4720921879177 | -1 260 | 38 | 1 | 0.561110707020054 | -1 262 | 38 | 2 | 0.546761144710915 | -1 264 | 38 | 3 | 0.509045491044267 | -1 267 | 38 | 4 | 0.352563467379567 | -1 265 | 39 | 1 | 3.71242139193729 | -1 263 | 39 | 2 | 3.70492107998442 | -1 261 | 39 | 3 | 3.67889624112289 | -1 258 | 39 | 4 | 3.56106977268494 | -1 307 | 40 | 1 | 0.559815541758115 | -1 Πώς θα το υλοποιήσω με μια SQL QUERY? ?
DeltaLover Δημοσ. 1 Ιουλίου 2011 Δημοσ. 1 Ιουλίου 2011 Αυτο που ζητας ειναι μια παραλλαγη του Tarjan algorithm: http://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm πανω στην οποια πρεπει να κανεις τις τροποποιησεις σου.... Οπως προαναφερθηκε δεν συνισταται το implementation αυτο του αλγοριθμου σε SQL... Θα πρεπει να προτιμησεις μια πιο imperative γλωσσα (C, C++, Java, C# κλπ)
ΠάρηςΓ Δημοσ. 2 Ιουλίου 2011 Δημοσ. 2 Ιουλίου 2011 Κύριος nikolaos_ , Για το τελευταιο ερώτημα αν δε το εχεις βρει γινεται ευκολα.. set @gid=0; set @num=1; SELECT *,@num := IF(@gid=gid,@num:=@num+1 ,1) as grad,@gid :=gid FROM PINAKS_SOU ORDER BY gid; Οσο για το αλλο μαλλον ΔΕΝ γινεται με SQL. Πιθανον να κοιταξεις τον Breadth FIrst αλγοριθμο και δες αν σου κανει..Δε ξερω ποσο χρονο θα κανει αλλα ισως χρειαζεται καποια cache για τα αποτελεσματα σου.. ΤΟ dijkstra αλλαγμενο βοηθα επισης.. http://en.wikipedia.org/wiki/Shortest_path_problem Ισως θες τον breadth first επειδη τα θελεις ολα μα ολα..
nikolaos_ Δημοσ. 3 Ιουλίου 2011 Μέλος Δημοσ. 3 Ιουλίου 2011 Κύριος nikolaos_ , Για το τελευταιο ερώτημα αν δε το εχεις βρει γινεται ευκολα.. set @gid=0; set @num=1; SELECT *,@num := IF(@gid=gid,@num:=@num+1 ,1) as grad,@gid :=gid FROM PINAKS_SOU ORDER BY gid; Το πρόβλημα το έλυσα τελικά με μια πιο "στάνταρ" SQL προσέγγιση. >SELECT tid, gid, row_number() OVER (PARTITION BY gid ORDER BY result DESC, tid), result FROM v; Δουλεύω σε Postgresql και έχει διαθέσιμη μια συνάρτηση όπως την row_number, ενώ δοκίμασα τη δική σου λύση και δυστυχώς δεν δούλεψε. Αυτό το πέτυχα μόλις καμιά ώρα πριν κοιτάξω ξανά το insomnia και δω τη δική σου απάντηση. Σε ευχαριστώ πάρα πολύ για τον χρόνο που διέθεσες για την απάντηση. Οσο για το αλλο μαλλον ΔΕΝ γινεται με SQL. Πιθανον να κοιταξεις τον Breadth FIrst αλγοριθμο και δες αν σου κανει..Δε ξερω ποσο χρονο θα κανει αλλα ισως χρειαζεται καποια cache για τα αποτελεσματα σου.. ΤΟ dijkstra αλλαγμενο βοηθα επισης.. http://en.wikipedia.org/wiki/Shortest_path_problem Ισως θες τον breadth first επειδη τα θελεις ολα μα ολα.. Ναι, έχω εγκαταλείψει πλέον την προσπάθεια, να 'σαι καλά πάντως.
ΠάρηςΓ Δημοσ. 3 Ιουλίου 2011 Δημοσ. 3 Ιουλίου 2011 Εφοσον το υποστηριζει μια χαρά! ΓΙατι εγω αναφερομουν για Mysql..που δεν εχει τετοια καλουδια Οσο για το αλλο τι θα κανεις τελικα;
Aztec Δημοσ. 10 Ιουλίου 2011 Δημοσ. 10 Ιουλίου 2011 Λογικά αυτό που ζητάς με τους προορισμούς όπως το σκέφτομαι γίνεται με hierarchical query στην oracle. Δες αν η postgresql έχει κάτι αντίστοιχο.
Προτεινόμενες αναρτήσεις
Αρχειοθετημένο
Αυτό το θέμα έχει αρχειοθετηθεί και είναι κλειστό για περαιτέρω απαντήσεις.