Επόμενη: SLD -Δέντρα Πάνω Επίπεδο: Ανάλυση Προηγούμενη: Η Αρχή της Ανάλυσης 

4.6 SLD -Ανάλυση

Η SLD- ανάλυση προτάθηκε από τον Kowalski. Το όνομά της σημαίνει SL- ανάλυση για οριστικές (Definite) προτάσεις και είναι βασισμένη στην ανάλυση εισόδου (input resolution), η οποία είναι ένας περαιτέρω περιορισμός της γραμμικής ανάλυσης και απαιτεί μια από τις γονικές προτάσεις σε κάθε βήμα ανάλυσης να είναι πρόταση εισόδου. Η SLD- ανάλυση είναι απλούστερη από την ανάλυση χωρίς περιορισμούς ή τη γραμμική, αλλά μπορεί να εφαρμοστεί μόνο σε προτάσεις Horn (Horn clauses).

Μια πρόταση Horn (Horn clause) (οφείλει το όνομά της στον λογικό Alfred Horn) είναι είτε μια οριστική προγραμματική πρόταση (definite program clause), είτε ένας οριστικός στόχος (definite goal). Μια οριστική προγραμματική πρόταση είναι μια πρόταση που περιέχει ένα θετικό και κανένα ή περισσότερα αρνητικά λεκτικά στοιχεία. 'Ενας οριστικός στόχος είναι μια πρόταση που περιέχει μόνο αρνητικά λεκτικά στοιχεία. Θα ονομάζουμε οριστικό πρόγραμμα ένα πεπερασμένο σύνολο από οριστικές προγραμματικές προτάσεις - συνήθως θα το συμβολίζουμε .

Εάν μια οριστική προγραμματική πρόταση αποτελείται από το θετικό λεκτικό στοιχείο A και από τα αρνητικά λεκτικά στοιχεία , τότε η πρόταση αυτή μπορεί να γραφεί, ισοδύναμα, στη μορφή

ή

όπου το A ονομάζεται κεφαλή (head) της πρότασης και το κομμάτι  σώμα (body) της πρότασης. Στην περίπτωση ενός μόνον ατόμου (m=0) μπορούμε να παραλείψουμε το σύμβολο ``''. 'Ενας οριστικός στόχος μπορεί να γραφεί στη μορφή

Επίσης, η κενή πρόταση θεωρείται στόχος.

Το σύνολο των προτάσεων Horn είναι ένας περιορισμός του συνόλου όλων των τύπων, αφού υπάρχουν τύποι που δεν μπορούν να γραφούν στη μορφή αυτή. Ωστόσο, οι προτάσεις Horn είναι ευκολότερες στο χειρισμό σε σχέση με τις γενικές προτάσεις. Η γλώσσα Horn από ένα αλφάβητο, είναι το σύνολο όλων των προτάσεων Horn που μπορούν να σχηματιστούν από τα σύμβολα του εν λόγω αλφαβήτου.

Ας είναι  ένα σύνολο προτάσεων Horn και C μια πρόταση Horn. Ονομάζουμε SLD- παραγωγή μήκους k της C από το , μια πεπερασμένη ακολουθία προτάσεων Horn

τέτοια ώστε  και κάθε  είναι ένα δυαδικό αναλυθέν ενός επιλεγμένου ατόμου στο σώμα του R_j-1 και της κεφαλής μιας οριστικής προγραμματικής πρότασης C_j από το . Το άτομο αυτό είναι δυνατό να επιλεγεί με χρήση ενός κανόνα υπολογισμού (computation rule) ή, όπως αλλιώς λέγεται, ενός κανόνα επιλογής (selection rule). Η R₀ ονομάζεται κορυφαία πρόταση (top clause) και οι C_j προτάσεις εισόδου (input clauses) της SLD- παραγωγής. Μια SLD- παραγωγή της κενής πρότασης από το  θα ονομάζεται SLD- άρνηση του .

Αν  είναι ένα οριστικό πρόγραμμα, G ένας οριστικός στόχος και  η ακολουθία των γενικότερων ταυτοποιητών που χρησιμοποιούνται σε κάποια SLD- άρνηση του , τότε το αποτέλεσμα του  ονομάζεται υπολογισμένη απάντηση (computed answer)  για το  και ισούται με τον περιορισμό της σύνθεσης  στις μεταβλητές του G, όπου υποθέσαμε ότι  .

Ο προηγούμενος ορισμός προϋποθέτει ότι κάθε πρόταση εισόδου C_j δεν έχει κοινές μεταβλητές με το στόχο G αλλά ούτε και με προηγούμενες προτάσεις εισόδου και γενικότερους ταυτοποιητές. Τούτο μπορεί να επιτευχθεί με τη μετονομασία κάποιων μεταβλητών στις προτάσεις εισόδου. Για παράδειγμα, ας θεωρήσουμε το επόμενο πρόγραμμα :
 

Αν , τότε η SLD- άρνηση του  φαίνεται στο σχ. 4.6α , όπου τα  είναι οι γενικότεροι ταυτοποιητές που χρησιμοποιούνται σε κάθε βήμα. Ο κανόνας υπολογισμού σ' αυτό το παράδειγμα επιλέγει το αριστερότερο άτομο σε κάθε στόχο (υπογραμμισμένα άτομα).

  
Σχήμα 4.6α: SLD- άρνηση με επιλογή του αριστερότερου στόχου
 

Η υπολογισμένη απάντηση είναι , αφού . Στο προηγούμενο παράδειγμα, αν χρησιμοποιήσουμε ένα κανόνα υπολογισμού ο οποίος επιλέγει πάντοτε το δεξιότερο άτομο σ' ένα στόχο, θα πάρουμε την ίδια υπολογισμένη απάντηση  (βλ. σχ. 4.7α  ).
 

Mon Apr 5 16:25:43 EEST 1999