CMPS278 - List of Suggested Projects

• Experimental Evaluation of Rank-Aware Plans. A ranking query retrieves the top few results of an SPJ query based on a scoring function. As an example, consider a sample database that stores information about visitors to a specific area. Assume that a visitor wants to plan out a short stay that includes a hotel, a restaurant, and an event. The following query will retrieve the top-10 combinations of such results, based on the rating of the hotel, the rating of the restaurant, and the type of the event:

  	SELECT r.name, h.name, e.title
  	FROM Restaurant r, Hotel h, Event e
  	WHERE r.city = h.city AND h.city = e.city
  	RANK BY 0.4 * r.rating + 0.4 * h.rating + 0.2 * contains(e.title,"Music")
  	LIMIT 10
  				

  The topic of this project is to evaluate experimentally different physical plans for answering this type of queries. In particular, the project will consider plans that use a specific join algorithm, termed HRJN*. There are theoretical results on the optimality of this algorithm for the specific type of queries. The goal of the project is to corroborate the theoretical results with an experimental evaluation.
• Data Statistics in a P2P Database System. In a P2P DBMS, the data is distributed among all the participating peers, and each peer contributes computational resources for evaluating queries over the available data. A key issue in this context is the gathering of data statistics that will allow the optimizer to make smart decisions on the evaluation of distributed queries. Given the characteristics of the system, there are two obvious requirements for gathering such statistics: (a) they must be gathered automatically, since there is no central administrator, and (b) they must be distributed, following the principles of P2P. The goal of this project is to investigate a solution for a P2P DBMS that handles XML data. The starting point will be a recently proposed scheme for gathering statistics in a centralized context. The project will involve the extension of this scheme to a distributed setting (according to the previous requirements) and an experimental evaluation.
• Porting the KadoP system over a network simulator (2-person team). KadoP is a P2P DBMS that enables the sharing and querying of XML data. KadoP is implemented in Java and has been evaluated experimentally over a real network of autonomous peers. The goal of this project is to perform a simulation-based evaluation of the system. Towards this goal, KadoP will be ported over PIER, a Java platform that allows the same system code to run on top of both a simulated and an actual network of peers. (The source code of KadoP and PIER will be made available.) The project will also involve a simulation-based evaluation of the ported KadoP system.
• Experimental Study of Summarization Techniques for Unstructured Text Data. Unstructured text data are ubiquitous and form a significant portion of the data stored in large enterprises. One interesting class of queries in this context are proximity queries, of the form: "Find all documents that contain the terms 'query', 'optimization', and 'database', in a window of size 5". The development of optimization techniques for such queries depends on the maintenance of statistics on the distribution of words in the textual content. TextSamples attempt to solve this problem by performing a careful sample of the words that appear in a text corpus. The goal of this project is the experimental study of TextSamples over several real-life text corpora, in order to characterize the effectiveness of the technique relative to the characteristics of the textual data. (The code for TextSamples will be made available for this project.)
• Sketching techniques for XML data. Randomized sketching techniques, that have been developed in the context of relational databases, can build a concise statistical summary of the base data by performing a single scan over the database. The goal of this project is to investigate the application of these techniques to the XML domain, by extending a recently proposed sketching technique for spatial data.
• Joining a fast stream with a non-static relation. The MeshJoin operator is a recently proposed algorithm for joining a fast stream of tuples with a large disk-resident relation. This scenario arises frequently in the emerging paradigm of active data warehouses, where the warehouse is kept continuously up-to-date with respect to a stream of updates that come from the data sources. The original MeshJoin algorithm is defined for a relation that is static, i.e., the relation is not modified while the join is computed. The goal of this project is to extend MeshJoin to the case of a non-static relation, i.e., a relation that is updated while the join occurs.
• Integration of MeshJoin in the Postgres DBMS. The goal of this project is the integration of the MeshJoin operator in the Postgres DBMS. The project will also involve an experimental study of the implemented algorithm in Postgres.