## Summaries

### First-order Logic
- Language `$ \mathcal{L}=(\Gamma,\Omega,\Pi, X) $`
	- Constant symbols, Function symbols, Predicate symbols, variable symbols
	- Is only syntax
- Building blocks of languages: Terms
	- Interpreting terms leads to an entity in an universe of discourse
- Formulas are the combination of predicates and terms
	- Can be quantified and connected
- Interpretation `$ I=(U,I_C,I_F,I_P) $`
	- Universe of discourse
	- Constant symbol mapping
	- Function symbol mapping
	- Predicate symbol mapping
- Interpretation is required to evaluate and interpret the individual components of a language
- Variable assignment `$ \rho $`

---

### Models
- Set of formulae `$ W $`
- *Model*:
	- Interpretation `$ I $` such that all formulae in `$ W $` evaluate to true w.r.t. `$ I $`
	- If `$ W $` has a model, it is called *satisfiable*
	- If `$ W $` has no model, it is called *unsatisfiable*/*inconsistent*
- *Semantically equivalent*:
	- If two formulae always evaluate to the same truth value for any interpretation `$ I $`, they are called semantically equivalent
- *Tautology*:
	- If every interpretation is a model of `$ W $`, the formulae in `$ W $` are called *tautologies*
	- Also called *valid*
	- Notation: `$ \models W $`
	- Tautologies can be used as *transformation rules*
- *Semantic conclusion*:
	- A formula `$ F $` is a *semantic conclusion* of `$ W $` if and only if every model of `$ W $` is also a model of `$ W $`
	- `$ W\models F $`
	- Test `$ W\models F $`: Show that `$ W\cup\{F\} $` is unsatisfiable
	- Testing unsatisfiability is hard due to the unlimited number of possible interpretations
- Idea: Herbrand Interpretations
	- Only for closed formulae
	- Interpret each constant as itself
	- Purely *symbolic interpretation* (worst case scenario)
- *Clause*:
	- Disjunction of positive/negative literals
	- *Horn clauses* contain at most one positive literal
	- Lemma:
		- Given a set of clauses `$ W $`
		- `$ W $` has model if and only if `$ W $` has a Herbrand Model
		- `$ W $` is unsatisfiable if and only if `$ W $` has no Herbrand model

---

### Complexity
- SAT in Boolean logic: Decidable
	- For any set of Boolean formulae there is an algorithm testing for satisfiability
	- NP-complete
	- Algorithm: Davis-Putnam algorithm
	- Restricting SAT to Horn clauses is *P-complete*
- SAT in first-order logic: Undecidable
	- No algorithm can check satisfiability for any first-order logic formula in finite time
	- Semi-decidable algorithms:
		- Algorithm finds out if a formula is unsatisfiable
	- Restrict FOL to decidable subset:
		- Schönfinkel-Barnays class
		- NEXP-complete

---

### Datalog
- Implementation of a logical programming language
- Restricted to *Horn clauses*
	- Fact horn clauses: Extensional DB 
	- Definite horn clauses: Rule
	- Goal horn clauses: Query
- Datalog classification:
	- Datalog
	- Datalog-neg
	- Datalog-f
	- Datalog-f-neg
- Problem: Programs with cyclic negations
	- Program must be rejected (program will not end)
	- Detection: Stratification
- Semantics:
	- Least, minimal, perfect Herbrand model
	- Herbrand interpretation
		- Herbrand interpretation satisfying the Datalog program is a model
		- Problem: it is not easy to compute a model
		- Multiple models exist: Which is the *intended semantics*?
- Datalog-f:
	- Computationally complete
	- Intended semantic: Least Herbrand Model
	- Least Herbrand model is the intersection of all Herbrand models
	- It does not contain superfluous statements
	- *Operational semantics*:
		- Computation of the LHM, use fixpoint iteration
		- Start with empty set of ground atoms
		- Iteratively, refine the set
		- Monotonous process (only expanded)
		- Method is finite for Datalog-f
		- Result: Least Herbrand Model
	- Iteration step: Elementary production rule
		- Apply given rules with premises contained in the set of the previous step
- Datalog-neg:
	- Provide natural modeling
	- Datalog-neg is potentially *unsafe* (infinite large models)
	- Datalog-neg is potentially *ambiguous* (multiple distinctive models possible)
	- Multiple minimal models
	- Address ambiguity:
		- Assume negation as failure
		- Non-provided fact is false
		- ==Is this the same as the Closed World Assumption?==
	- Address Safety:
		- *Positive grounding*
		- Each variable appearing in a negative clause must appear in a positive clause
		- This restricts the evaluation to known facts
	- Deterministic choice of models:
		- Perfect model w.r.t. to preference relation
		- Perfect model is the intended semantics
	- *Operative semantics*:
		- Iterated fixpoint iteration
		- Apply fixpoint iteration on every stratum
- Fixpoint iteration and iterative fixpoint iteration are very inefficient
- Datalog to RelAlg:
	- Merge Datalog-style reasoning with techniques of relational databases
	- Elementary production rule can be implemented in relational algebra
	- Bottom-up approach:
	- Top-down approach:
		- Start with query, construct a proof tree down to the facts
		- Construct search trees by their depth
		- *Search tree*: Parameterized proof tree
		- *Backwards-chaining*
		- Stopping? Maximal chain
- *Magic Sets*:
	- Logical rewriting
	- Query is part of program
	- Determine the reachable adorned system
		- Observe which terms are distinguished and propagate the resulting adornments
		- Contains adorned predicate occurrences
	- Determine the magic set
		- using magic rules and magic predicates
		- Restricted/modified rules use only the constants from their respective magic set

---

### RDF
- Markup language to encode knowledge
- Knowledge in triples
- URI represents entity or concept
- RDF document represents graphs of labeled nodes and edges
- RDF has not restriction of the used labels
- RDF-S defines valid resources
	- Define vocabulary for RDF graphs
	- Define classes and properties
	- Contains pre-defined relationships (e.g., sub-classes, sub-properties, ranges, domains)