Grant: Discovery Grants Program - Individual
Concordia University
$18,000.00
Uncertain Relational Database Management and Integration Systems: Concepts and Techniques
FY 2015-16
Summary
Many applications in diverse domains require the ability to store and process voluminous uncertain data. While traditional database management systems (DBMS) have been quite successful in handling precise data and missing values, they offer little or no support for uncertain data. What is also needed is the ability to ""quantify"" the integrity of the data. Informally, a piece of data is uncertain if its truth is not established definitely. Uncertainty has been studied extensively for over two decades in database and AI communities, resulting in a substantial body of principles, concepts, representations, and algorithms. However, more work is required to develop better solutions for a full realization of uncertain data management. This explains recent increased attention to the subject in database research, and the motivation of this proposal. The major problems include (1) semantics (representations), (2) evaluation (correct and efficient processing),<span style=""line-height: 1.5em;""> and (3) usability (ease of use). These problems which are related stem from the semantics of uncertain databases, defined based on the notion of possible worlds: essentially a set of standard relational databases only one of which represents the true state of the database, but we don't know exactly which one. The problem with the semantics is the exponential size of the possible worlds in the number of tuples in the database. To illustrate this, consider two scenarios of modeling uncertainty at attribute level and at tuple level. If a tuple in a relation has n alternative values for an attribute, then there are n relations in the possible worlds w.r.t. to this tuple. Analogously, if presence of a tuple t in a relation R is not sure, then R has two possible worlds, one which includes t and the other which doesn't. Probabilistic databases are uncertain databases with probabilities defined over the corresponding possible worlds. The main approach in related literature has been extending the concepts and techniques from traditional databases. A major difficulty is ensuring the ""correctness"" of query results, as different correlation assumptions among tuples require different run-time control and tracking algorithms. This turns query processing into reasoning which is more complex, if not infeasible. The expected outcomes include (1) novel query processing and rewriting techniques for extended relational algebra operations with desired semantics, (2) development of extended algebra techniques into an integrated calculator , and (3) development of prototype subsystems for uncertain data management and integration. All the practical work in this research will be evaluated experimentally. The research is anticipated to provide a more comprehensive understanding of uncertain data and the needs. I believe<span style=""line-height: 1.5em;""> that uncertain data research will influence, if not lead to, the <span style=""line-height: 1.5em;"">development of next generation DBMSs.<span style=""line-height: 1.5em;""> This research will make a leap in this direction.
Program
Discovery Grants Program - Individual
Recipient
Location
Quebec, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data
As published
Application id
RGPIN-2015-04145
Name nom
ShiriVarnaamkhaasti, Nematollaah
Department département
Computer Science and Software Engineering - Computer Science and Software Engine
Organization id
70
Institution établissement
Concordia University
Province en
Québec
Province fr
Québec
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2015
Competition year année de concours
2015
Award amount
18000
Program id
RGPIN
Program name en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
Discovery grants programs
Group fr
Programmes de subventions à la découverte
Committee code
1507
Committee name en
Computer Science
Committee name fr
Sciences informatiques
Area of application code
802
Area of application group en
Information and communication services
Area of application group fr
Services d'information et de télécommunications
Area of application en
Information systems and technology
Area of application fr
Systèmes d'information et technologie de l'information
Research subject code
2711
Research subject group en
Information technology
Research subject group fr
Technologie de l'information
Research subject en
Database management
Research subject fr
Gestion de bases de données
Partie
1
Nb partie
1
Application title
Uncertain Relational Database Management and Integration Systems: Concepts and Techniques
Keyword
NSERC
Application summary
<p>Many applications in diverse domains require the ability to store and process voluminous uncertain data. While traditional database management systems (DBMS) have been quite successful in handling precise data and missing values, they offer little or no support for uncertain data. What is also needed is the ability to ""quantify"" the integrity of the data. Informally, a piece of data is uncertain if its truth is not established definitely. Uncertainty has been studied extensively for over two decades in database and AI communities, resulting in a substantial body of principles, concepts, representations, and algorithms. However, more work is required to develop better solutions for a full realization of uncertain data management. This explains recent increased attention to the subject in database research, and the motivation of this proposal. The major problems include (1) semantics (representations), (2) evaluation (correct and efficient processing),<span style=""line-height: 1.5em;""> and (3) usability (ease of use). These problems which are related stem from the semantics of uncertain databases, defined based on the notion of <em>possible worlds</em>: essentially a set of standard relational databases only one of which represents the true state of the database, but we don't know exactly which one. The problem with the semantics is the exponential size of the possible worlds in the number of tuples in the database. To illustrate this, consider two scenarios of modeling uncertainty at attribute level and at tuple level. If a tuple in a relation has <em>n</em> alternative values for an attribute, then there are <em>n</em> relations in the possible worlds w.r.t. to this tuple. Analogously, if presence of a tuple <em>t</em> in a relation <em>R</em> is not sure, then <em>R</em> has two possible worlds, one which includes <em>t</em> and the other which doesn't. Probabilistic databases are uncertain databases with probabilities defined over the corresponding possible worlds. The main approach in related literature has been extending the concepts and techniques from traditional databases. A major difficulty is ensuring the ""correctness"" of query results, as different correlation assumptions among tuples require different run-time control and tracking algorithms. This turns query processing into <em>reasoning </em>which is more complex, if not infeasible. The expected outcomes include (1) novel query processing and rewriting techniques for extended relational algebra operations with desired semantics, (2) development of extended algebra techniques into an <em>integrated calculator</em> , and (3) development of prototype subsystems for uncertain data management and integration. All the practical work in this research will be evaluated experimentally. The research is anticipated to provide a more comprehensive understanding of uncertain data and the needs. I believe</span><span style=""line-height: 1.5em;""> that uncertain data research will influence, if not lead to, the </span><span style=""line-height: 1.5em;"">development of next generation DBMSs.</span><span style=""line-height: 1.5em;""> This research will make a leap in this direction.</span></p>