Logic on MARS: Ontologies for Generalised Property Graphs
Authors: Maximilian Marx, Markus Krötzsch, Veronika Thost
IJCAI 2017 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We give a formalisation of a generalised notion of Property Graphs, called multiattributed relational structures (MARS), and introduce a matching knowledge representation formalism, multi-attributed predicate logic (MAPL). We analyse the expressive power of MAPL and suggest a simpler, rule-based fragment of MAPL that can be used for ontological reasoning on Property Graphs. Our proof is based on an interesting reduction from the word problem of polynomially space-bounded Alternating Turing Machines, where we use attribute value sets to represent ATM configurations. Our estimation for the upper bound also reveals that the hardness for data complexity is related to the size of annotations, which occurs in the exponent in 2k2. |
| Researcher Affiliation | Academia | Maximilian Marx, Markus Krötzsch, and Veronika Thost TU Dresden Center for Advancing Electronics Dresden (cfaed) {maximilian.marx,markus.kroetzsch,veronika.thost}@tu-dresden |
| Pseudocode | Yes | Definition 11. The MARS chase procedure takes a MARPL ontology P, F and constructs a finite interpretation I as follows. The domain of I is the finite set of constants c C in P, F ; and such constants are interpreted as c I B c. We initialise p I B for every predicate p, and repeat the following steps until no more changes occur: (A) Let ϕ p(t1, . . ., tn)@Ψ P be a rule and let σ be a ground substitution such that I |= ϕσ but I |= p(t1, . . ., tn)@Ψσ. (B) If Ψ is a set term or a set variable, set T B Sσ. Note that Ψ is ground, because Ψ is either a variable-free set term or appears in ϕ. Otherwise, if Ψ = F(τ1, . . ., τℓ), set T B F(τ1σ, . . ., τℓσ). (C) Set p I B p I { (t1σ)I, . . ., (tnσ)I,T I }. |
| Open Source Code | No | No explicit statement about providing open-source code for the methodology or a link to a code repository is found. The paper only links to an extended technical report. |
| Open Datasets | No | The paper focuses on theoretical contributions and does not describe experiments on datasets. |
| Dataset Splits | No | The paper focuses on theoretical contributions and does not describe experiments on datasets, thus no dataset split information is provided. |
| Hardware Specification | No | The paper focuses on theoretical contributions and does not describe experiments that would require specific hardware specifications. |
| Software Dependencies | No | The paper focuses on theoretical contributions and does not describe experiments that would require specific software dependencies with version numbers. |
| Experiment Setup | No | The paper focuses on theoretical contributions and does not describe experiments or their setup. |