Canada Spends Logo

Explorez notre analyse du budget 2026

Grant: Discovery Grants Program - Individual

York University

$24,000.00

Planning and Factorization for Graph Database Query Optimization and Evaluation

EF 2023-24

Résumé
As long as people have looked at the stars, cultures have imaged lines connecting them. Some groups of so connected stars so stood out, people ascribed meaning to these constellations, relating them to things within their world. This is not so surprising. This way of modelling the world comes rather naturally. We map out how things in our world are related, the "conceptual lines" between them. We mentally walk these conceptual graphs we have constructed to answer questions about our world, and to generalize, to extract knowledge from our map. This is a useful model to use to capture information for computers, too, what we call a database. The things, entities, are whatever we are wanting to store information about. And we can put edges between entities (things) that are related, labelled with how they are related. So our database is a large graph. Then with the right language to ask questions, queries, we can extract useful information from the graph when needed. That is the computer walking the graph to find the queried information. Imagine we build a graph database for contact tracing. People are the entities. And we put a labelled edge into the graph between two people whenever the two come into close physical contact. Note two people entities might have lots of edges between them, one for each time they came in close proximity. Each edge can be labelled with the time that they did. Such a graph database could be used for contact tracing: whenever someone became ill, we could query the graph to discover with whom they had been in contact over a range of time. Graph databases are quite useful for collecting data in a natural way. And we are beginning to see organizations build extremely large graph databases. For example, the Uniprot SPARQL Endpoint (dataset) consists of 63,376,853,475 edges as of a recent time. Uniprot (UNIversal PROTein resource) is a freely accessible, popular repository of protein data used by biologists. But such graph databases are only as useful as, well, however we can use them to get useful information back out. Because of the immense size graph databases can be, queries over them can be hard to answer, to evaluate efficiently. A query is not useful if you have to wait years for the answer! Graph databases are a fairly new technology. So we are at the start of learning how to use and work with them efficiently. This includes how to evaluate queries over them efficiently. Other types of databases have been around much longer; we have much deeper experience how to work with them. In this work, we adapt methods of query optimization for more efficient query evaluation for graph databases. Conjunctive queries (a useful class) for graph databases are small graphs themselves. We model the answers to a query as a graph too, an answer graph. This is a _factorization_ technique that looks to be quite promising for graph data. And so towards making graph databases truly useful.
Programme
Discovery Grants Program - Individual
Bénéficiaire
Emplacement
Ontario, Canada
Type de bénéficiaire
Academia
Type
Grant
Source
NSERC's Awards Data

Tel que publié

Application id
RGPIN-2022-04548
Name nom
Godfrey, Parke
Department département
Computer Science and Engineering - Computer Science and Engineering
Organization id
38
Institution établissement
York University
Province en
Ontario
Province fr
Ontario
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2023
Competition year année de concours
2022
Award amount
24000
Program id
RGPIN
Program name en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
DISCOVERY RESEARCH
Group fr
RECHERCHE AXÉE SUR LA DÉCOUVERTE
Committee code
1507
Committee name en
Computer Science
Committee name fr
Sciences informatiques
Area of application code
1207
Area of application group en
Advancement of knowledge
Area of application group fr
Avancement des connaissances
Area of application en
Information, computer and communication technologies
Area of application fr
Technologie de l'information, des ordinateurs et des réseaux de communications
Research subject code
2803
Research subject group en
Artificial intelligence
Research subject group fr
Knowledge representation
Research subject en
Intelligence artificielle
Research subject fr
Répresentation des connaissances
Application title
Planning and Factorization for Graph Database Query Optimization and Evaluation
Keyword
algorithmic complexity; algorithms and data structures; data analytics; database systems; data science; graph databases; knowledge graphs; property graphs; query evaluation; query optimization
Application summary
As long as people have looked at the stars, cultures have imaged lines connecting them. Some groups of so connected stars so stood out, people ascribed meaning to these constellations, relating them to things within their world. This is not so surprising. This way of modelling the world comes rather naturally. We map out how things in our world are related, the "conceptual lines" between them. We mentally walk these conceptual graphs we have constructed to answer questions about our world, and to generalize, to extract knowledge from our map. This is a useful model to use to capture information for computers, too, what we call a database. The things, entities, are whatever we are wanting to store information about. And we can put edges between entities (things) that are related, labelled with how they are related. So our database is a large graph. Then with the right language to ask questions, queries, we can extract useful information from the graph when needed. That is the computer walking the graph to find the queried information. Imagine we build a graph database for contact tracing. People are the entities. And we put a labelled edge into the graph between two people whenever the two come into close physical contact. Note two people entities might have lots of edges between them, one for each time they came in close proximity. Each edge can be labelled with the time that they did. Such a graph database could be used for contact tracing: whenever someone became ill, we could query the graph to discover with whom they had been in contact over a range of time. Graph databases are quite useful for collecting data in a natural way. And we are beginning to see organizations build extremely large graph databases. For example, the Uniprot SPARQL Endpoint (dataset) consists of 63,376,853,475 edges as of a recent time. Uniprot (UNIversal PROTein resource) is a freely accessible, popular repository of protein data used by biologists. But such graph databases are only as useful as, well, however we can use them to get useful information back out. Because of the immense size graph databases can be, queries over them can be hard to answer, to evaluate efficiently. A query is not useful if you have to wait years for the answer! Graph databases are a fairly new technology. So we are at the start of learning how to use and work with them efficiently. This includes how to evaluate queries over them efficiently. Other types of databases have been around much longer; we have much deeper experience how to work with them. In this work, we adapt methods of query optimization for more efficient query evaluation for graph databases. Conjunctive queries (a useful class) for graph databases are small graphs themselves. We model the answers to a query as a graph too, an answer graph. This is a _factorization_ technique that looks to be quite promising for graph data. And so towards making graph databases truly useful.