Computing Minimal Equivalent Database Queries under Ontologies/Dependencies
Supervisors
Suitable for
Abstract
Ontologies or dependencies over databases, are sets of constraints that describe relationships among the tables in a database (such as functional dependencies, key constraints, RDF, DL-Lite, OWL-2QL, and others). This project deals with computing minimal equivalent queries under such constraints. Computing equivalent expressions for the same query is a common problem in areas such as query planning and data integration, while computing minimal expressions is a key strategy in query optimization. Focusing on the simple query language of conjunctive queries (i.e., SELECT-PROJECT-JOIN queries in SQL), and exploiting properties of certain classes of constraints, efficient algorithms can be developed for producing the set of all minimal equivalent query rewritings.
The student will work on refining existing algorithms and implementing a module for efficient computation of all minimal equivalent expressions to a given query, for a particular constraint language. The project builds upon an already developed algorithm, and can lead to a practical system, as well as research publications.
Prerequisites: Good Java implementation skills are required. Familiarity with databases and query rewriting is highly desirable.