1 Introduction↩︎

Knowledge graphs (KGs) have become central to many AI applications [1], benefiting many AI-based tasks, including NLP and reasoning [2], data integration [3], [4], and semantic search [5]. KGs organize information as graphs, with nodes as entity instances and edges as relationship instances [6], [7]. Systems like property graphs [8] and RDF [9] are built on this principle, and even relational databases can be viewed as KGs [10]: they too store information about objects and their relationships, although the information may be structured in a more arbitrary manner.

To use KGs effectively, it is essential to describe their structure and semantics. Database schemas define expected data structures, e.g., specifying that a Book is written by an Author and has a unique ISBN. Conceptual modeling languages—such as ER [11], [12], ORM2 [13], [14], and UML [15], [16]—provide intuitive, high-level interpretations of these structures. The line between schemas and conceptual models is often blurred, as conceptual modeling languages frequently serve to define schemas with domain-relevant, intuitive names for object classes (entities) and relationships.

However, supported schema features vary across systems [17] and can even be tied to the underlying data model. Consequently, one cannot assume that database schema is sufficiently expressive to fully capture the structure and the semantics of the underlying knowledge graph.

To address this deficiency we propose KG-ER (Section 2), a conceptual schema language that serves both as a schema capturing the structure of knowledge graphs and a modeling language to convey their semantics. KG-ER has been designed with the aim to provide modeling features particularly suited for knowledge graphs, and in particular, it supports:

• Entity types, with support for fine-grained inheritance (disjointness and totality) and expressive key constraints based on tree-patterns (acyclic conjunctive queries).

• Relationship types, of arbitrary arity, with support for multi-edge relationships, key constraints (known as determinants in TigerGraph [18]), and participation constraints.

• Attributes, for entities and relationships, with support for multi-valued attributes, as well as mandatory and single-valued attributes.

We intentionally omit less commonly embraced concepts, such as cardinality constraints or inheritance between relationships; previous research [19]–[21] has revealed that these features are indeed rarely used in practice. We also pragmatically limit the scope of certain concepts, such as general disjointness of entities, whose interpretation in the context of knowledge graphs leads to a complex and nuanced debate, as presented in Section 5.

If we compare KG-ER to major existing knowledge graph data models, we can observe the following. Compared to ER and EER data models it has extra features such multi-edge semantics for relationships, a more powerful notion of keys, more restricted participation constraints and it does not allow relationship hierarchies. Compared to PG-Schema it has simpler key constraints, lacks cardinality constraints and union types, although the latter can be simulated. Compared to SHACL and ShEx (which are in some ways similar and in some ways different from SHACL [22]) it lacks features such as complex constraints based on regular path queries and constraints that involve nested quantifiers and boolean operators, but it does add composite keys. We argue that KG-ER because of its choice of features is eminently suitable for discussing and designing knowledge graphs stored in different logical data models such as RDF, Property Graphs and relational databases.

As evidence of the usefulness and expressiveness of KG-ER, we note that the schema of the LDBC-SNB benchmark [23] can be captured using KG-ER. Naturally, KG-ER can be extended with support for additional features, if needed.

We also provide, in Sections 3 and 4 a rigorous formal semantics for KG-ER, which can be used to map KG-ER to existing schemas for knowledge graph representations, such as property graphs schemas [24], schemas for RDF such as ShEx and SHACL [25], [26], and relational schemas in various normal forms. Because KG-ER is a conceptual schema language, it is conceivable to use it for constructing mappings and transformations between knowledge graphs stored using different representations e.g., an RDF with a SHACL to a Property Graph with a PG-Schema.

There are many benefits of using KG-ER in the context of AI practice and research alike. For AI practitioners, the KG-ER, which consists of a set of simple statements, can be easily fed into a specific AI model. In the full version of the paper [27] we we illustrate precisely this benefit by verbalizing KG-ER in helping LLMs in solving a number of common database tasks (text-to-query, query optimization, and schema normalization). For AI theoreticians, the precise logical formalization of KG-ER provides a yardstick of the expressive power for a given AI model to possess, should it need to operate on the structural and semantic information about the knowledge graph.

2 KG-ER Schemas↩︎

Throughout this paper we assume pairwise disjoint sets of names of entities \(\mathcal{Ent}\), relationships \(\mathcal{Rel}\), attributes \(\mathcal{Attr}\), and roles \(\mathcal{Rol}\).

A KG-ER schema (or simply schema) is a set \(S\) of simple statements that we divide into two parts: the shape graph and the constraints. For every kind of statement we provide an intuitive natural language verbalization, and we provide precise formal semantics in Sections 3 and 4. We consider only well-formed schemas which satisfy certain structural conditions, stated alongside the introduced statements (using the \(\mathbf{WF}\) indicator).

2.1 Shape Graphs↩︎

A shape graph of a schema consists of simple structural elements that describe the basic topology of knowledge graphs.

The shape graph part of a schema \(S\) is a collection of statements of one of the following forms (with \(E\in\mathcal{Ent}\), \(R\in\mathcal{Rel}\), \(X\in\mathcal{Ent}\cup\mathcal{Rel}\), \(A\in\mathcal{Attr}\), and \(B\in\mathcal{Rol}\)):

\(\mathbf{WF}_{1}\): All attribute and role declarations of a shape graph only use entities and relationships declared in the shape graph. Formally, for every \(\mathrm{\small Attribute}(X, A)\) in the shape graph, it also contains \(\mathrm{\small Entity}(X)\) or \(\mathrm{\small Relationship}(X)\), and for every \(\mathrm{\small Role}(R, B, E)\) in the shape graph, it also contains \(\mathrm{\small Relationship}(R)\) and \(\mathrm{\small Entity}(E)\).

For simplicity, we assume global uniqueness of attribute and role names in the schema i.e., no attribute name appears more than once (with different entities or relationships) and similarly no role name appears more than once (with different relationships or connected entities). Note that attribute names and role names are also assume not to overlap. The shape graph in Example 1 satisfies this assumption but it would violate it if it also contained \(\mathrm{\small Attribute}(\textit{University}, \textit{email})\).

2.1.0.1 Relational vocabulary

The shape graph of a schema \(S\) defines the finite vocabulary \(\mathcal{L}_S\) that consists of the set of entity names \(\mathcal{Ent}_S\), relationship names \(\mathcal{Rel}_S\), attribute names \(\mathcal{Attr}_S\), and role names \(\mathcal{Rol}_S\) used in \(S\). For simplicity of notation, we assume a fixed shape graph, and in the remaining, we consistently use \(E_i\), with \(1 \leq i \leq n\), to range over \(\mathcal{Ent}_S\), \(R\) to range over \(\mathcal{Rel}_S\), \(X\) to range over \(\mathcal{Ent}_S\cup\mathcal{Rel}_S\), \(A\) to range over \(\mathcal{Attr}_S\), and \(B\) to range over \(\mathcal{Rol}_S\).

2.2 Graphical Representation and Pattens↩︎

2.2.0.1 Graphical Representation

A shape graph is represented diagrammatically by using different node shapes and labels for both nodes and edges. We use rectangular nodes for entities, oval nodes for attributes, and hexagonal nodes for relationships. The node label is the name of the respective element. Additionally, role names are used as labels for the edges that connect relationships to entities.

2.2.0.2 Patterns

We use tree patterns, a simple yet powerful querying metaphor, to specify the key information that constitutes the identifying information of entity and relationship instances. Formally, a pattern over a schema \(S\) is a term \(p\) over the set of attribute names \(\mathcal{Attr}_S\) and role names \(\mathcal{Rol}_S\), with the attribute names appearing only in the leaf nodes. The arity of a pattern is the number of its leaf nodes.

We use patterns to query knowledge graphs whose structure conforms to the shape graph, and so we only use valid patterns that navigate through the shape graph following the existing edges labeled with the given role names and may terminate at existing attributes. Patterns have a natural meaning, which is best illustrated graphically as shown on the example below.

Example 3. We illustrate patterns with graphical examples in Figure [fig:patterns], which contains a fragment of the shape graph from Example 2.

The simple pattern \(p_1=\textit{name}\) consists of a single attribute and allows to retrieve the name of a university. A similarly simple pattern \(p_2=\textit{email}\) allows to access email address of a person.

The pattern \(p_3=\textit{msg}(\textit{author})\) allows to retrieve the person that has authored a given message; this pattern retrieves the instances of the instances of \(\textit{Person}\) entity. We are often interested in patterns that retrieve only concrete (attribute) values. As an alternative to the pattern \(p_3\), we can use the pattern \(p_4=\textit{msg}(\textit{author}(\textit{fname}, \textit{lname}))\) that retrieves the first and last name of the author of a message.

\(\square\)

Note that patterns do not need to have attribute names in all leaf nodes, but those that do are called ground patterns. Ground patterns are particularly important because they allow to retrieve concrete data values (attribute values) and avoid using identifiers of entities and relationships that are dependent on the particular representation of a knowledge graph.

2.2.0.3 Syntactically valid patterns

We only work with valid patterns that can be "embedded" in the graphical representation of the shape graph as illustrated in Figure [fig:patterns]. For completeness in our presentation, we formally define valid patterns as patterns rooted at an entity or relationship as follows. A pattern \(p\) is rooted at \(X\) in \(S\) iff (1) \(p\) is an attribute name \(A\) and \(X\) has attribute \(A\); (2) \(p\) is a role name \(R\), and either (2.a) \(X\) is a relationship with role \(R\), or symmetrically (2.b) \(X\) is an entity that participates in a relationship in the role \(B\); (3) \(p = B(p_1, \ldots, p_k)\), with \(k \geq 1\), and either (3.a) \(X\) is a relationship with an entity \(E\) participating in the role \(B\), and each \(p_i\) is rooted at \(E\), or symmetrically (3.b) \(X\) is an entity that participates in a relationship \(R\) in the role \(B\), and each \(p_i\) is rooted at \(R\).

2.3 Constraints↩︎

The constraints part of a schema \(S\) are a collection of statements that we divide into a number of categories. Again, with every statement we provide a natural language verbalization and define the formal semantics later on.

2.3.1 Participation Constraints↩︎

Participation constraints specify the minimum (0 or 1) and maximum number (1 or unbounded) of relationships instances that an entity instance participates in. They are a simple subclass of cardinality constraints, which are not used frequently in practice, and for which there is no general tool support. An analogous subclass of cardinality constraints allows to specify the minimum and maximum number of attribute values of an entity or relationship \(X\) and by abusing the naming convention we put them in the same category.

\(\mathbf{WF}_{2}\): Every participation constraint is declared for an entity or a relationship instance that is declared in the shape graph. Formally, for every \(\mathrm{\small Mandatory}(X, A)\) and every \(\mathrm{\small Single}(X, A)\) the shape graph contains \(\mathrm{\small Attribute}(X, A)\), and for every \(\mathrm{\small Mandatory}(E, B, R)\) and every \(\mathrm{\small Single}(E, B, R)\) the shape graph contains \(\mathrm{\small Role}(R, B, E)\).

2.3.2 Key Constraints↩︎

We introduce two kinds of key constraints, allowing to identify instances of entity or relationship \(X\). Simple key requires the uniqueness of the identifying information specified with a collection of patterns \(p_1, \ldots, p_k\). A stronger notion of identity key requires additionally that the identifying information is always present and unique (and so constitutes canonical identifying information). In both cases below the patterns \(p_1, \ldots, p_k\) are rooted at \(X\) in the shape graph.

• \(\mathrm{\small Key}(X, [p_1, \ldots, p_k])\): no two instances of \(X\) may have the same key values obtained with \(p_1, \ldots, p_k\);

• \(\mathrm{\small Identity}(X, [p_1, \ldots, p_k])\) every instance of \(X\) must have precisely one tuple of key values obtained with \(p_1, \ldots, p_k\), and no two instances of \(X\) may have the same key values.

We introduce identifying keys for very specific purpose: they are used to identify instances of entities and relationships in a manner independent of the representation of a knowledge graph.

\(\mathbf{WF}_{3}\): Identity keys use ground patterns only.

A standard assumption in graph theory is that graphs are simple, that is, they allow at most one edge connecting the same pair of nodes; this assumption is transferred quite unconsciously to knowledge graphs. However, there exist frameworks, such as property graphs and the recent RDF 1.2 [9], that allow multiple edges between the same pair of nodes. For the sake of generality, we do not restrict knowledge graphs to have at most one edge between the same pair of nodes. For instance, in the running example of the schema (Figure 1) the same person can study at the same university multiple times (although, at different years). Interestingly, keys allow us to impose the restriction of singular edges if it is required for a particular application.

\(\mathbf{WF}_{4}\): Every relationship has an identifying key.

Note that one can use a trivial identifying key consisting of all its attributes and roles.

2.3.3 Type Hierarchy↩︎

It is a common and useful mechanism to organize entities into a hierarchy. For instance, in the LDBC-SNB schema, the Message entity has two subclasses, Post and Comment. These two subclasses are disjoint: a Post cannot be a Comment and vice versa. Furthermore, in this instance, the subclass relation is total: every Message is either a Post or a Comment. To support these features we introduce the following statements.

\(\mathbf{WF}_{5}\): The type hierarchy formed with the \(\mathrm{\small Isa}\) statements is acyclic.

We clarify that multiple inheritance is not disallowed and moreover, the type hierarchy may consist of disconnected components. To make sure that we can distinguish between entities in the same component we introduce the following requirement.

\(\mathbf{WF}_{6}\): The entity at any root of the type hierarchy has an identifying key.

Two entities from the same component of the type hierarchy can be made disjoint.

Finally, to express total inheritance we introduce a statement that allows to specify coverage of an entity \(E\) by its descendants \(E_1, \ldots, E_k\) in the type hierarchy.

3 Data Model↩︎

Recall that the shape graph of a schema \(S\) identifies the finite vocabulary \(\mathcal{L}_S\) of entity names \(\mathcal{Ent}_S\), relationship names \(\mathcal{Rel}_S\), attribute names \(\mathcal{Attr}_S\), and role names \(\mathcal{Rol}_S\) used in \(S\). Also recall that, for simplicity, we work under a unique name assumption: no attribute name and no role name are used with more than a single entity or relationship.

We define knowledge graphs as relational structures over the union of two disjoint sets of elements: the entity and relationship instances \(\mathcal{V}=\mathcal{V}_\mathrm{ent}\cup\mathcal{V}_\mathrm{rel}\) and the data values \(\mathcal{D}\). Namely, a knowledge graph (or simply a graph) \(G\) over \(\mathcal{L}_S\) is a function \(\cdot^G\) that gives each element of \(\mathcal{L}_S\) an interpretation: \[\begin{align} &\text{E^G \subseteq_\mathrm{fin}\mathcal{V}_\mathrm{ent} for every E\in\mathcal{Ent}_S,}& &\text{A^G \subseteq_\mathrm{fin}(\mathcal{V}_\mathrm{ent}\cup \mathcal{V}_\mathrm{rel})\times\mathcal{D} for every A\in\mathcal{Attr}_S,}\\ &\text{R^G \subseteq_\mathrm{fin}\mathcal{V}_\mathrm{rel} for every R\in\mathcal{Rel}_S,}& &\text{B^G \subseteq_\mathrm{fin}\mathcal{V}_\mathrm{rel}\times\mathcal{V}_\mathrm{ent} for every B\in\mathcal{Rol}_S.} \end{align}\] Moreover, we define the sets \(N_\mathrm{ent}= \bigcup\{E^G \mid E\in\mathcal{Ent}_S\}\) and \(N_\mathrm{rel}= \bigcup \{R^G \mid R\in\mathcal{Rel}_S\}\), and we require that:

1. we do not assign attributes or roles to entity or relationship instances that do not belong to any entity or any relationship respectively i.e., \(A^G \subseteq(N_\mathrm{ent}\cup N_\mathrm{rel}) \times \mathcal{D}\) for every \(A\in\mathcal{Attr}_S\) and \(B^G \subseteq N_\mathrm{rel}\times N_\mathrm{ent}\) for every \(B\in\mathcal{Rol}_S\),

2. role names are partial functions, i.e., if \(B^G(r, e)\) and \(B^G(r, e')\) then \(e = e'\) for every \(B\in\mathcal{Rol}_S\) and \(r\in R^G\),

3. every relationship instance belongs to exactly one relationship in \(\mathcal{Rel}_S\), i.e., \(R_1^G \cap R_2^G = \emptyset\) for every \(R_1 \neq R_2\in\mathcal{Rel}_S\).

By \(\mathcal{G}(S)\) we denote the set of all knowledge graphs over \(\mathcal{L}_S\).

4 Semantics↩︎

Given a schema \(S\) and a knowledge graph \(G\) over \(\mathcal{L}_S\), we define when \(G\) satisfies \(S\) by translating every statement in \(S\) into a first-order logic formula. For keys, it is important to translate patterns into formulas that extract the identifying information.

4.1 Semantics of Patterns↩︎

The translation is relatively natural but to handle correctly the direction of the role predicates we need to know if the pattern is evaluated (rooted) at an entity or a relationship. We illustrate this translation on a simple example below.

Formally, we translate a pattern \(p\) of arity \(k\) rooted at \(X\) to a formula \(\varphi_p^X(x, y_1, \ldots, y_k)\) with the following recursive procedure: (1) For an attribute leaf \(p = A\) the formula is \(\varphi_p^X(x, y) = A(x, y)\); (2) For a role leaf \(p = B\) we have either (2.a) \(X\) is an entity and the formula is \(\varphi_p^X(x, y) = B(y, x)\) or, (2.b) \(X\) is a relationship and the formula is \(\varphi_p^X(x, y) = B(x, y)\); (3) For a non-leaf pattern \(p = B(p_1, \ldots, p_m)\) with \(B\in\mathcal{Rol}_S\), we have either (3.a) \(X\) is an entity that participates in a relationship \(R\) in the role \(B\) and then the formula is \(\varphi_p^X(x, \bar{y}_1, \ldots, \bar{y}_m) = \exists z.\;B(z, x) \land \varphi_{p_1}^R(z, \bar{y}_1) \land \ldots \land \varphi_{p_m}^R(z, \bar{y}_m)\) or, (3.b) \(X\) is a relationship that participates in the role \(B\) with an entity \(E\) and then the formula is \(\varphi_p^X(x, \bar{y}_1, \ldots, \bar{y}_k) = \exists z.\;B(x, z) \land \varphi_{p_1}^E(z, \bar{y}_1) \land \ldots \land \varphi_{p_m}^E(z, \bar{y}_m)\).

4.2 Core Semantics of KG-ER↩︎

We map each statement \(\mathit{s}\) of a schema \(S\) into a FOL formula \([\![\mathit{s}]\!]\) that captures its meaning, as presented in Figure 3.

Now, the core semantics of schema \(S\) are the knowledge graphs that satisfy all its statements: \[L_\circ(S) = \{G \in \mathcal{G}(S) \mid G \models \textstyle\bigwedge_{\mathrm{s} \in S} [\![\mathrm{s}]\!]\}.\]

It can be shown that schema reasoning in KG-ER, namely deciding entailment among graphs, is decidable in EXPTIME, by encoding entailment KG-ER to the FunDL Feature-Based Description Logics–by reifying the relationships using features as suggested in [28]; this means that there can be concrete algorithms to reason with KG-ER graphs.

5 Disjointness and Identity↩︎

There are three important, but related, issues when designing a conceptual data model: (Q1) How identifiable should entities be? (Q2) Do we have implicit disjointness of entities without common supertypes? and (Q3) For which entities is it possible to indicate disjointness? In the data models that are used to represent knowledge graphs, these questions are answered quite differently. For example, in relational schemas and ER diagrams there is usually a very strong notion of identifiability, e.g., by requiring that all entities must have a primary key. However, in RDF and LPG schema languages there is usually no such requirement. Concerning implicit disjointness, this is usually assumed in relational schemas and ER diagrams. However, in schema languages for property graphs and RDF there is usually no such assumption. For disjointness constraints, these are in extended ER schema languages usually only allowed between entities that share a common supertype, whereas in RDF schema languages there is usually no such restriction.

For Q1 we define identifiability as the ability to identify entities in terms of an entity description that consists of the entity and a combination of associated data values. We can distinguish three different levels of identifiability, each increasingly more demanding, but coming with practical benefits: (1) referenceability, which means that for all entity instances within a certain entity there is at least one entity description that identifies only that entity instance, (2) local distinguishability, which means that within each entity, each entity instance has exactly one such entity description, and (3) global distinguishability, which means that the DBMS is able to tell for two entity descriptions if they refer to the same entity or not.

In general global distinguishability is clearly preferred: it makes the instance of a schema less ambiguous and makes it easier to map it faithfully and straightforwardly to a database model such as for example a relational schema while avoiding surrogate keys or artificial identifiers. This is achieved for example in ORM2 by requiring that (R1) all entities have or inherit a well-founded identifier and (R2) entities that do not have a common supertype are assumed to be disjoint. Note that (R1) only ensures local distinguishability, but in combination with (R2) it also ensures global distinguishability. After all, given two entity descriptions it will hold that their entities have a common supertype, or not. In the first case, the DBMS can use local distinguishability in that common supertype to decide if the descriptions refer to the same entity, and in the second case it knows that they cannot refer to the same entity.

For KG-ER we have decided to require R1, but not necessarily R2, since R2 may not be possible or desirable to enforce for some domains. The core semantics \(L_\circ\) satisfies R1 but not R2. However, when R2 is also required, we propose an alternative semantics \(L_\bot\) with implicit disjointness. Namely, by \(\theta_S\) we denote the conjunction of \([\![\mathrm{\small Disjoint}(E_1, E_2)]\!]\) for any two entities \(E_1, E_2 \in \mathcal{Ent}_S\) that are not directly related in the type hierarchy, i.e., do not have a common Isa-ancestor. We can now formally define the semantics with implicit disjointness as \[L_\bot(S) = \{G \in L(S) \mid G \models \theta_S\}.\]

Finally, the issue of question Q3 is answered in KG-ER by only allowing explicit disjointness constraints between entities that have a common supertype. Under the \(L_\bot\) semantics this makes sense, since disjointness constraints between entities that do not have a common supertype would be redundant. However, even under the \(L_\circ\) semantics it makes sense to disallow such constraints, since they might be hard to map to efficient database schemas.

6 Conclusions and Future Work↩︎

We have presented KG-ER, an expressive modeling language with the purpose of providing a unified schema language for knowledge graphs stored in a large variety of database systems. We have built this language through diligent selection of the most useful and frequently-used features while being considerate of particular features of existing database systems used for representing knowledge graphs.

A formalized modeling language allows to ask and treat with the necessary rigor many interesting questions, some that fall into the large AI domain. Firstly, we would like to know how faithfully can we translate a KG-ER instance to existing database models (relational, property graphs, RDF) and their schemas, and conversely, can a schema of an existing database, say relational, be faithfully mapped to KG-ER? How can AI techniques, and LLMs in particular, offer assistance in those tasks? This leads to another interesting question: can KG-ER be effectively used to help to define mappings between different database models?

Acknowledgements↩︎

This research was supported by the European Research Council under grant no. ERC-IRIS-2025-0001. The authors declare no competing interests. Piotr Wieczorek was supported by the National Science Centre (NCN), Poland under grant 2020/39/B/ST6/00521

7 Appendix: verbalizing KG-ER helps LLMs↩︎

We present a number of experiments to illustrate that using a conceptual schema can help LLMs to tailor their answers for a number of natural and commonly used tasks. We performed the experiments using the OpenAI’s GPT-4o model on July 4th and 5th, 2025. The prompts and answers are provided below. We point out that in our experiments multiple runs sometime returned different answers, which is expected due to the stochastic nature of LLMs. However, in all executions the observations were consistent: providing a conceptual schema improves the quality of the answers.

7.1 Text to query↩︎

We begin with a task where the LLM is provided a relational schema together with a query specification in natural language, and we ask for a corresponding SQL query.

Then, in another session, we provide a similar task where the LLM is provided with a conceptual schema in addition to the relational schema and query specification.

The query provided by the LLM is correct. It specifically observes that a LEFT JOIN is used to ensure that departments without employees are included in the result. We next issued (in another chat) the same task with an additional conceptual schema which in particular specifies that every department must contain at least one employee. We observe that the LLM is able to leverage the conceptual schema and returns a simpler query which uses an internal join rather than the left outer join:

7.2 Query optimization↩︎

In this experiment, we investigate whether LLMs can use the information in conceptual schemas to optimize queries.

We provide the LLM with a relational schema together with an SQL query, and we ask the LLM to optimize the query. The presented query joins two copies of Author to check conditions on their birth date and country of origin. However, as \(book_id\) is the primary key for the relationship Authorship, it is possible to infer that each book can have at most one author. Therefore, the query can be considerably simplified by removing unnecessary joins.

The optimized version of the query is correct, but the LLM does not infer that both conditions in the query can be checked for the single author of each book and keeps unnecessary joins. Repeated experiments generated many alternative query versions, yet none incorporated this cardinality constraint.

See additional examples of queries generated by GPT-4o below:

Next, in a new chat, we provide the LLM, in addition to the schema and query, with the verbalization of the conceptual schema containing explicit cardinality constraints.

7.3 Schema normalization↩︎

In this subsection, we would like to check whether LLMs can use the information in conceptual schemas to normalize a relational schema originally provided in a denormalized form (a single “universal” table joining all relationships from a star-shaped schema). We first present the LLM with the original schema only, without the conceptual schema.

We removed irrelevant summaries and explanations from the answer returned by the LLM. The relational schema provided by the LLM is correct if we expect manager to be the unique manager of a department, but would not fit some other cases. The unicity and referential integrity constraints on the input (denormalized) relational schema cannot clarify the relationship between and its manager. We next issued (in another chat) the same task with an additional conceptual schema which in particular specifies that we aim to model a relationship between an employee and its possibly multiple managers.

Again, we removed irrelevant summaries and explanations from the answer returned by the LLM. The LLM is able to leverage the conceptual schema and returns a normalized schema that allows an employee to have multiple managers. We observe that the LLM chose to add a department attribute to the management relationship, an information that we had not explicitly represented in our conceptual schema.

8 Appendix: translations from KG-ER to other schema formalisms↩︎

In this section, we show how we can express the KG-ER conceptual schema of our running example (inspired by LDBC-SNB) into other schema formalisms.

8.1 Our running example↩︎

We first recap and complete our running example. We start from the shape graph from Figure 1 (recalled below), then add the constraints in the paper (except the type hierarchy that we omit from this discussion for simplicity), and finally add or strengthen a few constraints to obtain a well-formed schema:

The constraints in our example are the following:

8.1.0.1 Participation:

We simply collect the participation constraints from our running example, and for simplicity require that every attribute but Person(email) is single-valued:

• \(\mathrm{\small Mandatory}(\textit{Message}, \textit{date})\)

• \(\mathrm{\small Single}(\textit{Message}, \textit{date})\) and, more generally \(\mathrm{\small Single}(\textit{X}, \textit{A})\) for every \(X,A\) except the pair \((X=\textit{Person}, A=\textit{email})\) since we want to allow persons to have multiple emails but want the other attributes to be single-valued.

In addition we have:

• \(\mathrm{\small Mandatory}(\textit{Message}, \textit{msg},\textit{wrote})\)

• \(\mathrm{\small Single}(\textit{Message}, \textit{msg}, \textit{wrote})\).

8.1.0.2 Keys:

We not only collect the participation constraints from our running example, but also complete and strengthen keys in order to satisfy \(\mathbf{WF}_{4}\) and \(\mathbf{WF}_{6}\) (every relationship – resp. "root" entity – has an identifying key):

• \(\mathrm{\small Identity}(\textit{University}, [\textit{name}])\)

• \(\mathrm{\small Identity}(\textit{Person}, [\textit{fname}, \textit{lname}])\)

• \(\mathrm{\small Key}(\textit{Person}, [\textit{email}])\)

• \(\mathrm{\small Identity}(\textit{Message}, [ \textit{msg}(\textit{author}(\textit{fname},\textit{lname})),\, \textit{number} ])\)

• \(\mathrm{\small Identity}(\textit{studies}, [\textit{uni(name)},\, \textit{student(fname, lname)},\, \textit{year}])\)

• \(\mathrm{\small Identity}(\textit{follows}, [\textit{follower(fname, lname)},\, \textit{followee(fname, lname)}])\)

• \(\mathrm{\small Identity}(\textit{wrote}, [\textit{author(fname,lname)},\,\textit{msg(number)}])\)

When translating this KG-ER schema to other schema formalisms we will for simplicity consider that every attribute has a textual data type.

8.2 KG-ER to relational schemas↩︎

In this section we present a translation of our running example KG-ER schema into a relational schema, expressed using SQL.

The translation is similar in essence to the translation from an Entity-Relationship conceptual schema to an SQL relational schema. Every entity type is mapped to a distinct relation. In our example, this is the case for University, Person, Message. In general, every relationship type is also mapped to a distinct relation, but some relationships can be absorbed into the participating entities depending on the constraints: studies and follows are expressed using a relation, but wrote is absorbed into the Message relation. Single-valued attributes such as Person(fname) are inserted into the relation which represents their parent entity or relationship, whereas a distinct relation is created for each set-valued attribute such as Person(email), containing the attribute and the identifying key of its parent attribute. The constraint \(\mathrm{\small Key}(\textit{Person}, [\textit{email}])\) which prevents two persons from having any common email is expressed in our relational schema by the unicity constraint on Emails(email). On our example, all KG-ER constraints translate directly into simple SQL integrity constraints. But triggers could have been required to express more complex KG-ER constraints, for instance if the patterns involved had connected distant entities through a long path.

8.3 KG-ER to SHACL↩︎

We present here a mapping of the running example KG-ER schema into SCHACL core, so without using SPARQL. This maps entities to nodeshapes, relationships to nodeshapes (unless they are identifying relationships such as wrote, which are mapped to properties) and attributes to properties.

The resulting SCHACL schema fails to model fully the following constraints:

• \(\mathrm{\small Identity}(\textit{University}, [\textit{name}])\)

• \(\mathrm{\small Identity}(\textit{Person}, [\textit{fname}, \textit{lname}])\)

• \(\mathrm{\small Key}(\textit{Person}, [\textit{email}])\)

• \(\mathrm{\small Identity}(\textit{Message}, [ \textit{msg}(\textit{author}(\textit{fname},\textit{lname})),\, \textit{number} ])\)

• \(\mathrm{\small Identity}(\textit{studies}, [\textit{uni(name)},\, \textit{student(fname, lname)},\, \textit{year}])\)

• \(\mathrm{\small Identity}(\textit{follows}, [\textit{follower(fname, lname)},\, \textit{followee(fname, lname)}])\)

Our schema features two unique keys on a single attribute: \(\mathrm{\small Identity}(\textit{University}, [\textit{name}])\) and \(\mathrm{\small Key}(\textit{Person}, [\textit{email}])\). Such keys can in our case be expressed in SHACL using maxCount on the reversed edge, thanks to the global uniqueness of attribute names (Section 2.1). Without this global uniqueness assumption, the unique keys on a single attribute could still be expressed in core SHACL using qualifiedMaxCount on qualifiedValueShape over the reversed edge, thus checking for instance that each name has a single parent entity of class University (though it may then have other parent entities of other classes). On the other hand, it seems it may not be possible to express composite unique keys in SHACL core [29], so we did not translate the other key constraints such as \(\mathrm{\small Identity}(\textit{Person}, [\textit{fname}, \textit{lname}])\), though we could have expressed them using SPARQL.

@prefix sh: <http://www.w3.org/ns/shacl#> .
@prefix xsd: <http://www.w3.org/2001/XMLSchema#> .
@prefix ex: <http://example.org/> .

#################################################################
# University
#################################################################
ex:UniversityShape
    a sh:NodeShape ;
    sh:targetClass ex:University ;
    sh:property [
        sh:path ex:name ;
        sh:datatype xsd:string ;
        sh:minCount 1 ;
        sh:maxCount 1 ;
    ] .

#################################################################
# Unicity of Name globally (hence of University names)
#################################################################
ex:NameTargetShape
    a sh:NodeShape ;
    sh:targetObjectsOf ex:name ;  # all nodes that are the object of :name
    sh:property [
        sh:path [ sh:inversePath ex:name ] ;
        sh:maxCount 1 ;
    ] .

#################################################################
# Person
#################################################################
ex:PersonShape
    a sh:NodeShape ;
    sh:targetClass ex:Person ;
    sh:property [
        sh:path ex:fname ;
        sh:datatype xsd:string ;
        sh:minCount 1 ;
        sh:maxCount 1 ;
    ] ;
    sh:property [
        sh:path ex:lname ;
        sh:datatype xsd:string ;
        sh:minCount 1 ;
        sh:maxCount 1 ;
    ] ;
    sh:property [
        sh:path ex:email ;
        sh:datatype xsd:string ;
        sh:minCount 0 ;    # Optional
    ] ;
    sh:property [
        sh:path ex:studies ;
        sh:node ex:StudiesRelShape ;
        sh:minCount 0 ;
    ] ;
    sh:property [
        sh:path ex:follows ;
        sh:node ex:FollowsRelShape ;
        sh:minCount 0 ;
    ] ;
    sh:property [
        sh:path ex:wrote ;
        sh:node ex:MessageShape ;
        sh:minCount 0 ;
    ] .

#################################################################
# Unicity of emails globally (hence of Person's emails) 
#################################################################
ex:EmailTargetShape
    a sh:NodeShape ;
    sh:targetObjectsOf ex:email ;  # all nodes that are the object of :email
    sh:property [
        sh:path [ sh:inversePath ex:email ] ;
        sh:maxCount 1 ;
    ] .
    
#################################################################
# Message (Weak Entity)
#################################################################
ex:MessageShape
    a sh:NodeShape ;
    sh:targetClass ex:Message ;
    sh:property [
        sh:path ex:number ;
        sh:datatype xsd:string ;
        sh:minCount 1 ;
        sh:maxCount 1 ;
    ] ;
    sh:property [
        sh:path ex:date ;
        sh:datatype xsd:string ;
        sh:minCount 1 ;
        sh:maxCount 1 ;
    ] ;
    sh:property [
        sh:path ex:text ;
        sh:datatype xsd:string ;
        sh:minCount 1 ;
        sh:maxCount 1 ;
    ] ;
    sh:property [
        sh:path ex:writtenBy ;   
            # derived from identifying relationship "wrote"
        sh:class ex:Person ;
        sh:minCount 1 ;
        sh:maxCount 1 ;
    ] .

#################################################################
# studies relationship node (with attribute "year")
#################################################################
ex:StudiesRelShape
    a sh:NodeShape ;
    sh:property [
        sh:path ex:year ;
        sh:datatype xsd:string ;
        sh:minCount 1 ;
        sh:maxCount 1 ;
    ] ;
    sh:property [
        sh:path ex:university ;
        sh:class ex:University ;
        sh:minCount 1 ;
        sh:maxCount 1 ;
    ] .

#################################################################
# follows relationship node (with attribute "since")
#################################################################
ex:FollowsRelShape
    a sh:NodeShape ;
    sh:property [
        sh:path ex:since ;
        sh:datatype xsd:string ;
        sh:minCount 1 ;
        sh:maxCount 1 ;
    ] ;
    sh:property [
        sh:path ex:followee ;
        sh:class ex:Person ;
        sh:minCount 1 ;
        sh:maxCount 1 ;
    ] .

8.4 KG-ER to ShEx↩︎

We present here a mapping of the running example KG-ER schema into ShEx. The mapping is broadly speaking the same as the one for SHACL. So we again map entities to nodeshapes, relationships to nodeshapes (unless they are identifying relationships such as wrote, which are mapped to properties) and attributes to properties. The result again does not fully represent all constraints of the KG-ER schema, and fails to represent the same list of constraints. Also here it is as far as we are aware not straightforward to represent in general such constraints correctly in the current version of ShEx at the time of writing, although extensions are under development that will make this possible, and in particular to express the key constraints.

PREFIX ex: <http://example.org/>
PREFIX xsd: <http://www.w3.org/2001/XMLSchema#>

# -------------------
# Entity: University
# -------------------
ex:UniversityShape {
  ex:name xsd:string          # exactly 1 name
}

# -------------------
# Entity: Person
# -------------------
ex:PersonShape {
  ex:fname xsd:string ;       # exactly 1
  ex:lname xsd:string ;       # exactly 1
  ex:email xsd:string* ;      # 0..* emails
  ex:studies @ex:StudiesRelShape* ;   # 0..* studies relationships
  ex:follows @ex:FollowsRelShape* ;   # 0..* follows relationships
  ex:wrote @ex:MessageShape*      # 0..* messages written
}

# -------------------
# Entity: Message (weak entity)
# Identified relative to a Person through 'wrote'
# -------------------
ex:MessageShape {
  ex:number xsd:string ;      # partial key (relative to Person)
  ex:date   xsd:string ;
  ex:text   xsd:string
}

# -------------------
# Relationship: studies (Person <-> University, with attribute year)
# -------------------
ex:StudiesRelShape {
  ex:year xsd:string ;
  ex:university @ex:UniversityShape
}

# -------------------
# Relationship: follows (Person <-> Person, with attribute since)
# -------------------
ex:FollowsRelShape {
  ex:since xsd:string ;
  ex:followee @ex:PersonShape
}

# -------------------
# Relationship: wrote (Person <-> Message)
# -------------------
# In ShEx we just model this via the property ex:wrote in PersonShape.
# Each Message is connected back to its Person.

8.5 KG-ER to PG-Schema↩︎

In this section we present a translation of our running example KG-ER schema into a PG-Schema graph type as presented in [24]. The translation basically maps entities to node types and (binary) relationship to edge types. The exceptions are the node type emailType and the edge type with label hasEmail, which model the multi-valued attribute email of entity Person. The KG-ER schema constraints map straightforwardly to similarly named constraints. Note that in some cases, such as for \(\mathrm{\small Mandatory}(\textit{Message}, \textit{msg},\textit{wrote})\) and \(\mathrm{\small Single}(\textit{Message}, \textit{msg}, \textit{wrote})\), they are combined into a single PG-Schema constraint.

CREATE GRAPH TYPE socialStudentGraphType STRICT {
     // Node types
    (universityType: University {name STRING),
    (personType: Person {lname STRING, fname STRING}),
    (emailType: EMail {address STRING}),
    (messageType: Message {number STRING, date STRING, text STRING}),}

    // Edge types
    (:personType)-[:hasEMail]->(:emailType),    
    (:personType)-[:studies {year: STRING}]->(:universityType),
    (:personType)-[:follows {since: STRING}]->(:personType),
    (:personType)-[:wrote]->(:messageType),
    
    // Node identifiers
    FOR (u:universityType) 
      IDENTIFIER u.name,
    FOR (p:personType) 
      IDENTIFIER p.fname, p.lname,
    FOR (m:messageType) 
      IDENTIFIER p.fname, p.lname, m.number WITHIN (p) -[:wrote]-> (m),

    // Edge identifiers
    FOR ()-[s:studies]->() 
      IDENTIFIER u, p, s.year WITHIN (p)-[s:studies]->(u),
    FOR ()-[f:follows]->() 
      IDENTIFIER p1.fname, p1.lname, p2.fname, p2.lname 
      WITHIN (p1)-[f]->(p2),
    FOR ()-[w:wrote]->() 
      IDENTIFIER p.fname, p.lname, m.number WITHIN (p)-[w]->(m),

    // Key and participation constraints
    FOR (m:messageType) 
      MANDATORY SINGLETON w WITHIN ()-[w:wrote]->(m),        
    FOR (p:personType)
      EXCLUSIVE e WITHIN (p)-[:hasEMail]->(e),
  }

References↩︎