Provenance Challenge

Quick overview on Problem Solving Methods

Problem Solving Methods (PSM) define ways in which a high-level task can be achieved by decomposing it into its constituent (sub)tasks. In general, PSM describe in a domain-independent way the reasoning steps and the types of knowledge necessary to perform a task.

Additionally, they are not designed for one specific application problem and can be used for a family of similar problems in terms of the goals to be achieved or the knowledge required. Thus, PSM have been traditionally used as a means to enable reuse of reasoning strategies. PSM provide generalizations of domain knowledge in the form of roles which can be mapped against domain-specific knowledge. PSM also contain information about the input required to achieve a task, as well as the output produced by such task.

PSM are used in a number of ways in knowledge engineering: as a guideline to acquire problem solving knowledge, as a description of the main rationale of reasoning processes, as a skeletal description of the design model of a knowledge-based system, and to enable flexible reasoning by selecting methods during problem solving. A problem solving method consists of:

• Name: a symbol to refer to the method.
• Goal: logical expression specifying the requirements that the method output can meet.
• Set of subtasks and primitive inferences which together achieve the method goal.
• Input task(s) that receive(s) the input(s) of the method.
• Output task(s) that yield(s) the method output.
• Data flow between subtasks in terms of the roles that the data play in the process.
• Input role(s) specifying the role(s) of the concepts received by the method.
• Output role(s) specifying the role(s) of the concepts produced by the method.
• Control regime over the subtasks.
• Suitability criteria, defining the conditions when a method is applicable to a particular task.

For the approach to provenance interpretation presented in the Challenge by the OntoGrid team, the goal of a problem solving method, its subtasks, input and output roles, data flow, and suitability criteria are especially relevant. This approach exploits the relationship between domain and PSM entities to match the data recorded in provenance logs, i.e. contents of Southampton-compliant interaction p-assertions, against PSM roles. The hierarchical structure of PSM allows refining such matching in more detail as PSM decompose tasks into sub-tasks.

Some bibliography on PSM

-- JoseManuel - 25 May 2007

• ontologies-and-PSM.pdf: Knowledge-System Technology: Ontologies and Problem-Solving Methods

• fensel98role.pdf: The Role of Assumptions in Knowledge Engineering

• fensel99upml.pdf: UPML: A framework for knowledge system reuse

• PSM-reuse.pdf: An Ontology-based broker: Making Problem-Solving Method Reuse Work