1. Home page
  2. Search

The Expressive Power of Higher-Order Datalog with Negation

This item is provided by the institution :
/aggregator-openarchives/portal/institutions/uoa   

Repository :
Pergamos Digital Library   

see the original item page
in the repository's web site and access all digital files if the item*



The Expressive Power of Higher-Order Datalog with Negation
Κωστόπουλος Χαράλαμπος (EL)
Kostopoulos Charalampos (EN)
born_digital_postgraduate_thesis
Διπλωματική Εργασία (EL)
Postgraduate Thesis (EN)
2023
Είναι γνωστό αποτέλεσμα στη βιβλιογραφία ότι η Datalog με την υπόθεση ότι οι βάσεις δεδομένων εισόδου είναι διατεταγμένες, μπορεί να εκφράσει όλα εκείνα τα ερωτήματα που ανήκουν στην κλάση πολυπλοκότητας PTIME. Πρόσφατα, αυτό το αποτέλεσμα επεκτάθηκε και σε προγράμματα Datalog υψηλής τάξης που δεν περιέχουν άρνηση και αποδείχτηκε οτι η εκφραστικότητα αυξάνεται αυστηρά καθώς αυξάνεται και η τάξη των προγραμμάτων. Αυτή η διπλωματική μελετάει την εκφραστικότητα προγραμμάτων υψηλής τάξης Datalog όταν επιτρέπουμε άρνηση. Πιο συγκεκριμένα παρουσιάζεται μια ανάλυση της εκφραστικότητας διαφόρων εκδόσεων της υψηλής τάξης Datalog όπου κάθε φορά επιτρέπουμε ένα υποσύνολο από χαρακτηριστικά όπως η άρνηση, μερικώς εφαρμοσμένες εκφράσεις ως ορίσματα και υπαρξιακές μεταβλητές υψηλής τάξης. Σε κάθε επιλογή τέτοιων χαρακτηριστικών μελετάμε την επίδραση της αύξησης της επιτρεπόμενης τάξης των προγραμμάτων στην εκφραστικότητα της γλώσσας. Προκύπτει ότι η εκφραστικότητα δεν αυξάνεται περαιτέρω όταν εισάγουμε τον τελεστή της άρνησης. Αν όμως δεν επιτρέψουμε μερικώς εφαρμοσμένες εκφράσεις στα προγράμματά μας τότε υπάρχει σημαντική διαφορά. Οι μερικώς εφαρμοσμένες εκφράσεις στα προγράμματα δίνουν από μόνες τους την μέγιστη εκφραστικότητα της γλώσσας σε διατεταγμένες βάσεις, ενώ αν απουσιάζουν χρειαζόμαστε άρνηση με υπαρξιακές μεταβλητές για να πετύχουμε την ίδια εκφραστικότητα. Σε όλες τις άλλες περιπτώσεις η εκφραστικότητα της γλώσσας πέφτει στην κλάση PTIME ανεξαρτήτως της τάξης που επιτρέπουμε να έχουν οι τύποι στα προγράμματά μας. (EL)
It is a well-known result that Datalog, with the added assumption that the input databases are ordered, can express exactly those queries that belong in class PTIME. Recently, this result was extended for higher-order Datalog that does not contain negation. It appears that an increase in the order allowed in the programs results in a direct increase in expressiveness. This thesis studies the expressiveness of higher-order Datalog when we introduce negation. More specifically, we present a study of the expressiveness of different higher-order Datalog language fragments where each time a subset of features is allowed from negation, partially-applied expressions as predicate arguments, and higher-order existential variables. For each such choice of features, we investigate the resulting expressiveness as we increase the order for the types we allow in our programs. It follows that the original expressiveness result is not changed when we just introduce negation. However, in the case that we restrict partial application from our syntax, there i s a big difference. Partially-applied expressions can alone give the maximum expressiveness achieved by higher-order Datalog in ordered databases while in their absence only negation paired with higher-order existential variables can achieve the same result. Finally, all other choices of features result in a collapse in PTIME for the problems the language fragments can express regardless of the order we allow in our programs. (EN)
Θετικές Επιστήμες
Θετικές Επιστήμες (EL)
Science (EN)
English
Βιβλιοθήκη και Κέντρο Πληροφόρησης » Βιβλιοθήκη Σχολής Θετικών Επιστημών » Πληροφορική
Σχολή Θετικών Επιστημών » Τμήμα Πληροφορικής & Τηλεπικοινωνιών » Διιδρυματικό ΠΜΣ Αλγόριθμοι, Λογική και Διακριτά Μαθηματικά (Α.Λ.ΜΑ.) » Κατεύθυνση Αλγόριθμοι, Λογική και Διακριτά Μαθηματικά (Α.Λ.ΜΑ.)
https://creativecommons.org/licenses/by-nc/4.0/
University of Athens
Pergamos Digital Library
Postgraduate Thesis



*Institutions are responsible for keeping their URLs functional (digital file, item page in repository site)