CS748M Projects

• Implementation of a Temporal Extension of the SQL language (implementation)

  SQL/TP [Toman97b] was proposed as a clean temporal extension SQL, the standard language of relational databases, to facilitate handling time-dependent data in a natural and efficient way. The goal of this project is to implement a SQL/TP-to-SQL compiler to serve as a front-end of a standard relational DBMS. The implementation will be carried out in two steps:

  1. the implementation of an source to source compiler (that accepts SQL/TP input and emits standard SQL translations), and
  2. the Java/JDBC based interface to a generic relational engine
  To facilitate the second goal, the whole implementation will be carried out in Java. Future extensions include optimization of the emitted code (potentially specific to the target database system), extending the capabilities of SQL/TP, and adopting the compilation approach to other application domains, e.g., to spatial and GIS systems.

• Memoing Evaluation of Constraint Extension(s) of Datalog (implementation)

  XSB [SSW95] is a sophisticated Prolog system that includes capabilities of deductive databases. In addition, it provides very efficient engine for evaluation of deductive queries. Unfortunately, these advantages apply only to manipulation of uninterpreted constants (and terms in the case of Prolog programs). However, in many applications we need to manipulate inherently interpreted values (e.g., time). Here, we can take an advantage of the constraint technology: several constraint extensions of Datalog (a function-free subset of Prolog) have been shown to have amenable properties. In this project we plan to integrate the constraint-handling facilities into XSB based on the technique introduced in [Toman97b,Toman96]. The implementation will provide

  1. an implementation of constraint operations (in Prolog, if feasible),
  2. an interface between the XSB engine and operations on the constraint representation, and
  3. a generic extension to the XSB engine that implements the above interface specification (possibly with a suitable fall-back operations).
  The XSB system has been successfully applied to verification of concurrent systems (using finite model checking). We plan to apply our extension to timed version of the above approach (which can't be easily accommodated by the current implementation).

• Statistical Methods in Data Mining (survey)

  In the recent few years data Mining became one of the hottest topics in databases (as there is a lot of money to be made). In this project we propose to study the application of techniques used in statistics to problems in data mining. We try to give answers to the following questions:

  1. how do statistical methods and data mining methods relate, e.g., do they subsume each other (one way)?
  2. how can/should the results of data mining be interpreted?
  3. can we use statistical methods instead of data mining? cheaply?
  4. can the usual statistical methods be applied efficiently on large sets of data?
  We also plan to survey the common data mining methods and compare them against their statistics counterparts (if any).

• Closure properties of queries and encodings (theory)

  A classical problem of relational queries is preserving closure under a chosen encoding of databases: in the standard relational setting this requirement boils down to preserving finiteness of answers to queries over finite relations. However, when a more sophisticated encoding iss used (e.g., a constraint-based encoding), the safety and closure questions re-emerge: for a given encoding of data (based on a class of constraints) and a query language (based on potentially different class of constraints) we want to find answers to the following questions:

  1. can answers to queries in the language be represented using the chosen encoding?
  2. if not (which is likely), is there a non-trivial class of queries that do preserve the encoding? Is it syntactically definable? Large enough (covering all closed queries of the original language?
  3. is safety decidable (not likely) or is there a syntactic approximation of safety?
  The goal of this project is to study the above interactions between various encoding-language pairs.

• Termination for constraint extensions of Datalog (theory)

  Datalog is a query language of function-free horn clauses that allows formulation of advanced queries which cannot be asked in standard SQL. An inherent feature of Datalog is that, despite of the recursive nature of the queries (and unlike Prolog, its bigger brother), it guarantees termination for all queries. To extend the application range of Datalog, several constraint extensions of the language have been proposed in the literature, all of them guaranteeing termination. However, the termination arguments are complicated. [Toman97a] has proposed a sufficient condition on the constraint theory (constraint compactness) that guarantees termination. However, the conjecture about the necessity of this condition is still open. In this project we study necessary conditions a constraint theory has to satisfy for all Datalog queries to terminate. We may also study classes queries between first-order (trivial) and full Datalog (possibly with well-founded negation) and their termination properties.

[Toman97b] Toman, D. A Point-based Temporal Extension of SQL Proc. DOOD'97.

[Toman96] Toman, D. Computing the Well-founded Semantics for Constraint Extensions of Datalog. Proc. CP'96 workshop on Constraint Databases, Cambridge, MA, LNCS 1191 (Constraint Databases and Applications).

[SSW95] Sagonas, Swift, and Warren. An Abstract Machine for the Well-Founded Semantics.