Graph databases enable the storage and querying of data while emphasizing not only the data itself but also the relationships between data items. As graph-based applications become increasingly common, the need for robust and expressive query languages has grown. The Graph Query Language (GQL),  a new international standard for graph query languages, has been under development since 2019.

Standardization raises deep foundational questions regarding the expressivity, complexity, and practical implementability of core language features. Theoretical insights into these aspects can significantly influence the evolving design of GQL and shape the capabilities of future graph database systems.

SQL is the de facto standard query language for relational databases, where data is modeled in tables. Its formal semantics relies on Kleene’s three-valued logic (3VL) to cope with incomplete information—specifically, the presence of NULLs. While this approach offers a principled foundation, it often results in unintuitive query results, violations of logical laws, and inconsistencies that surprise users and complicate optimization.

This raises fundamental questions such as: Can we avoid or refine the use of three-valued logic in practice? Is it possible to design alternative semantics that remain compatible with current SQL engines? What can graph query languages learn from the challenges SQL faces with incomplete data?

Handling incomplete information is a longstanding challenge in data management. Classical approaches typically focus on simple relational queries—those expressed in the SELECT-FROM-WHERE fragment—where foundational notions such as certain answers are well understood. However, real-world queries are far more expressive, often involving aggregations, comparisons, arithmetic operations, and negation.

This shift raises fundamental questions:
How can we extend the theoretical framework to accommodate such expressive queries?
What does it mean to "answer a query" in the presence of nulls, unknowns, or partially specified data?