Eric Corre

Université de Paris III LITRA 3413, AELA

Verbal particles and prefixes and situation aspect.

Prepositions and particles are notoriously polysemous and multifunctional across languages.

In many Indo-European languages, realized as pre-verbal prefixes or as detachable adpositions, they can have various lexical and /or grammatical functions, one of which is to mark so-called (a)telic aspect at the VP level, and that often goes together with valencychanging effects. The presence of prepositional phrases/particles/prefixes has long been held as one of the factors involved in what is called "aspect shift", i.e. change of membership from one aspectual class to another, along with the properties of the noun phrase (bare NPs or not)

and the presence of time (frame or durative) adverbials. At the sentential level, they may serve another purpose, which is to derive a perfective verb from an imperfective verb: it is the case in Russian. So it appears that particles / prefixes figure prominently among formal markers of aspect.

I propose to explore the interaction in this paper. In section 1, I present the data in order to give an idea of the cross-linguistic variation in the use of particles or prefixes across some familiar European languages, mainly English and Russian. In section 2, I review some of the most influential theories of semanctic (lexical) or situation aspect [START_REF] Smith | The Parameter of Aspect[END_REF]. Finally, in section 3, I select the two theories (Tenny's MOC and Levin and T. Rapoport's lexical subordination) that can best account for the general phenomena of verb type-shifting induced by particle verbs (pvs) and prefixes, among other elements.

1-The data

Let us begin with English, which has many constructions involving prepositional phrases and particles (intransitive prepositions).

1.1. English particle verb (pv) constructions.

1) He ran across (the square) 2) He took the garbage out.

3) He wiped the table down. 4) He wiped the table clean. 5) He ran up a lot of debts. 6) Billy bashed away at the piano. 7) He worked off his debts. 8) He sat out the storm. 9) He slept the afternoon away. 10) I'm all coffeed out.

In 1), across can be realized either as a preposition taking a NP complement or as a particle;

in 2), out is a directional particle: its meaning is transparent, the structure is highly productive and predictable; it is arguably from uses like these that other, non-spatial, uses of postpositions emerged. There is a close semantic and functional parallelism between structures 2) and 3), and 4), which is a so-called resultative structure: all three are cases of syntactic secondary predication, with the locational adverbial (out), the particle (down) and the adjective (clean) providing a secondary predicate to the main semantic predicate (took in 2, wiped in 3 and 4). In all three cases, the referent of the postverbal argument undergoes a change of state. The meaning of down in 3) is difficult to pin down; it is certainly not directional: the table does not end up "down" as a result of wiping. 5) is even more problematic: although the particle up appears to have the "maximalizing effect on the direct argument" that the literature typically (and rather vaguely) ascribes to it [START_REF] Mcintyre | Idiosyncrasy in Particle verbs[END_REF], its

Aktionsart contribution in 5) is next to nil: the debts do not end up being "up", neither do they get "run", for that matter. We seem to be dealing with a completely unpredictable "verbe + particle" combination. In 6), away, followed by the conative at-construction, is also an aspectual particle but unlike the particles from 1) to 5), it makes the whole verbal predicate atelic. Apart from the resultative construal that we already noticed, one further effect of the particle in 7) and 8) is its valency-changing effect on the main verb: the particle constructions make the intransitive verbs work and sit transitive. Finally, 9) and 10) are interesting cases of semi-productive formations (Jackendoff, McIntyre, 2002): one part of the schema is fixed (Verb time-away; be Verb-ed out), the other (the verb and the temporal phrase in 9, the verb in 10) is partially open, and again the sentence has a resultative, change-of-state flavor.

Russian offers the same variation but with two noticeable differences: 1) the prepositional element is realized as a non-detachable prefix; 2) the prefix is one of the means whereby a perfective verb is derived out of an imperfective verb stem. To a certain extent, prefixes in Hungarian fulfil the same function, but unlike their Russian counterparts, they are detachable.

Russian (and Hungarian) prefixes

Let us look at the data for Russian first.

11) On dobežal do doma i vbežal v kuxnju: He ran to the house and ran into the kitchen. 11) illustrates the prepositional nature of prefixes: in most cases the prefix is synchronically also a spatial preposition; v-in vbežal implies that he actually changed locations (namely, entered the kitchen running), and do-in dobežal that he reached the house running. In 12), that same prefix do-assumes an Aktionsart meaning: it signals an action that reached its completion; other such Aktionsart particles are za-(ingression), ot-(termination), etc. 13) and 14) recall the resultative structures of English above, with the difference that the secondary (resultative) predicate is realized as a non-detachable prefix vy-, which means that the action leads to "exhaustion, emptying". In 14), the intransitive verb rabotat' ("work"), together with the prefix ot ("off, from"), selects a result predicate as complement.

15) and 16) illustrate another type of combination making use of a prefix and the reflexive postfix -sja, "self": the compound is not the mere addition of the meaning of the terminative prefix do-and the reflexive postfix -sja, but it is a morpheme which obligatorily comes in two pieces (do-Verb-sja) for which the verb position is open provided it denotes somebody to be reached; it is semi-productive : doždat'sja,"wait till someone actually shows up", dokričat'sja, "shout till someone responds", dostučat'sja, "knock on a door till someone opens it", etc. But the pattern, which in theory could be unlimited, is not : there are many ways in which one can end up getting some response from someone by doing something peculiar in the way of getting their attention; for example, the verb *dosmotret'sja, which theoretically could exist ("end up getting a response from someone by looking at them intently"), does not. J. Fontaine notes somewhat paradoxically (1983,40) that this mode of composition is particularly productive for metaphorical formations. 16) is a further example of a two-morpheme verb; it is a formation which uses the two modes of verbal composition of Russian: prefixation (pod-) and suffixation (-va) applied on a simplex verbal stem (pet': sing); here again we have a split morpheme, the presence of one being conditioned by the presence of the other; taken separately, the formations *podpet' and ?pevat' either do not exist at all or are out of use (pevat' is now archaic). 17) and 18) show the valency-changing effect of certain prefixes: in 18) the prefix zawhich attaches to the simplex verb gruzit' ("load") contributes the meaning of a place / a surface totally covered with something (the holistic interpretation in the load-alternation, [START_REF] Anderson | La grammaire casuelle[END_REF][START_REF] Veyrenc | Pour une grammaire syntagmatique des préverbes[END_REF]) and triggers a change in the case of the argument NPs in its wake: from pogruzit' in 17) (po-being a "neutral" prefix1 ) + theme (accusative) + location (accusative directional), we get zagruzit' + location (accusative) + theme (instrumental).

But where Russian radically departs from English and other Germanic languages is that at one point in the history of the verb phrase it gave up the inflectional temporal paradigms it had inherited from common Slavic (aorist, perfect, imperfect) and developed the category of grammatical aspect by reanalyzing the already existing material (i.e., prefixal formations and suffixed verbs). In all the cases discussed above, the mere adjunction of the prefix renders the verb perfective. In 19), the verbs vypit' ('drink') and postavit' ('put in vertical position') are the perfective members for the simplex imperfective verbs pit' and stavit'; as the prefix seems to simply serve a grammatical function, the literature recognizes somewhat paradoxically that a purely derivational morpheme (vy-, na-…) fulfils an inflectional function. The choice of the prefix is not totally arbitrary, however; when it is not neutral (like po-), very often it is redundant or pleonastic in relation to the meaning of the verb: vy-is the prefix (one of the few, incidentally, which does not exist as a preposition) that indicates exhaustion, an emptying process; in 21a) na-is the preposition meaning "contact with a surface" ("on, onto"); pro-in 20a) implies a process of scanning, of "going over" something (exactly what one's eyes do when they are reading). One important point is this: in spite of what the morphology temptingly suggests (vy-pit' = "drink out of / up"; pro-citat' = "read through"), vypit' does not necessarily mean that the contents of the glass were completely drunk; it is perfectly natural to say something like On vypil čutok stakana: "He drank part of the glass", with no commitment as to the completion of the drinking process leading to exhaustion of the liquid. However, one systematic effect that perfective prefixed transitive verbs (and all perfective transitive verbs, for that matter, whether prefixed or un-prefixed) do have is that, as 20a) and 21a) illustrate, they cannot occur without a direct object.

One further striking aspectual effect that Russian prefixes do not have, but that Hungarian prefixes do show, is that, when some of them are detached from the verb, they give an imperfective progressive interpretation to the verb phrase; not only do they mark situation aspect (SA), they also express viewpoint aspect (VA, Smith 1991 The data has shown the deep correlations between situation/viewpoint aspect and the use of verbal prefixes/prepositional constructions/particles. In this paper I will explore the aspectual contribution of verbal prefixes/particles only at the level of SA, leaving the assessment of their contribution to VA for a later paper. But first, I need to clarify the notion of SA: I have been using the terms "(a)telicity", "perfectivity" indiscriminately. I will draw on existing theories of situation aspect, see how these apply in assessing particle/prefix constructions, and show how this affects the structural make-up of verbs.

Different versions of Situation Aspect

I insisted that the notion of SA should not be confused with that of VA. Although these two components utilize the same ingredients, they do not operate at the same level and make different contributions: SA operates at the VP level, basically transforming a spatial entity into a temporal one, whereas VA provides instruction concerning the interpretation of the whole sentence into the discourse world of the speaker/utterer. Some authors have suggested calling VA "presentational aspect", which avoids the vagueness and possible confusion inherent in the term "viewpoint"; "presentational" refers to the temporal function of grammatical aspect, which is basically to mediate the relationship between utterance time and the time of the event denoted by the verb.. However, I will continue using the term V(iewpoint) A(spect).

The origins of Situation Aspect

That prefixes / particles should be so enmeshed with aspect should not surprise us: aspect, whether situation (VP-level) or viewpoint (sentence-level), is the means whereby strictly spatial eventualities (write a letter is a "local" event) become temporal ones. Prepositions are very good candidates: their spatial origin predisposes them to do that. But what exactly does the term SA cover? I need to make an excursion into the vast literature on the subject, and clarify the notions of telicity, quantisation, culmination, etc, and then proceed to assess the relevance of prepositional/particle constructions to aspectual construals of sentences.

It did not all start with Vendler, of course, but I will take him as a starting point. Vendler insisted that the time element is crucial in classifying verbs, or rather VPs. He popularized a certain number of syntactic tests (be V-ing, the in and for adverbials) designed to make the temporal (later dubbed "aspectual") properties of VPs emerge. The first distinction concerns the so-called activity terms and the state terms: activities like run are made up of a certain number of dynamic sub-phases whereas states lack internal structure. The progressive helps tell the two classes apart. Then, among dynamic processes, a further distinction has to be made between those activities that are inscribed homogeneously in time and do not include a natural completion point (run), and those activities, dubbed accomplishments, that have both a phasal part and an endpoint beyond which the event will have reached completion (run two miles). Activities have the sub-interval property: at every moment of an event of John running, John can be said to be running; on the contrary, at a given moment of John running two miles one cannot assert that John ran two miles is true. In function of their theoretical frameworks, subsequent authors have given to this semantic opposition the names of atelic vs. atelic (the term "telic" originates with Garey 1957), cumulative vs. quantised (Krifka), non-culminated vs. culminated (Moens and Steedman), etc. Finally, there is another "genus" of verbs that share some properties with both accomplishments and states: they are the achievement terms; like the states, they do not have the interval property, and they naturally do not take the progressive (He is reaching the top can only mean that he is in the approach phrase of reaching the top); like accomplishments, they do include a terminal point beyond which the event will be over (he has reached the top).

The next step was to formalize the notion that aspectuality of the VP is derivable from the composition of other constituents, namely, V + NP; the first author to do that explicitly was Verkuyl (1972):

"The durative and non-durative aspects in [these] sentences appear to be composed of a verbal sub-category on the one hand and a configuration of categories of a nominal nature on the other." (1972, page iv, quoted by Dowty,64) In more recent work, Verkuyl has repeatedly spoken out against a narrow view of the telicity of the VP, denying that verbs can be classified as to whether they express "a specific inherent goal"; for him, NPs like three miles in John walked three miles or the letter in Peter wrote the letter "… restrict the progress expressed by the verbs walk and write rather than providing culmination or telos: the internal argument leaves no room for further walking or writing, so to say." (Verkuyl 2000:29) He concludes that telicity/quantisation/culmination is an epiphenomenon: what matters is the trajectory, the measuring scale denoted by the association verb-NP. That telicity is not lexically marked is obvious in the work of many other authors: if it was so, the abundant discussion of aspect shift could not have happened.

Aspect shift and change of state

Vendler himself recognized that very often English verbs change classes. This phenomenon has been termed "aspect shift" or 'type-shifting" (Zucchi 2001and others) in the literature, and one of the three phenomena that can induce it is the presence of PP complements or particles or prefixal modification for Russian (the other two are: properties of the object NP, presence of a frame or a durative adverbial). Dowty, who developed an aspect calculus from each of the Vendlerian classes, proposed the following formula for a canonical accomplishment: "(the) coming about (CAUSE) of a particular state of affairs (BECOME)".

Thus, the logic of a change of state was introduced: John ran two miles is not best described as telic or resultative in the ontological meaning of the term (the event contains no specific inherent goal leading up to a climax after which the event is over and done with), but the sentence denotes a particular state of affairs about John that is the outcome of a dynamic event which can be called running (the verb run has a predicative as well as an "appellative" function). This might sound an unnecessary refinement, but it is precisely this that the notion of aspect shift captures. Starting from Vendler's accomplishments and achievements, Dowty sought to refine the classification, and had many followers: he drew a distinction between single changes of state and complex changes of state. The difference lies in the punctual or intervallic nature of the transition (the term "transition" was adopted by Pustejovsky 2 1991, 1995) between the initial state and the final state denoted by the VP: notice and kill are single changes of states, build a house and walk from x to y are complex change-of-state VPs. 2 Pustejovsky developed a theory of generative or compositional model of lexical semantics, quite different from Verkuyl's or Dowty's "exhaustive" approaches, which assume "a set of primitives and then operate within this set to capture the meanings of all the words in the language." (38) For our purposes here, we need not enter this level of distinction.

Pustejovsky takes the notion of event / aspectual change further. For him, there are three components to event structure: "-the primitive event type of the lexical item; -The rules of event composition; -The mapping rules to lexical structure." (Pustejovsky 1991:39) There are three primitive event types: States, which are evaluated relative to no other event (love, know, resemble); Processes, "a sequence of events identifying the same semantic expression" (run, push, drag), and Transitions, "an event identifying a semantic expression, which is evaluated relative to its opposition." (give, open, build, destroy). (ibid.:40) In Pustejovsky's trees for those primitive types, we find Dowty's BECOME and CAUSE primitive predicates, but operating at different levels of event structure (ibid.: 41).

Figuring prominently among the rules of event composition we find prepositional/particle constructions: a verb whose primitive event type is Process (P) like run, type-shifts to a Transition when it is followed by a phrase like to the store; to the store "projects its own event structure", much in the spirit of D. [START_REF] Davidson | The Logical Form of Action Sentences[END_REF] recognition that prepositions contribute eventual structure as much as the verb. For this type-shift from Process to Transition, Pustejovsky introduces the notation <P,T>. He gives the following logical form for the sentence: "Cause(act(m), become(at(m, the-store)) BY run". The main verb (run) "is actually treated as an argument to <P,T>, … hence creating a "BY manner expression." The matrix verb is type-shifted to a subordinated predicate. The same principles of event composition concern resultative constructions like: 24) Mary hammered the metal flat. 25) The men drank the pot dry.

The adjective is type-shifted to an event interpretation which makes a state out of it, a state "that can be changed by being acted upon". The particle constructions exemplified in 3), 4), 5) above also contribute to type-shifting. [START_REF] Spencer | Verb prefixation in Russian and lexical subordination[END_REF] adopt the same analysis as Pustejovsky; they adapt the notion of "lexical subordination" from [START_REF] Levin | Lexical subordination[END_REF]: in 25), "The syntactic secondary predicator (dry) is semantically primary [it is the] "core predicate"; … the main verb is then subordinated as a manner or means clause [it is the] 'subordinated' predicate." (Spencer and Zaretskaya 1998:5) They give the following "template", which is the same as Pustejovsky's, for these resultative structures:

26) CAUSE [ACT (x)], BECOME (y) by [V(x))]]

This works well for resultative constructions: the y variable can be filled directly by the adjective (dry, clean); they extend the analysis to particle constructions, which are closely related to resultatives; the problem arises for particles like up or down, whose meaning contribution is rather vague. Although the sentence he wiped the table down gives us a strong sense that the table was brought into a new state as a result of wiping (its surface was completely wiped), down cannot as such stand for the y variable in the formula proposed above. [START_REF] Mcintyre | Idiosyncrasy in Particle verbs[END_REF] has a nice explanation: having looked at an important data sample, he noted that down as in wipe down does not occur randomly, but systematically with verbs from a same semantic class, namely verbs that indicate that a whole surface was affected by whatever the verb denotes in the way of cleaning (brush, clean, rub, soap, sponge, etc, down).

He defends the notion of a "construction-specific" meaning, "a meaning which is idiosyncratically confined to the pv construction' (McIntyre 2002: 98). It is actually the structural template proposed above and the independent meaning of both verb and particle that ensures the proper interpretation.

It has appeared that the notion of change of state is crucial in the discussion: we need an aspectual theory more sophisticated than the telicity/atelicity distinction that can capture the strong sense that the syntactic "template" V + NP + particle goes hand in hand with an aspectual change of state reading.

Tenny and the MOC

Tenny's Aspectual Interface Hypothesis permits one to do just that: she endeavors to uncover the principles whereby aspectual distinctions are mapped onto the syntax. She makes the aspect calculus of VPs one of the linking principles between thematic structure and the syntactic projections of arguments: "The universal principles of mapping between thematic structure and syntactic argument structure are governed by aspectual properties. Constraints on the aspectual properties associated with direct internal arguments, indirect internal arguments, and external arguments in syntactic structure constrain the kinds of event participants that can occupy these positions." (Tenny 1994: 2) She then formulates her Measuring-Out Constraint (MOC) on Direct Internal Arguments: "(i) The direct internal argument of a simple verb is constrained so that it undergoes no necessary internal motion or change, unless it is motion or change which 'measures out the event' over time (where 'measuring out' entails that the direct argument plays a particular role in delimiting the event). (ii) Direct internal arguments are the only overt arguments which can 'measure out the event'. (iii) There can be no more than one measuring-out for any event described by a verb. (ibid.:11) "Measuring-Out contains two ingredients: a measuring scale associated with an argument, and a temporal bound or delimitedness." (ibid.:15)

The MOC is evident in two types of verbs: verbs that take an incremental theme (Dowty 1991) (eat an apple, build a house) and verbs of change of state (henceforth abbreviated COS) (ripen, break). Each increment of the apple that is consumed measures progression in the action expressed by the verb; a verb like eat has the capacity of translating the spatial delimitation of the apple (which is an object in space) in a temporal delimitation. I believe the whole point of aspect is there: how to ensure the necessary homomorphism between space and time for inscription in time. The important insight of Tenny is that this aspectual role corresponds to a specific mapping to the syntax.

Canonical examples of "measuring-out" verbs include, apart from consumption and COS verbs, prepositional constructions and phrasal verbs which are the real "delimiters", the nonambiguous markers of a change of state :

27) Mary built a house 28) The lake froze 29) Thomas ate an apple up

We can easily capture the aspectual type-shifting effect of prepositional constructions in the following sentences, using the time-honored adverbial tests: 30a) Anne-Marie polished the countertop for ten minutes 30a) Anne-Marie polished the countertop in ten minutes. 31a) Anne-Marie polished the countertop to a shine / smooth / polished up the countertop ?for an hour 31b) Anne-Marie polished the countertop to a shine / smooth / polished up the countertop in an hour 3 , 32a) He wiped the table for / in an hour. 32b) He wiped down the table in an hour. 30a) implies that Anne-Marie spent ten minutes polishing it, then moved on to another task, while 30a) focuses measures the change of state: it took her 10 minutes to get the countertop polished. 31a) is odd because the for-phrase would measure not the semantic expression of the main verb, but that denoted by the prepositional/adjectival/particle construction: the state of cleanliness would have lasted only for an hour; in an hour in 31b) measures the time it took for the change of state to occur. The verb polish in 31b) becomes lexically subordinated [START_REF] Levin | Lexical subordination[END_REF], providing only the manner in which the change of state obtains.

The same analysis holds for 32a/b).

It follows that apart from a small class of real lexically specified transitions, among which we find canonical achievements (die, kill, break), many consumption, creation and even COS verbs do not lexically include an in-built inherent endpoint: a verb like polish, bake, even eat, are both Transitions and Processes. Thus I come to the conclusion that telicity as implying the existence of an inherent specific goal (a telos) together with a totality entailment is not central for classifying verb phrases: what counts for a classification of VPs is the measuring effect of either the direct object by itself (a real Measure), provided the verb also potentially expresses a change of state, or of the combination of an NP object with a particle/prepositional construction (a Path and Terminus, in Tenny's terminology).

Interestingly, Tenny's theory predicts that a certain number of apparently non-aspectual alternations are in fact explained by the aspectual role of measuring-out. It is particularly the case with "unselected" or "fake" objects, like the (real or fake) reflexive or the one's way object: 33) He washed for an hour. 34) He washed himself ??for / in an hour. 35) He laughed himself silly / to sleep in two minutes.

3 These examples are taken from R. Smollett's 2005 article "Quantized direct objects don't delimit after all", in Verkuyl, H., de Swart, H., van Hout, A. (eds), Perspectives on Aspect,Dordrecht,Springer, According to Tenny, himself in 34) provides the argument which serves to measure out the change, which the corresponding reflexive-less construction does not necessarily entail (in 33).

Pustejovsky comes to the same conclusion for 35): "the false reflexive NP serves the function of representing the predicate opposition in the transition (Pustejovsky 1991: 56)". The whole question is whether this fake object is actually an argument: using data from Russian, Spencer and Zaretskaya contend that it is (see below). Strikingly, it is the structural template in 26) above that ensures that "the argument of the BECOME predicate is mapped to an argument position, irrespective of whether it is also an argument of the subordinated predicate". ( Spencer and Zaretskaya 1998:12) In a way, the structural template forces the interpretation of the postverbal NP as an argument of the main verb.

Tenny provides other constructions which are best explained by her aspectual role: 36) John insulted his boss for five minutes/in five minutes. 37) John insulted his way across the room ?for five minutes / in five minutes.

Similarly, concerning psych verbs, a resultative PP expression can measure out the change of state for a verb like frighten, but not its near synonym fear :

38) The movie frightened the children to death. 39) *The children feared the movie to death. [START_REF] Jackendoff | English particle Constructions[END_REF] discusses a whole class of semi-idiomatic expressions using PP or verb+ particle expressions; some of them (over in 41) are telic particles (in the sense of Tenny), capable of measuring out the event: After all, 44) and 45) would be logically possible with the meaning that he kept on drinking scotch, reading newpapers, etc. Jackendoff then discusses another construction which does use away and takes a postverbal temporal NP: 46) Bill slept the afternoon away. 47) Bill frittered the evening away sleeping.

Here, unlike in the sentences above, quite unexpectedly, away does lend the whole construction a delimited interpretation: 46) could be paraphrased as: "Bill heedlessly used up the afternoon sleeping"; the transition/measuring-out effect is clear: the time is literally used up by the subject doing sth. Of course Bill has not changed in a trivial manner once the event has occurred, but the sentence states that he entered a new state, that of having used up his whole time sleeping, and that counts as a change of state. Again, the template forces this interpretation. We find all the ingredients for measuring-out: the template (Verb + NP + particle) and the consequent "measure" induced by the association between the unselected (fake) NP the afternoon or the evening (fake in the sense that you cannot "sleep an afternoon") the semantics of away, and the construction-specific meaning of this pv construction. This fake NP has all the attributes of a real NP: it cannot be separated from the verb by an adverbial of manner (see 49), whereas the canonical intransitive sentence does not show this However limited, this study of the behavior of pv constructions lends support to Tenny's MOC: it is the direct object NP that is the crucial element in measuring out; it is so strong a constraint that fake or unselected NPs must be inserted into the template when the verb naturally lacks one.

Russian prefixes, the load alternation and "time slices"

Spencer and Zaretskaya extend their conclusions to Russian prefixes: a whole class of prefixes constitute the core predicate, and the main verb is the subordinate predicator, just like in English, as in: 52) Ona vyterla stol: she wiped / scrubbed the table down.

She vy-scrubbed table 53) Ona ispisala svoju ručku: her pen has run out of ink. (lit.: "she out-wrote her pen") She is-wrote pen Apart from the fact that adjunction of the prefix makes the simplex verb (teret', pisat')

perfective, the most obvious difference with English is that the complex lexeme that denotes a change of state is a lexical entry that is distinct from that of the simplex verb. Some prefixes, however, do not have that function:

54) Ona poterla sebe glaza: she rubbed her eyes. She po-rubbed herself eyes 55) Ona napisala pis'mo moej ručkoj: she wrote a letter using my pen.

She na-wrote letter my pen.instr

Here, po-and na-are so-called empty, or pleonastic, prefixes, whose only function is to make the verb perfective: they contribute the exact same meaning than their imperfective prefixless counterparts, they have no valency-changing effect, they do not by themselves induce a change of state, no more no less than the corresponding imperfectives: 56) Ona terla sebe glaza: she rubbed / was rubbing her eyes. 57) Ona pisala pis'mo mojej ručkoj: she wrote / was writing a letter using my pen.

Before I explain this dual behavior of prefixes, I would like to focus on one particular aspect of this phenomenon which I will connect with the aspectual principles discussed above:

the cases where the prefix has a clear valency-changing effect and an aspectual measure role, the former being the effect of the latter; it is the Russian equivalents of the load/spray alternation.

Valency-changing effects

The spray/load alternation is well-known in English: it concerns three-argument verbs, for which two of the internal arguments can alternate: the direct object is either a theme (58) or a location (59).

58) He loaded hay onto the cart. 59) He loaded the cart with hay.

English shows no surface change: the verb load in 59) has no surface marker for the y variable in the BECOME predicate; however, the same aspectual principles ("measuring-out")

and the same structural component ("CAUSE the cart to BECOME full of hay BY loading", on the model of CAUSE the table to BECOME "down" -completely wiped -BY wiping it) seem to apply. Tenny suggests that aspectual principles regulate this alternation; in particular, the theme must be a material that is incrementally homomorphic to the progression expressed by the verb (viz., in 58 the volume of hay increases as it gets loaded), and the location must be a container that gets filled as the event progresses. In fact, both arguments must be able to mutually measure out the event. The alternation does not occur if either of these conditions is not met: 60a) Push the car to the garage. 60b) *Push the garage with the car.

61a) Send a letter to your sister 61b) *Send your sister with a letter.

The garage in 60b) is not an entity that can get incrementally filled as the car goes into it;

neither does the sister in 61b) "progressively" receive the letter. Clause (iii) of the MOC says that there can only be one measure for an event. It is either the theme or the location argument that measures out the event (that contributes to <P,T>).

In other languages, especially Russian, the difference is very often formally marked on the main verb by special prefixes 4 . In Russian, there is a whole class of prefixes whose function is precisely to do that : [START_REF] Veyrenc | Pour une grammaire syntagmatique des préverbes[END_REF] Za-explicity contributes the holistic meaning inherent in these constructions with the location as direct object: every parcel of the barge, the garden and the field is saturated with the entity marked by the theme. The principle behind these constructions is no different from the one applying in vyteret' stol (wipe the table down), except for the extra argument. The only surface difference in English is the change in word order and the with-phrase. In the a) constructions, however, the po-prefix is merely the perfective aspect marker.

The prefixes u-and o-/-ob are two other candidates for the expression of "holistic" themes; u-contributes a meaning of excess; o-/ ob-selects an animate NP that is entirely affected by the action: 65a) Povesit' kartiny na stenu: hang paintings on the wall. po-hang paintings.acc on wall.acc … that Jan the cart with hay be-loads 5 Veyrenc sees in the a) examples a structure based on a be diathesis ("diathèse d'être"), whereas the b) sentences reveal a have diathesis ("diathèse d'avoir"): 7a) is captured by the structural template 'somebody CAUSE the timber to BE on the barge, BY loading", 7b) gives: "somebody CAUSE the barge to HAVE the timber, BY loading". The proposal, formulated in the 1970s, bears strong resemblances to the one discussed here. This componential analysis allows Veyrenc to conclude that the a) examples are the basic structures for this alternation. These examples reveal the semantics and syntax of those particular "strong" prefixes in Russian: not only do they aspectually type-shift the main verb, they vary according to the object that they target and make visible the event (re-)composition that obtains. In those examples, it is the prefix that subcategorizes the location/container NP object in the b) examples, but the accusative case is licensed by the verb; we have: Conceptual structure: za-["totally cover"] subcategorizes: pole ("field"), stol ("table"), etc. Up to now, I have been focussing almost exclusively on the NP + particle predicate (the "core predicate"); however, the role of the subordinated predicate (the main verb) is also situation that is described is that a dog has found itself out (of the house), and that situation is predicated of an individual who was instrumental in doing that by his locking (sub)activity.

The notion of lexical subordination nicely accounts for that. Further research is needed to verify the claim made here. But the connection between the principles regulating situation aspect and the contribution of prepositional/particle constructions has been amply demonstrated.

Conclusion

This study of situation aspect and particles (for English) / prefixes (for Russian) has revealed a deep intricacy between the syntax and semantics of particle / prefixal constructions:

the lexical properties of the verb, i.e. their temporal make-up, constrain the structures they can enter into; if the conditions are met, they trigger in turn a phenomenon of lexical subordination of the main verb. A strong aspectual theory was needed to account for the mapping to syntax of verb-particle structures: Tenny's aspectual role of measuring-out has proved able to fulfil that function; not only can the direct internal argument of a canonical accomplishment "measure out" the event denoted by the verb, the unselected NP of a verbparticle template can also function as a real argument which can then measure out the event together with the result PP/particle complement. The important notion here is that of change of state rather than telicity understood as the "climax" of the verbal event. The study also confirmed Davidson's important insight that prepositions contribute structure to the event just like the verb.

What emerges as a more general conclusion of this paper is a new way of considering verbs:

the structural template proposed by Pustejovsky, Spencer and Zaretskaya, puts on its head our usual representation of what the verb exactly predicates over. In the cases of lexical subordination discussed here, the verb is a mere BY-clause, expressing cause or manner.

Hoekstra and Mulder7 have demonstrated that one of the roles of prepositional complements (we can extend the remark to verb-particle combinations) is precisely to change the focus of predication. The sentence John ran predicates of an individual in an event of running, whereas John ran across the square is three-way ambiguous: 1) either it predicates over an individual John as in the act of running, and that event goes on across (over) the square; 2) or it predicates over an individual John ending up at the other side of the square, as a result of an event of running; 3) but there is a third possibility: it predicates of the state of John across the square being characterised as a state of running. I note the same "predication shift" in, for example, the time-away construction as opposed to the simple time construction: Bill slept the whole afternoon predicates of an individual, Bill, as sleeping over a whole period of time, whereas Bill slept the afternoon away predicates over a situation where the afternoon was heedlessly wasted by an individual who slept through it. As Hoekstra and Mulder conclude, "verbs can be used in a rather flexible way, depending on a number of inherent aspectual properties," (1989: 25) and, if I may add, of elements like preposition/particle elements that also contribute eventual structure.

40)

  He cooked the food in an hour / for an hour. 41) He cooked the food over in an hour / ?for an hour. Others, like away or on, have striking properties: they denote atelic eventualities and, in that interpretation, never occur in the template; on the contrary, they have the property of disallowing direct objects: 42) Dave drank / danced away. 43) Bill drank / read on. 44) *Dave drank scotch away / *danced waltzes away. 45) * Bill drank scotch on / *read newspapers on.

  Sue drank Tuesday night calmly away. 49) *Sue drank calmly Tuesday night away. 50) Sue drank all Tuesday night calmly. 51) Sue drank calmly all Tuesday night. I suggest that the argument-blocking effect in sentences 44-45, and the argument "unblocking" effect in 46-47, are directly the consequence of the aspectual principle of measuring-out as expressed by the template. (or, alternatively, we can adopt Pustejovsky's <P,T> type-shifting principle, which captures the same intuition). The crucial notion in measuring out, I repeat, is the denotation of a change in the state of affairs that ends up being different from what it started out as.

  Syntactic structure: [za-V] governs accusative case. This allows Spencer and Zaretskaya to consider the postverbal NP in the b) examples as a real argument and not as a fake one; that argument is similar in behavior to all other arguments; it can appear in the genitive in negative contexts, it can passivize, it can be the notional logical object of a middle-type reflexive construction, etc (p. 24): 68) On ne odaril ni odnogo iz svoix druzej. He neg o-offered not one.gen of his friends "He did not offer any present to any of his friends." 69) Pole bylo zastroeno: the field was all built up. field was za-built 70) Takije barži zagružajutsja ne tak legko: these barges do not get loaded very easily. such barges za-load-refl not very easily Russian does not differ radically from English: it simply makes the same operations visible in its surface syntax.

  She vy-drank-perf glass of vodka and po-stood-perf it on table "She drank the glass of vodka and put it on the table." 20a) On pročital *(knigu): he read/has read the book.

	He za-loaded barge.acc timber.instr
	19) Ona vypila	stakan vodki i postavila	ego na stol.
	He pro-read-perf *(book)
	20b) On čital	(knigu): he read/was reading the book.
	He read-imp (book)
	21a) On napisal	*(pis'mo): he wrote/has written a letter.

He do-ran do house and v-ran v kitchen 12) Dopisav pis'mo, on zagovoril s nej. do-write letter, he za-talk to her "Having finished writing the letter, he started to talk to her." 13) On vyterel stol: he wiped down the table. He vy-wiped table 14) On otrabotal svoj dolg: He worked his debts off. He ot-worked his debts 15) Budil, budil, no ne mog dobudit'sja eë. woke, woke-imp, but could not do-wake-refl "He was trying hard to wake her, but didn't succeed in waking her up." 16) Ona igrala, a sestra eë podpevala: She played, and her sister sang along. She played-imp, but sister her pod-sang-yva 17) On pogruzil drova na baržu: He loaded timber onto the barge. He po-loaded timber.acc on barge.acc 18) On zagruzil baržu drovami: He loaded the barge with timber. He na-wrote-perf *(letter) 21b) On pisal (pis'mo): he wrote/was writing a letter. He wrote-imp (letter)

  calls them « strong prefixes, … with a syntactic effect (à effet syntaxique) », those prefixes that affect a verb's valency. There are several of them; zais very common, it is used for various semantic classes of verbs and induces a meaning of covering and filling the whole of an entity 5 :

	62a) Pogruzit' drova	na baržu : load timber onto the barge.
	po-load	timber.acc on barge.acc
	62b) Zagruzit' baržu	drovami : load the barge with timber.
	za-load barge.acc timber.instr
	63a) Posadila cvety	v sadu: plant flowers in the garden.
	po-plant flowers.acc in garden.loc
	63b) Zasadil sad	cvetami : plant the (whole garden) with flowers.
	za-plant garden.acc flowers.instr
	64a) Postroit' doma	na pole: build houses on the field.
	po-build houses.acc on field.loc
	64b) Zastroit' pole	domami: cover the field with houses.
	za-build field.acc houses.instr

65b )

 65b Uvesit' stenu kartinami: hang the wall with paintings.

	u-hang wall.acc paintings.instr
	66a) Podarit' podarki		druz'jam : offer presents to friends.
	po-offer presents.acc to-friends.dat
	66b) Odarit' druzjej	podarkami : lavish presents on friends.
	o-offer friends.acc presents.instr
	67a) On podnës	vino	gostjam: he brought wine to the guests.
	He pod-carried wine.acc guests.dat
	67b) On obnës	gostej	vinom: he served wine to all the guests.
	He ob-carried guests.acc wine.instr

  Again, love sb out would be logically possible ("stop loving someone"), on the model of, e.g., tire sb out. But states do not have an internal structure: they project no t "slice" of which to predicate the core predicate. Achievements can take particles, however, because they do As Spencer and Zaretskaya remark, you can write off a car or dig up a bone without ever doing any writing or digging (just as you carry out no locking on the dog if you lock it out); however, if you break a door down or break off from someone, there is, however metaphorically, a breaking event involved. In other words, the main achievement verb is not a BY-clause. Furthermore, achievements cannot enter into the time-away construction: 78) *He froze the night away. *He broke glasses the afternoon away, in spite of the fact that these are all logically possible, e.g. "he (recklessly) spent the whole afternoon breaking glasses (to vent his anger)".

	Interestingly, state verbs seldom tolerate particle formations:
	74) *Hate up, ?love up, *know off,* remember up, *understand down, etc.
	75) *love sb out
	have an element of dynamism:
	76) Freeze up
	Dry up/off/out
	Kill off
	Break up/off/out…
	The verb itself already inherently denotes a change, which is lexically in-built, so to speak,
	and those verbs are necessarily transitive or unaccusative (i.e., they take a deep object realized
	as a surface subject); the particle has at best an intensifying effect, it can express spatial
	modification or highlight a different NP subcategorization, but it is not aspectual in the sense
	that it forces a measuring-out that was not already present in the verb itself: the temporal
	slices are virtually non-existent, there is only one, which is precisely the one that already
	measures the change, and that is expressed by the main verb ; thus we predict that lexical
	subordination is much less evident in achievements, which means that achievements cannot
	have "real" fake objects, whereas canonical activities and transitive accomplishments (dig,
	wipe, read, lock, write) may or may not have unselected objects:
	77) *Freeze himself to death
	*Arrive up, down.
	*Break,* shatter one's way (out, off…)
	Break the door down
	Eat, push, work, laugh, etc, one's way (up, into NP, through…)
	Write the car off
	Lock dog out
	Dig the bone up

The notion of a "neutral prefix" is a long-standing tradition in Russian aspectual research; they are prefixes which merely make an imperfective verb stem perfective, without adding any meaning nuances whatsoever; among those, po-is the generalized neutral perfective marker, semantically empty, and one of the "criteria that go most towards making a systematic set of aspectual oppositions"(Comrie, 1976, writing about Slavic po-).

It is also the case in Dutch, which uses the prefix be-: … dat Jan het hooi op de wagen laadt. …that Jan the hay on the cart loads … dat Jan de wagen met hooi belaadt.

"Unergatives as copular verbs" (1989).

essential in licensing verb-particle constructions: not all verbs can do that. The Vendlerian temporal schemata have to come back into the picture.

Restrictions, or how time comes back in

Other authors [START_REF] Hoekstra | Aspect and theta theory[END_REF][START_REF] Guéron | The temporal interpretation of predication[END_REF] The notion of temporal slices or event restructuring is an essential element for understanding the verb's behavior, in particular whether it allows particle or PP combinations:

write a letter has a descriptive content, it is an activity verb that has an internal structure made up of different "time slices" 6 (t1, t2, …tn); each of these slices is matched by each of the increments of the letter. Things are straightforward in write a letter. What about a VP like lock the dog out ? The descriptive content of lock ("to shut using a key") does not naturally apply to a dog (a dog has no lock); but lock can be decomposed into temporal slices or subevents; it is an eventuality that takes time (lock = t1, t2 … tn ); what makes lock the dog out possible is that one of the locking subevent (concretely, one -or several -of the phases of someone locking a door) can lead to the situation resulting in [the dog out]; there is a double predication, captured by Hoekstra and Guéron in the form of a SC complement; the real 6 Hoekstra (Aspect and Theta theory, 1991) suggests that the semantic complexity of accomplishment predicates (they include a phasal part and an endpoint) "be mirrored by a syntactic complexity" (14). He proposes the following structure for John ate a cake: V +dyn [SC NP PRED], which comes down to saying that accomplishment precicates have a resultative configuration; PRED is an abstract predicate much like a particle (up in the case of eat). This complex syntactic structure nicely accounts for the aspectual difference between an activity predicate (John teased his sister) and an accomplishment (John ate a cake), which have the same surface structure (S+V+NPcount). See also Mulder (1992).


Andreas Wombacher
email: a.wombacher@utwente.nl

Mohammad Rezwanul Huq

Towards Automatic Capturing of Semi-Structured Process Provenance

Often data processing is not implemented by a workflow system or an integration application but is performed manually by humans along the lines of a more or less specified procedure. Collecting provenance information in semistructured processes can not be automated. Further, manual collection of provenance information is error prone and time consuming. Therefore, we propose to infer provenance information based on the file read and write access of users. The derived provenance information is complete, but has a low precision. Therefore, we propose further to introducing organizational guidelines in order to improve the precision of the inferred provenance information.

Introduction

Semi-structured processes are business or scientific workflows, where the execution of the workflow is not completely controlled by a workflow engine, i.e., an implementation of a formal workflow model. Examples can be found in scientific communities where a workflow of data cleansing, data analysis and data publishing is informally described but the workflow is not automated. Other examples can be found in scenarios where several people potentially from different organizations cooperate e.g. in creating a yearly progress report or writing a scientific paper.

The lack of a workflow system controlling the process execution and the usage of non-provenance aware applications for executing activities, i.e., the application is not recording provenance information itself, makes it difficult to answer provenance questions like 'Who did what when and how?'. Since the provenance question can not be answered it is hard to assess the quality of the output of the semi-structured process, like e.g. the quality of data in a report. In many scenarios, manual provenance acquisition is infeasible since it is too time consuming, and therefore too costly. Thus, the aim is to explore automatic provenance capturing in semi-structured processes.

By analyzing the execution of semi-structured processes the following observations can be made: First, the result of an activity is a single document or a set of documents.

Second, information contributing to a document is often copied from previous activity results, i.e., other documents. Thus, for an activity the source document must have been read/opened before the information can be copied and saved in the target document. Therefore, each document which has been read before a save operation is performed may have contributed to the target document.

Third, users of ICT systems organize their information often in hierarchical structures like e.g. directories. Thus, for a certain activity a user has to perform specific directories are relevant.

Fourth, several revisions of documents are issued over time, where the revision number may or may not be explicated in the file name. However, the process handles potentially various revisions of a document.

In this paper, an approach to automatically capture provenance information for semi-structured processes is proposed. The basic idea is that all documents, which have been read by a user, may have contributed to a document saved later on. Since this derived provenance is rather imprecise it is proposed to facilitate knowledge of the process, of the revisions of documents, and of the organization of the documents by the user to increase the precision. In particular, it is proposed to introduce organizational directives, i.e., guidelines for the user on how to organize information relevant to the data processing workflow. The more strict these guidelines are the higher the precision that can be achieved. However, strict guidelines lower the degree of freedom for a user to organize 'her' data and therefore may result in non complying users effecting the data quality.

In a next step we investigate the mining of provenance relations from the collected version information of the used files without considering the organizational directives. It turns out that actions performed by a script or program can be mined well while manual modifications of files can be detected but the provenance can not be mined. The results are qualitatively compared with the provenance information derived from the organizational directives.

The proposed approach is based on a WebDAV infrastructure which supports version control of files. The proposed approach has been implemented and evaluated on the paper writing of this paper.

In the following related work is discussed (Sect 2) before a use case is introduced (Sect 3). The approach is presented on a conceptual level (Sect 4) while a more technical view on the derivation of provenance information is provided in Sect 5. Next an evaluation of the proposed approach (Sect 6) is presented followed by a description of the mining approach (Sect 7) and the conclusions (Sect 8).

Related Work

Automatic collection of provenance information is often applied in e-science workflow systems, like e.g. Kepler [START_REF] Ludascher | Scientific workflow management and the Kepler system[END_REF] or Taverna [START_REF] Oinn | Taverna: a tool for the composition and enactment of bioinformatics workflows[END_REF]. Most systems even rely on exchanging data via files. In previous work [START_REF] Huq | Facilitating fine grained data provenance using temporal data model[END_REF] we investigated inference of provenance information for stream processing workflow system using a temporal model. However, the workflow system is executing a workflow and all involved tasks are executed automatically which is a major difference to our requirements.

Provenance information is also collected in closed systems like e.g. a data warehouse [START_REF] Cui | Lineage tracing for general data warehouse transformations[END_REF] or a relational database [START_REF] Szomszor | Recording and reasoning over data provenance in web and grid services[END_REF]. The level of granularity in these approaches varies between fine-grained and coarse-grained data provenance [START_REF] Simmhan | A survey of data provenance in e-science[END_REF]. The fact that the provenance acquisition is limited to the system makes it infeasible for our scenario. Automatic collection of provenance information focusing on the exchange of information is addressed in various ways. In [START_REF] Allen | Capturing provenance in the wild[END_REF] provenance information is captured by monitoring a service bus where the invoked services must not be provenance aware. Although this is quite close to the scenario at hand, in this case all processing has to be implemented as a service, which is not the case in our case. The approach in [START_REF] Seltzer | Provenanceaware storage systems[END_REF] records file manipulation operations including system variables and their changes. However, this approach is limited to a single computer since it is woven into the kernel of a linux system which differs significantly from our scenario. This may be the closest match to our approach. In [START_REF] Margo | The case for browser provenance[END_REF] the authors automatically collect provenance information based on events recorded by browsers. However, the approach is limited to a single application.

Systems for storing provenance information are e.g. Tupelo2 [START_REF] Futrelle | Tupelo server[END_REF] or Karma2 [START_REF] Simmhan | Karma2: Provenance management for data driven workflows[END_REF]. These systems provide an into store provenance information and provide means to query the data. The provenance information derived by the proposed approach could be stored in such a system. Further, the acquired provenance information could be made accessible in different provenance models like e.g. the Open Provenance Model (OPM) [START_REF] Moreau | The open provenance model: An overview[END_REF] or the value centric model (TVC) [START_REF] Misra | Advances and Challenges for Scalable Provenance in Stream Processing Systems[END_REF]. However these are just alternative representations of the derived provenance data, while the focus of this paper is on acquiring the provenance data rather then how to represent them.

Use Case

The process used as a running example is writing this technical paper with multiple authors in Latex. After initializing the project, two authors are writing together on the same paper. A BPMN notation of the process is depicted in Fig 1 1 .

In the process the following activities can be executed in arbitrary order with an arbitrary number of repetitions:

-creation, update and conversion activities on figures and graphics files (modify figure) -creation and update activities on bibtex files (modify bibtex) -creation and update activities on latex files (modify latex) -pdflatex activity, for creating a pdf file of the paper (do pdflatex) -bibtex activity, for creating the bibliography file (bbl file) related to the paper (do bibtex)

All activities result in a single result or output document/file. There are two authors involved in this particular paper writing process, which makes it interesting to determine whether a specific revision of a generated pdf file contains all the latest file revisions. Especially whether all figures have been properly converted before executing the pdflatex task. Further, it can be inferred whether in a specific pdf revision of the paper all indexes and the bibliographic information is up to date, since this requires the following task sequence: pdflatex -bibtex -pdflatex -pdflatex.

Approach

The aim is to infer provenance information from a semi-structured process execution without the user providing any information and the legacy applications not being provenance aware. Since files are used to exchange information between different activities of the process, the approach is based on documenting data manipulations on files. Combining file manipulation information with data dependencies of the process allows to infer which revision of which file may have contributed to a revision of a file written by a particular user.

The intuition is that data processing is based on zero or several input files producing one output file. In particular, all files which have been opened before the point in time a file is saved potentially contributed to the creation of the saved file. These derived provenance relations have a very low precision, i.e., are too broad especially when considering the amount of files opened in the coarse of a day at a desktop computer.

Therefore, we propose to facilitate knowledge of the process to derive organizational directives, i.e., rules for the user performing the data processing activities to be able to associate files with specific activities in the process. Thus, they support inference of provenance information. Organizational directives give a responsibility to the user without technically enforcing the directive. Organizational directives are widely implemented in organizations, like e.g. you are not allowed to install software on your company laptop, you are not allowed to download copyright protected material, you are obliged to make backups or to encrypt your hard disc. In particular, a relation exists, if a file with revision v s has been written after a file with revision v r has been read and v r < v s assuming a global version scheme. In the following the basic derivation of provenance relations (continuous part) and the creation of organizational directives (one time part) of the approach are discussed in more detail after the infrastructure and some generic directives are introduced. The inferred provenance information is made accessible via a web application2 .

Infrastructure to Capture User Behavior

The proposed approach is based on a Web based infrastructure for file storage and version control, in particular, a WebDAV infrastructure facilitating a Subversion (SVN) as version control system. WebDAV is an HTTP based protocol for managing content on a web server, i.e., accessing, writing and moving files. WebDAV seamlessly integrates into various operating systems, i.e., the WebDAV server appears as a mounted network drive and therefore is intuitively usable also for basic ICT users.

Further, since the WebDAV protocol is based on HTTP it easily supports distributed and cross-organizational scenarios, like the motivating example in Sect 3. Furthermore, WebDAV can also be used for information dissemination. From a provenance capturing point of view, WebDAV has the advantage that it supports logging of file read operations via the web server access log and logging of write operations via the underlying version control system. In particular, the web server access log documents the read (GET), write (PUT), move (MOVE), and delete (DELETE) operations applied to files on the server. The choice of using WebDAV seems a bit outdated compared to currently existing offers like DropBox, Google Drive or Microsoft SkyDrive. While all these offers provide history information comparable to the SVN functionality, the size of the history information maintained is limited. The history information documents the write access to files, however, the read access to files is not documented there. Furthermore, the products synchronize the files with all related devices instantly, thus, every read operation by another person after a change is a local file operation, which is not documented. Therefore, WebDAV although old fashioned allows to track read access since the WebDAV functionality is under our own control.

Generic Organizational Directives

The proposed approach is based on observing the handling of files. Thus, some generic directives are needed to ensure that the handling of files can be observed at the first place. Similar to directives in organizations that all important information has to be saved on a network drive because local disks are not backuped, a data security directive is introduced requiring the user to save data on a mounted network drive, i.e., a WebDAV server.

Directive 1 (Data Security) Users must save all files related to a semi-structured process on the network drive. Thus, it is not allowed to store files related to the process on a local disc. This directive is necessary, since local file systems can not be monitored with regard to file handling that easily from outside the computer.

A standard directive in organizations is that login and password information must not be shared between different users. It must always be possible to identify a responsible user for any observed action in the infrastructure.

Directive 2 (Delegation) In case of vacation or illness the execution of activities must be delegated.

In many organizations you have a clean desk policy, which means that at the end of the day all business relevant documents must be removed from the desk. Translating this into the digital world means that the desktop computer has to be switched off at the end of the day, which is also in the context of green IT getting more attention. This results in the following directive: Directive 3 (Clean Desk Policy) The user must shut down his/her computer at the end of the day, i.e., there are no open files or applications active anymore.

Provenance relations are based on the observed reading and saving of files. Since it can not be observed by WebDAV when a file is closed again, the clean desk policy directive enforces that at the end of a day all files are closed. Thus, this is a synchronization point for deriving provenance relations by excluding files opened at previous days.

Provenance Relations

The generic directives are the basis to infer provenance relations based on WebDAV commands. A provenance relation is a relation between a read or save operation of a file A and a save operation of a file B, where the read or save operation of file A is performed before the save operation of file B. The order of the operations can be determined by the timestamps at which the operations are observed and on the associated revision numbers.

Due to directive 3 only read operations which have been performed at the same day as the write operation are considered. Further, according to directive 2 each file access is associated with a specific user, thus, provenance relations require that the files are read and saved by the same user.

Based on the scenario described in Sect 3 it can be derived that e.g. the modification of a latex file will not use information from an image file. This independence, which is derivable from the process, has to be explicated as specific organizational directives as discussed in the following section.

Specific Organizational Directives

The goal of the organizational directives is to increase the precision of data provenance by excluding observed provenance relations which are actually irrelevant. Since provenance relations are based on sets of read files with a single point in time when files are certainly closed again (see Directive 3), additional mechanisms are required to determine the precise inference of data provenance. One way is to apply directives on the hierarchical structure of data on the network drive. Further such a structure is often established to exchange information between different organizations and to control access rights. In particular, one possible approach is to establish a basic directory structure where each directory is associated to a particular activity in a data processing workflow, as it is known e.g. from group ware solutions like BSCW or groove. An alternative is to use filters based on regular expressions exploiting file naming conventions or specific file extensions being unique for the output of an activity.

However, the derived directives might be not specific enough or too complicated to implement resulting in imprecise provenance information. The challenge is to find a good balance between usability of organizational directives and the targeted data provenance precision.

With regard to the motivating scenario in Sect 3 the following directives should be instantiated: 5. An update of a bibtex file only depends on the old bibtex file, i.e. the filename of source and target are equivalent. 6. The execution of a pdflatex command reads data from all project directories and writes a pdf file in the project root directory. 7. The execution of a bibtex command reads from the project root directory and the bib directory and writes a bbl file in the project root directory.

Provenance Relation Derivation

After the conceptual introduction in the previous section a more detailed technical discussion follows. The provenance information forms a provenance graph, which consists of vertices and edges. A vertex is either an access log entry or a SVN log entry. The edges represent the provenance relations. In this paper three classes of provenance relations are distinguished: provenance relation correlating SVN and access log entries, SVN step relations, and relations derived from directives. A access log contains read (GET), write (PUT), move (MOVE), and delete (DELETE) operations (WebDAV commands) applied to files. Further, the SVN internal logs contains write (Add, Modify), delete (Delete) and move (combined Add and Delete) entries. All relation classes are discussed in the following subsections after a discussion on observations of file handling using WebDAV clients.

File Handling Observations

The manipulation of files via a WebDAV client and documenting them in SVN and access logs is not as straight forward as initially expected. In particular, the following observations can be made:

First, adding and updating files is realized in different combinations of WebDAV commands by different applications.

Second, the WebDAV MOVE command documents only the source filename of the move in the access log, but not the destination filename. However, by using WebDAV with autocommit each change on a file results in a new revision number, thus, only a MOVE command results in a delete and an add SVN log entry with the same revision number. This can be facilitated to correlate SVN and access log entries.

Third, a WebDAV DELETE command removes a file from the SVN repository. After the command is executed the file is not in the repository anymore, thus, the revision number of the removal of the file requires an extra query to the SVN log.

Fourth, reading a file is only documented in the access log. Which revision of a file has been read has to be inferred from the state of the SVN and the size of the file read.

The final observation is that the correlation between SVN and access log entries can not be based on time, since the timestamps recorded by the SVN and the access log are points in time when the event has been recorded in the corresponding system. Thus, the timestamp of the access log entry is always before the entry in the SVN log since the HTTP request is first processed by the HTTP server which forwards the request to the WebDAV and therefore to the SVN. However, in case of two fast subsequent operations, it is possible that the access log has two entries before any entry is recorded in the SVN log. Thus, it is sometimes hard to infer the correlation of access to SVN log entries.

Based on these observations, a simplified version of the correlation algorithm is depicted in Alg 1. The token variable indicates whether the SVN entry can be correlated to an access log entry. A correlation is possible if the SVN entry is either a Delete or an Add entry (line 3). Further, a correlation is possible if the SVN entry is a Modify entry and the previous entry has been older than 2 seconds (line 4). The two second bound is based on the observation that an incremental upload of a file to the SVN resulted in a new revision approximately every second in our test system.

If an entry can not be correlated to an access log entry (line 7), than it is inferred that an incremental upload is occurring. Incremental updates are documented as a provenance relation between SVN log entries called SVN step relation (line 9). Otherwise, Add and Modify entries are correlated with PUT entries (line 11) and Delete entries are correlated either with DELETE (line 12) or with MOVE entries (line 13).

Since the file access is not documented in the SVN log entries, a second loop is executed on the access log entries (line 14). In particular, all GET entries are selected (line 15). For each GET entry the corresponding SVN entry is inferred (line 16) and the entries are correlated (line 17). In Fig 3

Directive Provenance Relations

The last type of relations are the ones derived from organizational directives. This type of relation is inferred between access log entries only. As outlined in Sect 4 all files read at the same day as another file is saved are potentially contributing to the saved file. The relation is labeled by the associated activity in the process. The organizational directives can be translated into constraints on these potential provenance relations mainly by constraining files locations and filenames of sources and targets of a provenance relation.

For example Directives 4 in Sect 4.4 determine that only files in directory pics are relevant for the 'modify figure' activity (see Fig 1). Thus, files of other directories do not contribute to any provenance relation associated to this activity. In Fig 3 an example of the 'modify figure' directive relation is depicted. Since file pics/prototype.vsd (F1) is a prefix (ignoring the extension) of file pics/prototype architecture.eps (F2) as specified in directive 4.4 a directive relation between the GET(F1, Rezwan) access log entry and the PUT(F2, Rezwan) access log entry can be inferred.

Evaluation

To evaluate the proposed approach the running example described in Sect 3 is used. The scenario is a semi-structured process of writing a scientific paper using latex, where figures are usually created in Microsoft Visio, which are then converted to Enhanced Windows Metafile (emf) files, and further into Encapsulated PostScript (eps) files. The pdflatex command uses a library to convert the eps figure files into pdf figure files, which can then be used in the resulting pdf file.

The process uses the generic organizational directives (directives 1-3 in Sect 4.2) as well as the specific organizational directives (directives 4.1-7) discussed in Sect 4.4.

These organizational directives are not hard to implement, since we use the same way of structuring a paper writing project for years already. Our guess is that for many semi-structured processes this is similar, since people tend to organize their data rather on content and topics than on time.

Overhead

The paper is based on two latex files, which uses three style files contained in WebDAV. There are six bibtex files used and one image file with its corresponding emf, eps and pdf files. Further there is one BPMN file directly available as pdf file. The processing uses 4 auxiliary files and writes a single pdf file.

The overhead for the user during this experiment is clearly experienced due to the network delay introduced by using WebDAV compared to a local disc. My ADSL line at home is a bout a 1000 times slower than my local disc access. In particular, for a pdflatex command 840kB are read and 377kB are written, thus, in total 1.2MB are transferred. Further, for a bibtex command 250kB are read and 3kB are written, thus, in total 253MB are transferred. So far we have approximately 120 executions of the pdflatex command during the complete paper writing process. As a conclusion, since a build is not performed that often, the overhead is effecting our working experience only marginally.

The usage of WebDAV has an influence on the network load. How much depends on the size of the files the users are working with. In the context of latex these are rather small files and therefore the effects are hardly measurable. In case of other applications using e.g. spatial information or large image files with many write operations this may be different.

Quality

Quality assessment is problematic since there is no ground truth. Capturing the ground truth automatically is difficult. It would require to extend the operating system and monitor all content related actions, such as opening and closing files, copy and past operations from one application/file to another etc. This includes also the handling of content by non UI applications like e.g. running a pdflatex command. In this case file read system level routines have to be monitored. With the current available resources this is not feasible. In the provenance community there are groups of people researching on how to do this best, however, we are not aware of a complete solution yet -especially not for windows systems.

As a consequence the only possibility is to manually assess the quality of the inferred provenance information by inspection. The manual inspection does not show any missing provenance relations. Sometimes additional provenance relations are reported, which are e.g. artifacts of file transfers (temporary files). From our inspection we have not found cases with missing information. The precision depends on the organizational directives, which can be adjusted to the required level of precision as discussed before. Please be aware that the current alternative is no provenance information at all.

Mining Provenance Patterns

The mining approach uses the available log information and applies some counting and some statistic methods to infer provenance relations between different filenames. In particular, the assumption is if an activity is performed repeatedly then the same relations must show up in the log files. In a first step the time difference between file accesses is used to mine provenance relations and in a second step the frequency of file updates is considered.

Time based Mining

Before the actual mining can start the available dataset has to be investigated with regards to the characteristics of accessing files. The time behavior of a system depends besides others on the used application, the system, and the network connection. Therefore it is not possible to provide an absolute number here. Thus, a histogram of the time difference between two subsequent entries in the log is calculated (see Fig 4). In the histogram you can see that many files are accessed within a time difference of two seconds. The histogram turns flat for time differences greater than 12 seconds therefore, in the following we use the 12 seconds as an upper bound to infer provenance relations between files.

Next we retrieve all pairs of log entries which are less than 12 seconds apart and appear at least twice, remove transitive relations, and represent these relations as a weighted graph, where the weight corresponds to the number of observed occurrences of the relation. To enforce a directed weighted graph, the directionality is enforced by considering only the direction with the higher weight. The directed graphs are depicted in Fig 5 and6, where the thickness of the connection corresponds to the weight of the relation. . The two activities are captured in one graph since the underlying dataset was produced by using a tool, which provides a macro to perform the sequence pdflatex-pdflatex-bibtex-pdflatex automatically. Therefore no sufficient big time difference can be observed between the provenance related to the bibtex and the pdflatex activity. This graph also contains the conversion of figures from eps format to pdf format which is performed by a script related to the pdflatex command. This is visible by the writing of pdf files with the suffix eps converted-to. The corresponding eps files are not included since the weights of the relations must be at least two.

An unexpected node in this graph is the writing of file paper.tex since it is not related to performing the two activities. The explanation for this is that the used tool before executing the above sequence of bibtex and pdflatex commands checks whether all source files have been saved. If this is not the case then the tool automatically saves the modified files. Therefore, the writing of the latex source file paper.tex becomes a part of this graph.

The graphs in Overall it can be concluded that all graphs are related to some automated processing initiated by the user. However, manual modifications of files are not observed since they usually require more than 12 seconds to perform the modification, like e.g. writing a new section in the paper.

Frequency Analysis

Next we try to identify the files which are mainly manipulated manually. To do so we calculate the histogram of files being written as partially depicted in Fig 7 . This histogram is compared with the histogram of the files being part of the provenance relations as discussed in the previous subsection. A file can be a source or the target of the provenance relation. In Fig 7 the two ways of participation are explicated per file. If a file is written often and participates a lot in provenance relations like e.g. file paper.pdf, than it is unlikely that this file is subject to manual manipulation. On the other hand side if a file hardly participates in a provenance relation but is written often then it is most likely manipulated manually often like e.g. file paper.tex. Files at the tail of the histogram are potentially subject to manual modification.

Since it is not possible to mine the sources used for manual manipulations of a file without looking at the content of the files, the proposed approach is to ask the user to provide patterns on how to derive provenance relations for these files. In case of figure and latex files the provenance relation mainly includes the other figure and latex files often with the same name, just different versions. The same applies for bibtex files.

The decision on how much of the tail of the histogram is considered determines the imprecision of the derived provenance relations compared to the manual effort required to explicate these rules.

Evaluation

Comparing the clusters and the manual manipulations identified in the previous two sections and compare them to the organizational guidelines specified in Sect 4.4 shows some interesting results: The mining based approach does not make any assumptions on the behavior of the user. However, in case of manually modified files user input is required to derive the provenance relations. The files to which this applies can be mined automatically.

The organizational directions distinguish the pdflatex and bibtex activity. However, the mining approach identified additional automated activities like the conversion of emf to eps files and the conversion from eps to pdf files. This indicates that the organizational guidelines may be incomplete.

Comparing the mined graph for bibtex and pdflatex activity with the provenance derived using organizational guidelines it turns out that the mined approach covers pretty well the real provenance although it may have some additional provenance relations. This is because the processing of bibtex and pdflatex command in a sequence by the tool results in mined provenance relations which are actually not existent.

Conclusion

In this paper, a provenance capturing approach for semi-structured processes involving provenance unaware legacy systems is proposed. Further, the derivation of different classes of provenance relations is discussed. It has been argued that the recall of the proposed approach is very high while the precision depends on used organizational directives, i.e., constraints on handling files as a basis for deriving provenance relations.

Future work should address the currently used 'version on every write' approach to minimize the versions used. A further topic is instead of deriving organizational directives to observe directives and assess the quality of the data handling as applied by the users for deriving provenance relations.

Fig. 1 .

 1 Fig. 1. Editing phase of a paper writing process

Fig. 2 .

 2 Fig. 2. Prototype data processing

  Further, the Subversion (SVN) version control log documents write (Add, Modify), delete (Delete) and move (combined Add and Delete) operations. Both sources (see content gray box in Fig 2) are required to capture the file information and therefore have to be correlated (see Sect 5.1).

Directive 4 ( 3 . 4 .

 434 Scientific paper writing) 1. All bibtex files are located in a bib subdirectory of the project root directory. 2. All pictures and figures are located in a pics subdirectory of the project root directory. All latex files, project files and auxiliary files are located in the project root directory. Figures may require a conversion of file formats. The source figure filename is a prefix of the target figure filename ignoring file extensions.

Algorithm 1 :Fig. 3 .

 13 Fig. 3. Derived relations for the paper writing use case

Fig. 4 .

 4 Fig. 4. Time difference in seconds between subsequent entries in the log file

Fig. 5 . 1 Fig. 6 .

 516 Fig. 5. Cluster 1

  Fig 5 are related to figure conversion. It contains the conversion of figures from the emf format into eps format initiated by the author using a conversion tool. The conversion of the other figures is not represented in this graph since a frequency of at least two relations was required. The graph containing the visio file (vsd extension) represents the copying of a visio figure into an emf file.

Fig. 7 .

 7 Fig. 7. Histogram of occurrence of files as a source or as a target in an identified provenance relation compared to the frequency of the file being written (incomplete)

  an example of the access and SVN log are

	1 token=true;
	2 forall the SVN entries do
	3	if Delete or Add then token=true;
	4	if Modify and size>0 and time difference to previous event<2sec then
	5	token=true;
	6	if not token then
	7	ignore entry for correlation;
	8	document SVN step relation with previous event;
	9	else
	10	if Add or Modify then correlate to PUT;
	11	if Delete then
	12	correlate to DELETE;
	13	if not possible then correlate to MOVE;
	14 forall the access log entries do
	15	if GET then
	16	find SVN entry preceding the GET with same filename and size;
	17	correlate entries;

Created with http://oryx-project.org/

accessible at http://www.sensordatalab.org/offline_provenance_web/