Dimensional Inconsistency Measures and Postulates in Spatio-Temporal Databases (Extended Abstract)

1 Spatio-Temporal Databases

The representation and processing of spatio-temporal data has attracted much attention by the AI community [Cohn and Hazarika, 2001; Gabelaia et al., 2005; Yaman et al., 2005; Knapp et al., 2006]. In this paper, we focus on SpatioTemporal (ST) Databases (DBs), representing atomic statements of the form "object id is/was/will be inside region r at time t". Spatio-Temporal databases can be viewed as a special case of Spatial Probabilistic Temporal Databases [Parker et al., 2009; Parisi et al., 2010; Grant et al., 2010; Grant et al., 2013b; Grant et al., 2013a; Parisi and Grant, 2016; Parisi and Grant, 2017; Grant et al., 2017; Grant et al., 2018].

Below we briefly introduce the syntax and semantics of ST databases. We assume the existence of three finite sets: ID is the set of object ids, T is the set of integer time values, and Space is the set of point locations. We assume that an object can be in only one location at a time, but a single location may contain more than one object. A region is a nonempty subset of Space.

∗This paper is an extended abstract of [Grant et al., 2021] published in the Journal of Artificial Intelligence Research.

Definition 1. An ST atom is a tuple (id, r, t), where id ∈ ID is an object id, r is a region, and t ∈ T is a time value. An ST database is a finite set of ST atoms.

Intuitively, the ST atom (id, r, t) says that the location of object id belongs to region r at time t. Hence, ST atoms can represent information about the past and the present, such as that generated by techniques for interpreting RFID readings [Fazzinga et al., 2014; Fazzinga et al., 2016], but also information about the future, such as that derived frommethods for predicting the destination of moving objects [Mittu and Ross, 2003; Hammel et al., 2003; Southey et al., 2007], or from querying predictive databases [Akdere et al., 2011; Agarwal et al., 2010; Parisi et al., 2013]. The meaning of an ST database is given by the interpretations that satisfy it.

Definition 2. An ST interpretation I is a function I : ID × T → Space.

An interpretation specifies a trajectory for each id ∈ ID by saying where in Space object id was/is/will be at each time t ∈ T. We now define satisfaction and ST models.

Definition 3. Let a = (id, r, t) be an ST atom and I an ST interpretation. We say that I satisfies a (denoted I |= a) iff I(id, t) ∈ r. I satisfies an ST database S (denoted I |= S) iff for all a ∈ S, I |= a. We say that I is a model for a (resp., S) iff I satisfies a (resp., S).

Finally, we define when an ST database is consistent.

Definition 4. An ST database S is consistent iff there exists at least one model for S.

The set of all minimal (under set-inclusion) inconsistent subsets of an ST database S is denoted as M(S).

2 Notion of InconsistencyMeasure for ST Databases and (Classical) Postulates

An inconsistency measure (IM) is a function that assigns a nonnegative real value or infinity to every ST database. We use R∞≥0 for the set of nonnegative real numbers and the infinity symbol, and use L for the set of all ST databases.

Definition 5. An inconsistency measure I : L → R∞≥0 is a function such that, for every S, S ′ ∈ L, the following two properties hold:

1. (Consistency) I(S) = 0 iff S is consistent.
2. (Monotony) if S ⊆ S ′ , then I(S) ≤ I(S ′ ).

These two properties ensure that all and only consistent ST databases get a measure of 0 and that the measure is monotonic w.r.t. set-inclusion.

We now define several properties that some inconsistency measures possess and that are intuitively desirable. Specifically, we present a list of eight additional properties that have counterparts for propositional knowledge bases. For an ST database S, the ST atoms that appear in some minimal inconsistent subset are called problematic ST atoms. The ST atoms that are not problematic are called free. Formally, we write Problematic(S) = ⋃M∈M(S) M and Free(S) = S \ Problematic(S).

Definition 6. Let I be an IM, and S, S ′ be two ST databases. We consider the following postulates:

1. (Free-Formula Independence) If (id, r, t) ∈ Free(S) then I(S) = I(S \ {(id, r, t)}).
2. (Penalty) If (id, r, t) ∈ Problematic(S) then I(S) > I(S \ {(id, r, t)}).
3. (Dominance) If (id, r, t) and (id, r′ , t) are ST atoms such that r ⊆ r′ then I(S ∪{(id, r, t)}) ≥ I(S ∪{(id, r′ , t)}).
4. (Super-Additivity) If S∩S ′ = ∅ then I(S∪S ′ ) ≥ I(S)+ I(S ′ ).
5. (Attenuation) If M,M ′ ∈ M(S) and |M| < |M ′ | then I(M ) > I(M ′ ).
6. (Equal Conflict) If M,M ′ ∈M(S) and |M| = |M ′ | then I(M ) = I(M ′ ).
7. (MI-Normalization) If M ∈M(S) then I(M)=1.
8. (MI-Separability) If M(S ∪ S ′ ) = M(S) ∪M(S ′ ) and M(S) ∩M(S ′ ) = ∅ then I(S ∪ S ′ ) = I(S) + I(S ′ ).

We will find that in most cases these postulates are not satisfied, suggesting that they are not appropriate for the new IMs, because such postulates do not take into account the time, space, and object dimensional information within ST atoms. This turns out to be too coarse-grained an approach for ST databases. To cope with this issue, we will define "dimensional" postulates (in Section 4), which are more suitable for ST databases and the new inconsistency measures.

3 InconsistencyMeasures for ST Databases

In this section, we propose several inconsistency measures that are relevant for ST databases, as they explicitly take into account the dimensions characterizing such data.

3.1 Dimensional InconsistencyMeasures

We use the fact that ST databases can be considered along three dimensions: objects, time, and space. This allows us to measure the inconsistency along one or a combination of dimensions. Separating the dimensions of ST databases requires looking inside the formulas. Consider what such a step means for propositional knowledge bases. The formulas there contain propositions and logical connectives (as well as parentheses). As IMs typically use only the problematic formulas, a natural way of measuring inconsistency is to count the number of distinct propositions in the problematic formulas. Let us call a proposition p problematic if p appears in a problematic formula. Then we can define IP (K) = |{p | p is a problematic proposition}| for a propositional knowledge base K. Actually, we did not find this definition in the literature on IMs. However, it is the absolute version of a relative IM studied in [Xiao and Ma, 2012]. So IP is our inspiration for measuring inconsistency along the three dimensions.

In some cases we may just be interested in how many objects or how many time values are involved in an inconsistency, which leads us to the two IMs defined below.

An IM based strictly on objects is:

Thus, IO counts how many objects are contained in some minimal inconsistent subset, that is, the number of objects involved in an inconsistency.

Similar to the IM along the object dimension, a natural IM along the time dimension counts how many time values are involved in an inconsistency:

It is natural to combine the object and time dimensions before dealing with the spatial dimension. This can be done by combining the two dimensions individually, that is, computing IO and IT and then applying some operation(s) to the two numbers. Instead of doing so, we observe that in many cases we are dealing with id, t pairs. Indeed, all the ST atoms of a minimal inconsistent set must have the same id and t values. The following IM is thus defined looking at id, t pairs in minimal inconsistent subsets:

Thus, IOT counts how many object-time pairs are involved in an inconsistency.

Let us now turn our attention to the space dimension. For an ST database S we define a region RS as follows:

Then, we define IS(S) = |RS|. Thus, IS counts the number of points that are in regions involved in an inconsistency.

For the next measure involving space, we require a metric d : Space × Space → [0,∞). First, we define distance for minimal inconsistent subsets. Let M be a minimal inconsistent subset of an ST database S: M = {(id, r1, t), . . . , (id, rn, t)}. We start by defining n new regions, one for each i, 1 ≤ i ≤ n, as Ri = ⋂j̸=i rj . Since M is a minimal inconsistent set, for each i, 1 ≤ i ≤ n, Ri ̸= ∅, but ∩ni=1 ri = ∅. We define the value d(M) as:

We can think of d(M) as the minimal distance in Space between any regions involved in a minimal inconsistent subset. Then, we define: ID(S) = ∑M∈M(S) d(M). Thus ID sums the minimal distances between regions involved in minimal inconsistent subsets.

3.2 Repair-based InconsistencyMeasures

In this section, we define three new inconsistency measures, namely Iid, Itime, and Iregion, which are based on the cost of restoring consistency along the object, time, and spatial dimensions. We also introduce measure Icard, which is not dimensional (it deals with whole ST atoms), but it is also based on the cost of restoring consistency in a minimal way as the other three measures introduced in this section.

In general, an update of an ST atom a is an ST atom a′ derived from a by changing (at most) one of its dimensions. Hence, we will deal with 3 types of updates.

Definition 7. Given an ST atom a = (id, r, t),

1. an id-update of a is an ST atom a′ = (id′ , r, t);
2. a time-update of a is an ST atom a′ = (id, r, t′ );
3. a region-update of a is an ST atom a′ = (id, r′ , t).

Thus, an id-update (resp., time-update, region-update) of a is either the result of changing the id value (resp., time value, region) of a or a itself. Corrections are ways of changing an inconsistent ST database to a consistent one using updates.

Definition 8. Let S be an ST database. A consistent ST database S ′ is called an X-correction of S, where X ∈ {id, time, region}, if there is a surjective function Xcorr : S → S ′ s.t. for every a ∈ S, Xcorr(a) is an X-update of a.

So an id-correction allows only id-updates, and the other types of corrections are defined analogously.

We assume a metric dID on the set ID of object identifiers for measuring the cost of updating id to id′ for an ST atom. Thus, the cost of fixing the object identifier id of an ST atom a by setting it to id′ is given by the distance dID(id, id′ ) between the two identifiers. In the following, we denote by costid(a, a′ ) the cost of changing atom a into an id-update a′ . Thus, costid(a, a′ ) = dID(id, id′ ). Moreover, given an ST database S and an id-correction S ′ , let Cid be the set of all functions idcorr as per Definition 8. We define costid(S, S ′ ) = minidcorr∈Cid {∑a∈S costid(a, idcorr(a))}.

Definition 9. An id-repair for an ST database S is an idcorrection S ′ of S such that for all id-corrections S ′′ of S, costid(S, S ′ ) ≤ costid(S, S ′′ ).

We are now ready to define the measure Iid. It is the cost of an id-repair, if one exists. It is possible that there is no idcorrection at all, as all possible sets of id-updates result in an inconsistent database. Recall that ID is fixed.

Definition 10. Given an ST database S, Iid (S) = ∞ if there is no id-repair; otherwise Iid(S) = costid(S, S ′ ) where S ′ is an id-repair for S.

The next repairing strategy we use is based on minimally updating the time values associated with the ST atoms. We need a metric dT on the set of time values in T measuring the cost of updating t to t′ . For this purpose we can use for instance dT (t, t′ ) = |t′ - t|. Then, we denote by costtime(a, a′ ) the cost of changing atom a to a timeupdate a′ , where t in a was changed to t′ in a′ , and define costtime(a, a′ ) = dT (t, t′ ). Finally, given an ST database S and a time-correction S ′ , let Ct be the set of all functions timecorr as per Definition 8. We define costtime(S, S ′ ) = mintimecorr∈Ct {∑a∈S costtime(a, timecorr(a))}.

The notions of time-repair and the measure Itime are analogous to id-repair and Iid but for the time dimension.

Definition 11. A time-repair for an ST database S is a timecorrection S ′ of S such that for all time-corrections S ′′ of S, costtime(S, S ′ ) ≤ costtime(S, S ′′ ).

Definition 12. Given an ST database S, Itime(S) = ∞ if there is no time-repair, otherwise Itime(S) = costtime(S, S ′ ) where S ′ is a time-repair for S.

The next repairing strategy we use is based on minimally updating regions in ST atoms. Similar to the previously introduced notions of repairs, we use a metric dR(r, r′ ) on the set of regions. For instance, since a region is a set of point locations, we might measure the cost of updating a region r into a region r′ as the cardinality of their symmetric difference, that is, we might define dR(r, r′ ) = |(r \ r′ ) ∪ (r′ \ r)|. We denote by costregion(a, a′ ) the cost of changing atom a to a region-update a′ , where r in a was changed to r′ in a′ , and define costregion(a, a′ ) = dR(r, r′ ). Given an ST database S and a region-correction S ′ , let Cr be the set of all functions regcorr as per Definition 8. We define costregion(S, S ′ ) = minregcorr∈Cr {∑a∈S costregion(a, regcorr(a))}. The notions of region-repair and Iregion are as follows.

Definition 13. A region-repair for an ST database S is a region-correction S ′ of S such that for all region-corrections S ′′ of S, costregion(S, S ′ ) ≤ costregion(S, S ′′ ).

Definition 14. Given an ST database S, Iregion(S) = costregion(S, S ′ ) where S ′ is a region-repair for S.

The last repairing strategy we consider relies on assuming that some ST atoms were wrongly generated and thus need to be removed to restore consistency. We require that the number of removed atoms be minimal.

Definition 15. A card-repair for an ST database S is a consistent subset S ′ of S such that |S ′ | = max{|S ′′ | such that S ′′ is a consistent subset of S }. The cost of card-repair S ′ for S is costcard(S, S ′ ) = |S| - |S ′ |.

Definition 16. Given an ST database S, Icard(S) = costcard(S, S ′ ) where S ′ is a card-repair for S.

4 Dimensional Postulates

In this section, we propose dimensional versions for some of the postulates-we will find in the next section that in several cases the dimensional postulate holds even though the original postulate does not hold.

Definition 17 (Dimensional Penalty). Let I be an IM and S be an ST database.

1. (Object Penalty) If (id, r, t) ∈ Problematic(S) and A = {(id, r′ , t′ ) ∈ Problematic(S)} then I(S) > I(S \ A).
2. (Time Penalty) If (id, r, t) ∈ Problematic(S) and A = {(id′ , r′ , t) ∈ Problematic(S)} then I(S) > I(S \ A).
3. (Space Penalty) If (id, r, t) ∈ Problematic(S) and A = {(id′ , r′ , t′ ) ∈ Problematic(S) | r∩r′ ̸= ∅} then I(S) > I(S \ A).

In the following, for an ST database S, we use the following notations: ID(S) = {id | (id, r, t) ∈ S}, Time(S) = {t | (id, r, t) ∈ S}, and Region(S) = ⋃{r | (id, r, t) ∈ S}. Definition 18 (Dimensional Super-Additivity). Let I be an IM, and S, S ′ be two ST databases. For X ∈ {ID, Time, Region}, if X(S)∩X(S ′ ) = ∅ then I(S ∪S ′ ) ≥

I(S) + I(S ′ ).

Definition 19 (Dimensional MI-Separability). Let I be an IM, and S, S ′ be two ST databases. For X ∈ {ID, Time, Region}, if X(S)∩X(S ′ ) = ∅ andM(S∪S ′ ) = M(S) ∪M(S ′ ), then I(S ∪ S ′ ) = I(S) + I(S ′ ).

5 Postulate Satisfaction and Complexity

We analyze which postulates, both classical (cf. Definition 6) and dimensional (cf. Section 4) ones, are satisfied by the proposed IMs, considering dimensional as well as repair-based IMs (cf. Section 3). We also analyze the time complexity of our IMs. Results are summarized in Table 1. Each row in Table 1 but the last one refers to a postulate and shows which IMs satisfy it. The first 8 postulates are classical ones, while the last 3 are dimensional. The first 5 IMs (i.e., columns) are dimensional ones, while the remaining 4 are repair-based.

Classical Postulate Satisfaction. We first consider dimensional IMs. We note that IO, IT, and IOT satisfy the same set of (classical) postulates. The two IMs based on the space dimension behave quite differently: IS satisfies only Free-Formula Independence; ID satisfies postulates (Penalty, Super-Additivity, and MI-Separability) that are not satisfied by any other dimensional IMs, but it does not satisfy postulates (Equal Conflict and MI-Normalization) that are satisfied by other dimensional IMs.

Let us consider now repair-based IMs. We first note that Iid and Itime behave in the same way, satisfying Dominance and Super-Additivity, while Iregion satisfies only Super-Additivity. In contrast, the classical postulates fit quite well with Icard, which satisfies all of them except Penalty, Attenuation, and MI-Separability. This should not be surprising, since the classical postulates are designed for nondimensional IMs like Icard. However, we will see below that the measures based on the dimensions satisfy the dimensional versions of some classical postulates they do not satisfy.

Dimensional Postulate Satisfaction. Notice that we do not include IOT as it deals with two dimensions and we restricted the dimensional postulates to a single dimension. Also, we do not include Icard , as it does not deal with dimensions.

We first consider dimensional IMs. All dimensional IMs satisfy all dimensional postulates. Considering the dimensional postulates in place of the classical counterpart, IO and IT satisfy all postulates but Attenuation, thus the highest possible number, since Attenuation is incompatible with MI-Normalization (cf. [Grant et al., 2021]). The number of postulates satisfied by considering dimensional and classical postulates has doubled for all the measures except for ID.

We now consider repair-based IMs. Iid and Itime satisfy the dimensional postulates except Dimensional MISeparability, with Dimensional Penalty being satisfied when the IM returns a finite value. Then, Iregion satisfies all dimensional postulates unconditionally. Also, if the metric used for measuring region distance is the symmetric difference, Icard coincides with Iregion (cf. [Grant et al., 2021]), and considering dimensional and classical postulates, Iregion satisfies all the postulates except Attenuation, that is, the maximum number of postulates that can be jointly satisfied.

Overall, our analysis shows that the dimensional postulates suit very well the dimensional inconsistency measures.

Complexity Analysis. Following [Thimm and Wallner, 2016; Thimm, 2018], we characterize the complexity of the following decision problem for an IM I: given an ST database S and rational number k, decide whether I(S) ≤ k.

The complexity of such problem for our IMs is reported in (the last row of) Table 1; more specifically: it is in P for IO, IT, IOT, and Icard; it is in P for IS and ID under the restriction of isothetic rectangular regions, by which we mean rectangles oriented in the standard way, that is, with horizontal and vertical sides; it is in P for Iregion when the symmetric difference is employed as the metric to measure distance between regions; finally, it is NP-complete for Iid and Itime.