In: B. Veenendaal and A. Kealy (Eds.): Research@Locate'15, Brisbane, Australia, 10-12 March 2015, published at http://ceur-ws.org
People use natural language (NL) descriptions to communicate spatial information, mostly referring to space in qualitative terms. In this research, a graph database is used to store such qualitative spatial information as derived from NL descriptions. It focuses on developing and testing qualitative spatial reasoning mechanisms to maintain relational consistency within the graph database. The study provides a first step into using a graph database to storing and querying qualitative spatial data from NL place descriptions, and provides some insights for the system implementation.
People represent environment in natural language (NL) descriptions typically in a qualitative way of spatial features and their relationships, such as “Building A is to the left side of Building B” or “The campus is a little bit north from the city”. Such qualitative information could provide an intuitive approach for representing human spatial knowledge. Since this knowledge can be extracted in the form of triplets of locatum-relationship-relatum (as in “campus”-“north of”-“city”) a formal model of two nodes and a linking edge comes to mind. Graph databases, which have already proven useful for modelling qualitative relationships in other areas, present a way to store and query these triplets.
This research focuses on building such a graph database that can store triplets while maintaining relational
consistency. The research will go back to Qualitative Spatial Reasoning (QSR) for consistency checking. QSR has
been used in other contexts, such as robot navigation, e.g.
The hypothesis of this study is that a graph-based place database can preserve relational consistency in transactions about triplets representing locata, qualitative spatial relationships, and relata. It is anticipated that, as an outcome, a graph-based place database is able to identify and flag if new input is violating the current consistency and causing logical contradictions. For this purpose the paper studies the relationships and calculi in question, suggests reasoning constraints and algorithms for consistency checking, and tests these algorithms.
The rest of this paper is structured as follows: Section 2 discusses related work and tools. Section 3 explains the methodology for data modelling, as well as reasoning configurations to preserve relational consistency. Section 4 explains the experiments and provides a demonstration of the implemented system. The experiment results presented in Section 5 and discussed in Section 6. Section 7 includes conclusions and suggestions of future work. Copyright © by the paper’s authors. Copying permitted only for private and academic purposes.
The NoSQL database family (NoSQL means ‘not only SQL’) includes a variety of database management
systems that are not restricted to relational SQL models. It is not in contrast to but rather complements relational
databases
Graph databases have two advantages in modelling rich-connected data, compared to relational databases
(
Graph databases are today used in modelling information from social networks, such as Facebook, as well as general knowledge, for example the Google Knowledge Graph. In this study, a graph database is used to model place information since it provides a natural, suitable, efficient and flexible way for modelling spatial objects and the qualitative spatial relationships among them, with no need for pre-defining a tabular schema as in a relational database.
The concept of triplets has been widely utilized
QSR is a constraint-based process that enables spatial intelligence to reasoning about space
In this context, Frank suggested QSR with cardinal directions and qualitative distance relationships
(a) (b) (c)
For qualitative distance relationships Frank discussed two-step (close, far), three-step (close, middle, far) and
multi-step systems
Freksa provided an approach for reasoning with relative direction relationships
Egenhofer et al. discussed a methodology for modelling and reasoning with topological relations
The different calculi of QSR, each of them applicable on one type of spatial relationships, have been packed into
toolboxes. For example, SparQ
Triplets of place information, as extracted from NL description, can be integrated and stored in a graph database. The graph database should only store relationships that are consistent with each other in order to avoid contradictions in querying or reasoning, even if the information is not necessarily true according to geographic reality. In this section, methods will be provided to maintain relational consistency.
A triplet consisting of {locatum, relation, relatum}, such as {Building A, to the right of, Building B} is represented in a graph database using two distinct nodes for locatum and relatum, and a directed edge from the locatum to the relatum, as shown in Figure 3. In the following sections, L-r->R will be used to represent a triplet, such as “Building A–to the right of–>Building B”.
Each time a new triplet is to be added, the names of the locatum and relatum will be queried to verify whether already nodes of these names exist in the database. If the nodes already exist, the triplet is integrated in the existing graph, otherwise new nodes are created and connected with directed edges. The graph can become a multi-graph when more than one triplet are added with the same locatum and relatum (e.g., A–right of–>B; A–west of –>B).
Relational inconsistency occurs in a graph database when two pieces of information can be derived from the
stored data that are logically contradicting. For example, if a real world situation as shown in Figure 4 is described
by “A-west of->B” and then by “B-west of->A” there is a contradiction. Contradictions can also occur over longer
cycles, such as in “A-west of->B”, “B-west of->C” and then “C-west of-A”.
R3(A, C)
Distributive law: A = {A1. . A }, B = {B1. . B }, A ∘ B = ∑=1 ∑ =1
A ∘ B relationships, an n*n composition table consists of each composition result between any two relationships in n.
A table can be constructed to represent the composition results S3(A, C) . For a calculus of n possible
For the time being, any new triplet L-r->R, r must be from one of the three categories: cardinal direction, qualitative distance, or topological relationship. All other relationships are not yet covered; they might be stored without consistency checking, or conservatively just rejected.
In order to identify relational inconsistency, any new input triplet L-r->R will be compared to existing knowledge between L and R derived from the stored data. a set of relationships.
Definition: Given a triplet L-r->R, an existing path (EP) is a sequence of nodes and edges in the graph database that starts from L and ends with R, while all the relationships in the path belong to the category of r.
Definition: An existing knowledge (EK) is a set of derived relationships between L and R from an EP. If the length of EP equals to one, then EK is the single relation in the EP. If the length of EP is greater than one, then for all relationships with 1..n in EP in sequence order, EK = 1 ∘ 2 ∘. . , which could be either a single relationship or
A new triplet L-r->R is regarded consistent with a database if it is relationally consistent with all EKs between L and R. If the triplet is consistent, it will be added to the graph database; otherwise an inconsistency will be flagged.
For cardinal directions this research adopts the neutral zone system (Figure 1c), as it is assumed that all spatial features have a two-dimensional extend. As for any other system, each cardinal direction can be associated with a region such that these regions form a JEPD partition of the Euclidian plane. The size of the neutral zone is defined by the relatum R, while the locatum L in a triplet L-r->R belongs to one of the eight zones (NW, N, NE, E, SE, S, SW and W).
Table 2 shows Frank’s composition table for the neutral zone model. ‘Any’ in the table means again that any of the eight relationships is possible. However, the composition table is not directly applied in this work. This is because the semantics of cardinal directions in NL descriptions are more vague than a logical model suggests. For example, when people say North, they could mean anywhere within zones of W, NW, N, NE and E—in the neutral zone model—instead of only N, because if the half-planes of cardinal directions intersect in a valid relation, it seems that people consider them as conceptually consistent (i.e., non contradicting), as they can generalize from the more specific relations, to the more general and broader application region of each relation (half-planes). Therefore, without more detailed knowledge, a certain level of uncertainty should be accepted and not be regarded as inconsistency. For instance, in reasoning N and NW should be considered as consistent while N and S should be regarded as inconsistent.
N NE E SE S SW W NW
Definition: An extended cardinal direction set (ECD) is a set of consistent cardinal direction relationships given a cardinal direction relationship r in a NL description.
The ECD for any cardinal direction relationship is shown in Table 3. The table provides a set of relationships that are regarded as relationally consistent with r. For instance, “Building A-north of->Building B” and “Building A-east of->Building B” are considered as relationally consistent, and their half-plane intersection exists in the form of a valid relation north-east (NE); while “Building A-north of->Building B” and “Building A-south of->Building B” are relationally inconsistent, as obviously an intersection of their half-planes does not exist.
ECDs provide a ‘tolerant’ mechanism that first stores triplets which are considered to be relationally consistent. Then, when more triplets with new knowledge between the same two spatial objects are stored, and the number of EP (and EK) increases, the system becomes less tolerant, as a new input triplet will need to be consistent with every EK in order to be consistent with the graph database.
Rule 1: Given an input triplet L-r->R and r is a cardinal direction relationship, if for every EK between L and R, r belongs to the ECD of at least one of the elements in that EK, then the triplet is relationally consistent with the graph database.
Relative direction relationships require a reference frame for relative directions. The reference frame can be linked to the orientation of the observer (egocentric, to my left), the orientation of the relatum (allocentric, to the left of the front side), or be a projection of the speaker to the reference frame of the recipient (your left). Unfortunately triplets do not provide this spatial reference frame. For instance, when someone says “A is in front of C” then this sentence’s ambiguity with respect to the spatial reference frame cannot be resolved without further context (which is not accessible). This is the reason why in this research reasoning mechanisms for relative direction relationships are not provided.
Egenhofer’ s composition table for the 4-intersection model
The data used to test the algorithms are 731 triplets derived from 42 place descriptions collected by Vasardani et
al.
The Neo4j community version is used in this research as local host visualization platform. The Neo4j Python-embedded is the main module used to interact with the local database host. The system structure is shown in Figure 5.
triplets node already exist?
no create node yes checking procedure cardinal direction
relationship qualitative distance relationship topological relationship other
Rule 1 Rule 2 Rule 3 reject
no consistent?
yes create L-r->R
The experiment consists of two parts. In Part 1, during the import stage, the reasoning algorithms were applied to identify inconsistent triplets form the set of 731. Each flagged triplet is then manually verified of whether it really causes relational inconsistency or not. Thus, rate P1 calculated by Formula 4.2.1, is the precision of the algorithm. For instance, if the system detects 10 inconsistent triplets, and 9 of them are verified, then P1 equals to 0.9 (maximum 1).
1 = number of verified inconsistent triplets number of inconsistent triplets identified (4.2.1)
In Part 2, after all triplets are imported, an additional set of 60 made-up consistent and inconsistent triplets of the three categories of relationships were input to the database. In this case it was known in advance which of the triplets are consistent or inconsistent. Again it was tested whether the system is able to correctly accept or reject each of them accordingly. The rate P2 calculated by Formula 4.2.2 provides another insight on the precision of the algorithm.
When querying for EPs that start from node L and end with R, a maximum path length has been set, since computing all the paths between two nodes in a graph draws on computation time. This theoretical drawback can only be justified by pragmatics: First, it can be observed that after just a few steps of reasoning, composition tables in many places end with ‘any’ anyway. The second pragmatic argument is based on the First Law of Geography: Near things are more related than far things, which raises the expectation that relevant spatial information is provided in short cycles. The parameter for the maximum path length, Maximum Query Depth (MQD), has been tested in order to observe when the overall computation time becomes unacceptable. This test was done by adding all the 731 triplets into an empty graph database and recording the overall computation time of reasoning for each triplet, over a range of MQD.
For Part 1, all 731 triplets were added from the descriptions, and no inconsistent triplet occurred. All triplets were then verified, and P1=1. For Part 2, 60 triplets were tested. 60 out of 60 were processed correctly—both all consistent and all inconsistent cases were identified—by the graph database, thus P2=1.
Figure 6a shows the overall number of EP computed in Part 1 for every triplet from the set of 325 in the considered relation categories. Figures 6b, 6c, and 6d show the number of EP for triplets for each respective category (MQD = 3).
Number of EP computed for the 325 triplets in Experiment 1
Number of EP computed for 146 cardinal direction triples 1 11 21 51 61 71 81 1 Number of EP 20 (c)
Number of EP 20 Number of EP 6 ]15 10 5 0 ]4 2 0 (b) (d) 1 3 5 7 9 11 13 15 17 19
Triplets
Computation time for MQD that equals to 1, 2, 3 and 4 respectively is shown in Figure 8. When MQD is set to 1, 2 and 3, the computation time is rather stable (around 0.1s). But when it is set to 4, the computation time suddenly begins to soar as the size of the graph database grows.
Computation time when MQD = 1
Computation time when MQD = 2 Computation time (s) 5.00
Computation time (s) 5.00 (a) (c) Computation time when MQD = 3
] Computation time (s) 5.00 325 Triplets
Compu]tation time when MQD = 4 Computation time (s) 5.00 325 Triplets
325 Triplets
The implementation of relational consistency rules is the first step of automatically reason with qualitative spatial relationships from NL descriptions in a graph database. The implemented mechanisms are flexible and robust to preserve relational consistency in a graph database.
In Part 1 of the experiment, the 731 triplets extracted from the 42 place descriptions are relationally consistent. This result is not surprising, since the descriptions are from students that are already, to various extents, familiar with the environment of the University of Melbourne’s Parkville campus, therefore the possibility of giving misleading descriptions is low (but still possible, such as by mistake, and which makes the consistency checking mechanisms necessary). Alternatively, also malicious users could try to add inconsistent knowledge and should be prevented. However, the system does only flag an inconsistency; it has no mechanisms to decide whether the already stored or the added relations are the truer representation of geographic reality.
According to the result given by Part 2, the system is capable of distinguishing consistent and inconsistent triplets. Additionally, as shown in Figure 6, the numbers of EP found for qualitative distance relationships are overall small. This indicates that there are not as many neighbouring relationships that belong to the qualitative distance relationship category, therefore it is not as rich-connected as cardinal direction and topological relationships.
The system is flexible and accommodates certain degrees of ambiguity and uncertainty. The graph database is robust for maintaining relational consistency with given rules and formalized triplets, even though the reasoning algorithms are flexible.
Among the input spatial objects, ‘Campus’ is a special one. It is rather a container of most other spatial objects in these (campus) place descriptions. Among all 731 triplets, 144 of them (approximately 19.7%) related to ‘Campus’.
Although relative direction relationships were not reasoned, it was observed that some relative direction relationships appear ‘inconsistent’ in expression when considered without their individual spatial reference frame. For instance, in one triplet, the Engineering Department is “right of” the South Lawn, while in another triplet, the relationship between them is “left of”. Triplets of relative directions occupy approximately 25% of the total number of triplets; hence they must be addressed in future work by ways of capturing and maintaining their spatial reference frame.
Additionally, each relationship is only checked for consistency within its own category. Relational consistency checking among different categories is not considered in this research; therefore the system is not yet able to reason relationships from multiple categories. For example, “A-inside->B” and “A-far->B” are contradicting since A and B must be disjoint in order to be far from each other. Due to the fact that ‘inside’ and ‘far’ do not belong to the same category, they will not be regarded as relationally-inconsistent by the implemented database. Thus, reasoning rules among different categories of relationship should be developed in future research.
It was anticipated that by setting different MQD, the number of EP queried for any triplet L-r->R would be different. Also, it is expected that the reasoning results would be different since cycles longer than MQD can still be inconsistent with a triplet to be added. When implemented, no difference in reasoning result was detected by setting different MQD; however, the difference of number of EP detected is significant.
Although more EP could be queried by setting larger MQD (and consequently more EK can be used for consistency checking), it is suggested to set MQD to 3 in order to limit the computation time. As shown in Figure 8, it can be predicted that with a larger dataset, the computation time would soon become unacceptable with larger MQD.
This research proves that a graph database can preserve relational consistency when modelling qualitative place information derived from NL. The hypothesis is verified by the outcomes of the experiments described in earlier section. The implemented system is overall flexible enough to accommodate NL descriptions and robust for maintaining relational consistency.
Data triplets in this research include spatial relationships from categories such as cardinal directions, qualitative distances, topological relations, relative directions and other (non-categorized) relationships. Reasoning rules were developed for the first three categories. When a new input triplet violates a consistency rule, it will be flagged by the graph database to prevent logical contradiction and relational inconsistency. Currently, the system can only process reasoning based on relationships that belong to the same category. It is not yet able to reason on triplets with relationships from multiple categories.
The path length of reasoning cycles has to be limited for computational reasons. Different MQD were tested for composition reasoning, and an MQD of 3 still delivered acceptable computation times.
This research is the first step in attempting to build a relationally consistent database for place information from NL. Such a graph database, built and maintained in relational consistency, can then be used to solve relevant decision making tasks, such as landmark navigation; or be used for other applications, such as plausible sketch map drawing.
The major limitations of this research are the limited size and context of the test dataset (all campus descriptions of the same campus). More interesting observations are expected if the graph database is used for testing datasets referring to different locations. Second, the robustness of mapping NL descriptions of qualitative distance relationships into intervals needs further research. It is known that qualitative distance judgements change with the context in a conversation, do not follow the commutative law (from “A is near B” does not necessarily follow that, within the same context, “B is near A”), and negation within the three-step model is not addressed. For instance, “not far” could mean either ‘near’ or ‘middle’ in a description, however it is mapped to ‘middle’ in this research. Third, as discussed, the system is not yet able to reason over relationships from different categories, and also it is not able to reason with relative direction relationships.
Apart from the limitations discussed above, other work can also be done in future studies. First, semantic reasoning could be introduced to automatically identify synonyms of relationship labels, thus helping a graph database further to maintain relational consistency over a larger variety of relationship names. Secondly, due to the ambiguity of natural language descriptions, relationships cannot be categorized automatically currently. For instance, ‘in’ and ‘on’ in NL descriptions could stand for not only topological ‘inside’ (i.e. room in the building; clock-tower on the lawn), but also other relations (i.e. station on the road). Mechanisms could be developed by considering the type of the referenced objects as well as the context, in order to categorize relationships automatically.