PH.D DEFENCE - PUBLIC SEMINAR

Supporting Keyword Search in Temporal Databases

Speaker
Ms. Gao Qiao
Advisor
Dr Lee Mong Li, Professor, School of Computing
Dr Ling Tok Wang, Emeritus Professor, School of Computing


04 Nov 2020 Wednesday, 03:00 PM to 04:30 PM

Zoom presentation

Join Zoom meeting.
Meeting ID: 831 0195 8169
Link: https://nus-sg.zoom.us/j/83101958169?pwd=RTlwWmdTMHp6UktXMkNyeHQ0UGhxUT09
Password: 130057

Abstract:

Many organizations, especially in regulated industries such as finance and healthcare, need temporal databases to manage and maintain data that changes over time. Keyword search over temporal databases provides a convenient way for non-export users to query temporal databases without constructing complex SQL queries. However, the existing works did not consider the Object-Relationship-Attribute (ORA) semantics of the temporal databases in both database schema design and keyword query processing aspects, which leads to the inability of database to capture intended temporal and non-temporal semantics in real world, and the inability of the keyword query processing to capture intended query interpretations and return incorrect search results. Furthermore, aggregate functions, group-by and negation have not been supported in temporal keyword search, which limits the expensiveness of temporal keyword query. This thesis overcomes the above problems by adopting a semantic approach to design temporal database schema and process temporal keyword query.

In temporal database schema design, we develop a framework to help users create a temporal database schema from a traditional ER diagram. Our proposed temporal database schema captures both temporal and non-temporal ORA semantics. Two algorithms are proposed, one to generate a database schema in normal form relations, and another to generate normal form nested relations, which both handle the data redundancy caused by temporal attributes.

In temporal keyword query processing, we propose solutions to process the time condition, aggregate, GROUPBY, and negation in temporal keyword queries. The solutions utilize an Object-Relationship-Mixed (ORM) schema graph to capture the temporal and non-temporal ORA semantics of the temporal database, which facilitates the identification of objects and relationships involved in the query and whether they are temporal or not.

When handling the time condition in temporal keyword query, we first identify the temporal ORA semantics involved in the query, and then apply the time condition to generate a set of temporal constraints. Each temporal constraint depicts one possible interpretation of the time condition, and temporal join operators are used to retrieve the correct results. A prototype system is designed to support interactive keyword search with a two-level ranking scheme, which guides users to choose their intended query interpretation.

When handling the aggregates and GROUPBY in temporal keyword query, we observe that the data redundancy in the intermediate join relation could lead to incorrect temporal aggregate results. The ORA semantics is used to identify the unique objects/relationships and remove data duplicates in the intermediate relation. Aggregate over user-specified time unit is also supported to return meaningful results.

When handling negation in temporal keyword query, we consider whether the negation is applied to a single tuple or a set of tuples. While the former implies a logical NOT, the latter requires an anti-join or a temporal anti-join operator in order to obtain the correct results. When the negation is applied on some objects/relationships in a database, the scope of the negation are identified. Finally, multiple negation and nested negation are also supported in temporal keyword queries.