SubjectsSubjects(version: 837)
Course, academic year 2018/2019
   Login via CAS
Query Languages II - NDBI006
Title in English: Dotazovací jazyky II
Guaranteed by: Department of Software Engineering (32-KSI)
Faculty: Faculty of Mathematics and Physics
Actual: from 2017 to 2018
Semester: summer
E-Credits: 5
Hours per week, examination: summer s.:2/2 C+Ex [hours/week]
Capacity: unlimited
Min. number of students: unlimited
State of the course: taught
Language: Czech, English
Teaching methods: full-time
Additional information: http://www.ksi.mff.cuni.cz/~pokorny/vyuka.html#NDBI006, http://www.ksi.mff.cuni.cz/~vojtas/vyuka/vyuka.html
Guarantor: prof. RNDr. Jaroslav Pokorný, CSc.
prof. RNDr. Peter Vojtáš, DrSc.
Class: Informatika Mgr. - volitelný
Classification: Informatics > Database Systems
Annotation -
Last update: doc. RNDr. Pavel Töpfer, CSc. (16.03.2018)
Equivalence of the relational algebra (RA) and DRC restricted to definite formulas. Transitive closure of a relation. The least fixpoint of a mapping, minimal fixpoint. Datalog without recursion, with recursion, with negation, stratification. Recursive SQL. Graph query languages. Tableau query as visual query interface for e-shops - static analysis, inclusion, optimization, complexity. Datalog with recursion and functional symbols.
Course completion requirements -
Last update: prof. RNDr. Jaroslav Pokorný, CSc. (02.10.2017)

For completing the course through the exam it is necessary to obtain a credit based on

a preparation of a paper for the course colloquium. The student's slide presentation is prepared and presented on the basis of materials given by the teacher.

In the case of a larger number of students, the presentation can be created as a report only in written form. Another option permits the possibility of 2 students for the paper and its presentation.

Literature -
Last update: RNDr. Michal Kopecký, Ph.D. (11.05.2017)
  • Robinson, I., Webber, J., Eifrem, E.: Graph Databases - The Definitive Book on Graph Databases. O'Reilly Media, 2013
  • Abiteboul S., Hull R., Vianu V.: Foundations of Databases, Addison-Wesley 1995
  • Lloyd, John W. Foundations of Logic Programming, Springer 1987
  • Eric Ries. The Lean Startup: How Today's Entrepreneurs Use Continuous Innovation to Create Radically Successful Businesses. Crown Business 2011

Slides:

http://www.ksi.mff.cuni.cz/~pokorny/vyuka.html#NDBI006/

http://www.ksi.mff.cuni.cz/~vojtas/vyuka/vyuka.html

Syllabus -
Last update: RNDr. Michal Kopecký, Ph.D. (11.05.2017)

1. Three semantics of Domain Relational Calculus (DRC). Definite and safe expressions in DRC. Equivalence of the relational algebra (RA) and DRC restricted to definite formulas.

2. Inexpressibility of the transitive closure of a relation in RA.

3. Composition of relational algebra expressions, least fixpoint of a mapping, minimal fixpoint. Datalog - three possible semantics of the language. Evaluation of a logical program without recursion.

4. Datalog with recursion. Naive valuation method, method of differences.

5. Datalog with negation, stratification. Expressive power of Datalog. Relationship to other relational languages. Deductive databases. Logical problems of information systems.

6. Recursive SQL

7. Graph databases and graph query languages.

8. Tableau query as visual query interface for e-shops, conjunctive query containment and homomorphism theorem.

10. Tableau query with inequality for e-shops

11. Tableau query and algorithmic complexity of query inclusion.

12. Formal framework for transferability of querying models

13. Datalog with recursion and functional symbols.

14. Datalog with recursion and functional symbols - completeness.

 
Charles University | Information system of Charles University | http://www.cuni.cz/UKEN-329.html