Budapest University of Technology and Economics, Faculty of Electrical Engineering and Informatics

    Belépés
    címtáras azonosítással

    vissza a tantárgylistához   nyomtatható verzió    

    Semantic and Declarative Technologies

    A tantárgy neve magyarul / Name of the subject in Hungarian: Szemantikus és deklaratív technológiák

    Last updated: 2010. november 11.

    Budapest University of Technology and Economics
    Faculty of Electrical Engineering and Informatics

    Mérnök informatikus szak

    BSc képzés

    Course ID Semester Assessment Credit Tantárgyfélév
    VISZA090   3/1/0/v 4  
    3. Course coordinator and department Dr. Szeredi Péter,
    Web page of the course www.cs.bme.hu/....
    4. Instructors
    Name

     

    Position

     

    Department

     

    Péter SZEREDI

     

    Assoc. professor

     

    Department of Computer Science and Information Theory

     

    Gergely LUKÁCSY

     

    Lecturer

     

    Department of Computer Science and Information Theory

     

    Zsolt ZOMBORI

     

    PhD student

     

    Department of Computer Science and Information Theory

     

    7. Objectives, learning outcomes and obtained knowledge The objective of the first half of the course is to give an introduction to semantic technologies in general, and to the Semantic Web, its languages and tools, in particular. The course also discusses Description Logics, as the mathematical background for semantic technologies.

     

    Semantic technologies are about bringing semantics, i.e. meaning into various computer applications.  In the forefront of this research is the Semantic Web initiative, which aims at making web search much more intelligent than today. Its vision is to make it possible for the computers to understand the information available on the web, as opposed to the current search engines, which merely read this information.

     

    Several steps are needed for this vision to come true. First, the textual information on the web has to be transformed – either manually, or, preferably, automatically – into formal, structured statements. Second, the common background knowledge, which we take for granted when reading a text, has to be formalized, i.e. transformed into computer processable format, as well.  Note that a collection of formal statements of both these kinds is often called an ontology.  Third, a reasoning engine has to be developed, which is capable of deriving new pieces of information from the old ones.

     

    The World Wide Web Consortium (W3C) has published several standards for formalizing knowledge on the web. The Resource Description Framework (RDF) makes it possible to include formal statements in the web pages, while the RDF Schema (RDFS) allows for formulating simple forms of background knowledge. The Web Ontology Language (OWL) supports more complex forms of background knowledge, while still offering efficient reasoning capabilities.

     

    Description Logics (DLs) is a family of formal languages each of which is a subset of first order logic. DLs provide the mathematical background for the RDF, RDFS and OWL languages, while the theorem proving algorithms for DLs are used in the reasoning engines developed for the Semantic Web languages.

     

     

    The objective of the second half of the course is to give an introduction to declarative programming with emphasis on logic programming and constraints.

     

    The slogan of declarative programming is "WHAT rather than HOW". This is because a declarative program consists of statements about the problem being solved (WHAT to solve), as opposed to traditional imperative programs, which contain instructions to carry out some actions (HOW to solve the problem). Such actions, most of the time, change program variables, i.e. modify memory locations.  Declarative programs only have single assignment variables, which denote a single but possibly unknown entity, similarly to variables used in mathematical arguments.

     

    Within the declarative paradigm there are two main directions: functional programming, which is built around functions; and logic programming, which uses relations.  The LISP language, developed in late 1950's, was the first functional language, followed by several more sophisticated languages, such as SML, Haskell and Erlang, just to mention a few. The Prolog language, originating in early 1970's, is the first and still the most widespread logic programming language.

     

    A Prolog program can be read in two ways: as a collection of formal statements (declarative semantics) and as instructions on how to reduce a problem to solving some other (sub)problems (procedural semantics). These two faces of Prolog reflect the WHAT and the HOW side of problem solving, although the HOW part is on a much higher level than in imperative languages. This is because the Prolog problem reduction mechanism is based on pattern matching, and is non-deterministic. The latter means that Prolog uses backtracking to try multiple reductions, until a successful one is found.

     

    The constraint logic programming (CLP) paradigm was introduced in late 1980's, and implemented mostly as an extension to Prolog.  The generic schema CLP(X) extends Prolog with specific relations (constraints) within the domain X, and also adds strong reasoning capabilities in this domain. The most developed and most widely used variant is CLP(FD), where FD stands for finite domain. CLP(FD) uses the techniques of Constraint Satisfaction Problems (CSP), a branch of Artificial Intelligence.

     

    The course is a practical introduction to Prolog and CLP(FD) using SICStus Prolog, one of the most widely used and most efficient Prolog implementations.  As motivating examples we develop several variants of solvers and generators for Sudoku puzzles.

     

     

    8. Synopsis First half-semester

     

    1. Introduction

     

       Semantic technologies – what are they?

     

       Problem classes to be solved by semantic technologies – some examples.

     

       The vision of the Semantic Web.

     

       Basic technologies of the today's web: HTML, XML.

     

       A roadmap from the today's internet to the Semantic Web.

     

     

    2. The Resource Description Framework

     

       The basics of RDF: Uniform Resource Identifiers (URIs), triples, various syntactic notations.

     

       Advanced RDF constructs: reification, containers, collections.

     

       The RDF Schema: classes, properties, hierarchies, restrictions.

     

     

    3. Description Logics

     

       Terminological and assertional knowledge: the TBox and the ABox.

     

       The main building stones of DLs: concepts and roles.

     

       A hierarchy of DL languages: AL, ALC, SHIQ, SROIQ and beyond.

     

       Reasoning tasks for DLs.  

     

     

    4. The Web Ontology Language

     

       Constructs for building classes: property restriction, intersection, union, complement.

     

       Class axioms: subclasses, equivalence and disjointness.

     

       Property axioms: subproperties, equivalent and inverse properties.

     

       OWL sublanguages: OWL Lite, OWL DL and OWL Full.  

     

     

    5. Building and using ontologies

     

       The Protégé ontology editor, its user interface and services.

     

       Analyzing and querying ontologies.

     

       The underlying reasoning algorithms – a brief overview.

     

       Example ontology: Wine.     

     

     

    6. Semantic Technologies beyond the Semantic Web – an outlook

     

       Semantic aspects of Enterprise Application Integration.

     

       Semantic Web Services.

     

       Related technologies: decision support systems, rule-based languages, declarative programming.

     

     

    Second half-semester

     

    7. Introduction

     

       Imperative and declarative programming, a comparison.

     

       The two main declarative paradigms: logic and functional programming.

     

       A motivating example: a solver for the Sudoku puzzle.

     

     

    8. The Prolog programming language – basic principles

     

       The declarative semantics of Prolog: deducibility.

     

       The procedural semantics: unification (pattern matching), backtracking search.

     

       Terms as data structures; syntactic sugar: lists, operators.

     

       Negation and if-then-else.

     

     

    9. Programming in Prolog, part I

     

       The SICStus Prolog system.

     

       Tools for program development and debugging.

     

       Basic programming techniques.

     

     

    10. Programming in Prolog, part II

     

       Built-in predicates: control, all-solutions, meta-logic.

     

       Efficiency issues: tail-recursion, accumulators, using logic variables. 

     

       The Sudoku solver revisited.

     

     

    11. Constraint programming

     

       Finite domain constraints, constraint satisfaction problems.

     

       The SICStus Prolog finite domain library.

     

       The Sudoku solver generalized and made efficient.

     

       A Sudoku puzzle generator.

     

     

    12. Declarative programming in practice – an outlook

     

       Major implementations of declarative languages.

     

       Application areas of declarative programming.

     

       Declarative technologies and parallel/multi-core computing. 

     

     

    9. Method of instruction Lectures, recitations, project-based group work

     

    10. Assessment The grading of students is based on the following criteria:

     

     

      - class participation and activity:      20 points

     

      - mid-term tests                                 20 points

     

      - assignment:                                     20 points

     

      - final exam                                       40 points.

     

     

    The mid-term tests are written in Weeks 4 and 10.

     

     

    Assignments: The students are required to develop

     

    (1)   a simple ontology using the Protégé editor, together with its documentation in the first half-semester and

     

    (2)   a simple puzzle solver in Prolog, together with its documentation.

     

    12. Consultations You can reach the instructor at the following e-mail address for consultation:

     

    Péter SZEREDI : szeredi@cs.bme.hu

     

    13. References, textbooks and resources

    Szeredi, P., Lukácsy, G., Benkő, T.: The Semantic Web Explained, Cambridge University Press, 2009.

     

    Clocksin, W.F., Mellish, C.S.: Programming in Prolog using the ISO standard, Springer Verlag, 2003.

     

    14. Required learning hours and assignment
    Number of contact hours

     

    56

     

    Preparation to the classes

     

    18

     

    Preparation to the tests

     

    20

     

    Homework

     

    6

     

    Assigned reading

     

     

    Preparation to the exam

     

    20

     

    Total

     

    120

     

    15. Syllabus prepared by
    Name

     

    Position

     

    Department

     

    Péter SZEREDI

     

    Assoc. professor

     

    Department of Computer Science and Information Theory