• Database security
• Distributed systems for standing subscriptions
• Information integration
• Privacy and anonymity in databases
• Semi-structured data repository and query processing
• Skyline query processing
• XML query evaluation and estimation
• Mobile databases
• Peer-to-peer database management
• Peer-to-peer technologies for distributed applications
• Query processing in peer-to-peer (P2P) systems
• Schema integration and schematic discrepancy
• Sensor network
• Spatio-temporal data mining

Database Security

Distributed Systems for Standing Subscriptions

Information Integration

The objective of this research is the design of strategies, techniques and tools for the integration and management of multi-modal and multimedia information from distributed, heterogeneous and autonomous sources. The approach is primarily grounded in database research. As such, it emphasises various ideas such as declarative query languages, conceptual data models, adaptive processing and optimisation of programs and queries, and the consideration of large numbers of users and large collections of data. Currently, the research focuses on the following themes: XML data management and processing, progressive processing of disparate information (stream processing), business process definitions management and integration, and algorithms for web information (clustering).

The research findings concern the semantic integration of disparate information sources, in particular, the integration and management of XML data. The integration and management of multi-modal information also concern textual and geographical information indexing, retrieval and extraction, as well as business processes management.

Our research achievements include:

• The first geographical search engine Global Atlas
• The X007 benchmark
• The iMinMax indexing technique for multidimensional data

Privacy and Anonymity in Databases

Organisations, such as government agencies, insurance companies and hospitals, need to release detailed data (e.g., medical records, financial data, etc.) for research and other public benefit purposes. However, sensitive personal information (e.g., disease of a specific person) may be revealed in this process, despite the hiding of identifying attributes, such as name or social security number. This is due to the existence of quasi-identifiers (QI), which are sets of attributes (e.g., ZIP, DateOfBirth, Sex) that can be used in conjunction with information obtained from a variety of sources (e.g., public voting registration data) to reveal the identity of individuals whose data is residing on the records. Indeed, a well-known study has found that 87% of the US population can be uniquely identified by the combination of ZIP, DateOfBirth, Sex. As more data is made available online, greater concern over privacy may be expected. Recent research has proposed k-Anonymity and l-Diversity to solve this problem. Both approaches involve generalisation (e.g., showing the area code instead of the exact phone number) or suppression (completely hiding some data), which inadvertently causes information loss.

Our research focuses on:

a) Developing a framework for efficient data transformations (i.e., k-Anonymity and l-Diversity), which minimises information loss (for the given k or l ). Most existing research employs many-to-one mappings to compute anonymised versions of original multi-dimensional data. We focus on more flexible many-to-many multi-dimensional mappings. Although it has been acknowledged that this method may achieve lower information loss, it has not received much attention because it is computationally expensive. To reduce computation cost, we use dimensionality reduction techniques and study efficient approximation algorithms in one-dimensional space.

b) Studying the dual problem: Given the maximum acceptable information loss, we seek to find a transformation that maximises privacy (i.e., k or l). Although this problem is significant in practice, it has not been studied before.

c) Extending our framework (i.e., anonymisation via dimensionality reduction) to related applications. Examples include location-based services (e.g., online maps), where the location of the querying user (rather than the data) must be anonymised, or stream data (e.g., data from sensors, stock market, etc.).

Semi-structured Data Repository and Query Processing

There has been increased interest in semi-structured data recently with the introduction of XML and related languages and technologies. Semi-structured data is claimed to be self-describing, making it important to define a schema for the data. The data models that have been proposed specifically for semi-structured data, (e.g. DOM, Dataguides, etc.), capture limited semantics in the data, and do not model the semantics expressed in the schema.

Although XML documents could have rather complex internal structures, they can generally be modelled as ordered trees. In most XML query languages, the structures of XML documents are expressed by twig patterns while the values of XML elements are used as part of selection predicates. Efficiently matching all twig patterns in an XML database is a major concern of XML query processing. Among them, the holistic twig join approach has been taken as an efficient way to match twig patterns through reducing intermediate results.

The project has so far achieved the following:

a) We have defined a data model called ORASS that captures richer semantics. Using this semantically rich data model, we have investigated and experimented with more efficient storage mechanisms, identified valid views of the base data, defined efficient view maintenance algorithms, and proposed methods for efficiently querying a semistructured data repository.

b) We have extended the existing Dewey node labelling technique and used it to improve twig pattern query processing.

c) We have developed new node labelling techniques to label dynamic XML data without re-labelling any node labels when the XML data is updated. Prior node labelling techniques used in twig pattern processing are designed for static XML data.

Skyline Query Processing

This project started in January 2005, and is funded by the Faculty Research Committee (FRC). The goal of this project is to investigate efficient techniques to process an important class of qualitative preference queries called skyline queries. A skyline query returns a set of records such that each returned record is not dominated by other records with respect to a userspecified set of attributes.

The project has so far achieved the following:

a) We have developed a novel framework and several scalable algorithms to efficiently process a generalised class of skyline queries that support data attributes with partially ordered domains.

b) We have introduced two novel notions of interesting skyline points (frequent skylines and k-dominant skylines), and developed efficient algorithms to compute them. These concepts are particularly important for high-dimensional data points in enabling a meaningful ranking of large sets of skyline query results.

XML Query Evaluation and Estimation

With the fast-growing use of XML data on the Web, optimising XML queries has become one of the most active and exciting research areas. Developments in query processing and selectivity estimations of XML data are among the major issues since they determine data access methods and the best possible execution plans for complex XML queries.

Our research in this area aims to develop efficient approaches for query evaluation and selectivity estimations of XML queries. We examine how path information in XML data can be utilised to speed up structural join, which is the core operation in XML query processing. The proposed solution comprises a path-based node labelling scheme and a path join algorithm. The path-based approach is also efficient for an important class of XML queries involving structural join with not-predicates.

We have also designed several methods for XML selectivity estimations. These include a compact statistical method, a histogram-based method for skewed XML data, and a path-based method for estimating the selectivity of XML queries with or without order-based axes.

The faculty members involved in database management systems are:

• BRESSAN Stephane
• CHAN Chee Yong
• HSU Wynne
• KALNIS Panagiotis
• LEE Mong Li
• LING Tok Wang
• OOI Beng Chin
• TAN Kian Lee
• TUNG Kum Hoe, Anthony