Formalization of Workflows and Correctness Issues in the Presence of Concurrency View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

1999-04

AUTHORS

ÏsmaÏlcem Budak Arpinar, UĞur Halici, Sena Arpinar, Asuman DoĞaÇ

ABSTRACT

In this paper, main components of a workflow system that are relevant to the correctness in the presence of concurrency are formalized based on set theory and graph theory. The formalization which constitutes the theoretical basis of the correctness criterion provided can be summarized as follows: -Activities of a workflow are represented through a notation based on set theory to make it possible to formalize the conceptual grouping of activities. -Control-flow is represented as a special graph based on this set definition, and it includes serial composition, parallel composition, conditional branching, and nesting of individual activities and conceptual activities themselves. -Data-flow is represented as a directed acyclic graph in conformance with the control-flow graph. The formalization of correctness of concurrently executing workflow instances is based on this framework by defining two categories of constraints on the workflow environment with which the workflow instances and their activities interact. These categories are: -Basic constraints that specify the correct states of a workflow environment. -Inter-activity constraints that define the semantic dependencies among activities such as an activity requiring the validity of a constraint that is set or verified by a preceding activity. Basic constraints graph and inter-activity constraints graph which are in conformance with the control-flow and data-flow graphs are then defined to represent these constraints. These graphs are used in formalizing the intervals among activities where an inter-activity constraint should be maintained and the intervals where a basic constraint remains invalid. A correctness criterion is defined for an interleaved execution of workflow instances using the constraints graphs. A concurrency control mechanism, namely Constraint Based Concurrency Control technique is developed based on the correctness criterion. The performance analysis shows the superiority of the proposed technique. Other possible approaches to the problem are also presented. More... »

PAGES

199-248

References to SciGraph publications

  • 1996-01. Transaction decomposition using transaction semantics in DISTRIBUTED AND PARALLEL DATABASES
  • 1995-04. Managing heterogeneous multi-system tasks to support enterprise-wide operations in DISTRIBUTED AND PARALLEL DATABASES
  • 1995-04. An overview of workflow management: From process modeling to workflow automation infrastructure in DISTRIBUTED AND PARALLEL DATABASES
  • 1998-03. Adeptflex—Supporting Dynamic Changes of Workflows Without Losing Control in JOURNAL OF INTELLIGENT INFORMATION SYSTEMS
  • Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1023/a:1008758612291

    DOI

    http://dx.doi.org/10.1023/a:1008758612291

    DIMENSIONS

    https://app.dimensions.ai/details/publication/pub.1024207832


    Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
    Incoming Citations Browse incoming citations for this publication using opencitations.net

    JSON-LD is the canonical representation for SciGraph data.

    TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT

    [
      {
        "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
        "about": [
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0806", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Information Systems", 
            "type": "DefinedTerm"
          }, 
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/08", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Information and Computing Sciences", 
            "type": "DefinedTerm"
          }
        ], 
        "author": [
          {
            "affiliation": {
              "alternateName": "Middle East Technical University", 
              "id": "https://www.grid.ac/institutes/grid.6935.9", 
              "name": [
                "Software Research and Development Center, Department of Computer Engineering, Middle East Technical University (METU), 06531, Ankara, Turkey"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Arpinar", 
            "givenName": "\u00cfsma\u00cflcem Budak", 
            "id": "sg:person.015106543057.92", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015106543057.92"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Middle East Technical University", 
              "id": "https://www.grid.ac/institutes/grid.6935.9", 
              "name": [
                "Software Research and Development Center, Department of Computer Engineering, Middle East Technical University (METU), 06531, Ankara, Turkey"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Halici", 
            "givenName": "U\u011eur", 
            "id": "sg:person.012470124473.98", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012470124473.98"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Middle East Technical University", 
              "id": "https://www.grid.ac/institutes/grid.6935.9", 
              "name": [
                "Software Research and Development Center, Department of Computer Engineering, Middle East Technical University (METU), 06531, Ankara, Turkey"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Arpinar", 
            "givenName": "Sena", 
            "id": "sg:person.07721402144.55", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07721402144.55"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Middle East Technical University", 
              "id": "https://www.grid.ac/institutes/grid.6935.9", 
              "name": [
                "Software Research and Development Center, Department of Computer Engineering, Middle East Technical University (METU), 06531, Ankara, Turkey"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Do\u011ea\u00c7", 
            "givenName": "Asuman", 
            "id": "sg:person.01074167140.73", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01074167140.73"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "sg:pub.10.1007/bf01277644", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1004226782", 
              "https://doi.org/10.1007/bf01277644"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf01277644", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1004226782", 
              "https://doi.org/10.1007/bf01277644"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf01277643", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1019738307", 
              "https://doi.org/10.1007/bf01277643"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf01277643", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1019738307", 
              "https://doi.org/10.1007/bf01277643"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf00122147", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1020871365", 
              "https://doi.org/10.1007/bf00122147"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf00122147", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1020871365", 
              "https://doi.org/10.1007/bf00122147"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1023/a:1008604709862", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1023335759", 
              "https://doi.org/10.1023/a:1008604709862"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/319996.319999", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1038103660"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1088/0967-1846/3/4/003", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1059121860"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "1999-04", 
        "datePublishedReg": "1999-04-01", 
        "description": "In this paper, main components of a workflow system that are relevant to the correctness in the presence of concurrency are formalized based on set theory and graph theory. The formalization which constitutes the theoretical basis of the correctness criterion provided can be summarized as follows: -Activities of a workflow are represented through a notation based on set theory to make it possible to formalize the conceptual grouping of activities. -Control-flow is represented as a special graph based on this set definition, and it includes serial composition, parallel composition, conditional branching, and nesting of individual activities and conceptual activities themselves. -Data-flow is represented as a directed acyclic graph in conformance with the control-flow graph. The formalization of correctness of concurrently executing workflow instances is based on this framework by defining two categories of constraints on the workflow environment with which the workflow instances and their activities interact. These categories are: -Basic constraints that specify the correct states of a workflow environment. -Inter-activity constraints that define the semantic dependencies among activities such as an activity requiring the validity of a constraint that is set or verified by a preceding activity. Basic constraints graph and inter-activity constraints graph which are in conformance with the control-flow and data-flow graphs are then defined to represent these constraints. These graphs are used in formalizing the intervals among activities where an inter-activity constraint should be maintained and the intervals where a basic constraint remains invalid. A correctness criterion is defined for an interleaved execution of workflow instances using the constraints graphs. A concurrency control mechanism, namely Constraint Based Concurrency Control technique is developed based on the correctness criterion. The performance analysis shows the superiority of the proposed technique. Other possible approaches to the problem are also presented.", 
        "genre": "research_article", 
        "id": "sg:pub.10.1023/a:1008758612291", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": false, 
        "isPartOf": [
          {
            "id": "sg:journal.1136670", 
            "issn": [
              "0926-8782", 
              "1573-7578"
            ], 
            "name": "Distributed and Parallel Databases", 
            "type": "Periodical"
          }, 
          {
            "issueNumber": "2", 
            "type": "PublicationIssue"
          }, 
          {
            "type": "PublicationVolume", 
            "volumeNumber": "7"
          }
        ], 
        "name": "Formalization of Workflows and Correctness Issues in the Presence of Concurrency", 
        "pagination": "199-248", 
        "productId": [
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "735469dd16b5a8f06b7108c8384dfd5f38669adea1f704d712ac7e061d117ac9"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1023/a:1008758612291"
            ]
          }, 
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1024207832"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1023/a:1008758612291", 
          "https://app.dimensions.ai/details/publication/pub.1024207832"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2019-04-10T16:47", 
        "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
        "sdPublisher": {
          "name": "Springer Nature - SN SciGraph project", 
          "type": "Organization"
        }, 
        "sdSource": "s3://com-uberresearch-data-dimensions-target-20181106-alternative/cleanup/v134/2549eaecd7973599484d7c17b260dba0a4ecb94b/merge/v9/a6c9fde33151104705d4d7ff012ea9563521a3ce/jats-lookup/v90/0000000001_0000000264/records_8669_00000536.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "http://link.springer.com/10.1023%2FA%3A1008758612291"
      }
    ]
     

    Download the RDF metadata as:  json-ld nt turtle xml License info

    HOW TO GET THIS DATA PROGRAMMATICALLY:

    JSON-LD is a popular format for linked data which is fully compatible with JSON.

    curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1023/a:1008758612291'

    N-Triples is a line-based linked data format ideal for batch operations.

    curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1023/a:1008758612291'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1023/a:1008758612291'

    RDF/XML is a standard XML format for linked data.

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1023/a:1008758612291'


     

    This table displays all metadata directly associated to this object as RDF triples.

    104 TRIPLES      21 PREDICATES      33 URIs      19 LITERALS      7 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1023/a:1008758612291 schema:about anzsrc-for:08
    2 anzsrc-for:0806
    3 schema:author N0ede29b15f0047ff9c8223dd664b4781
    4 schema:citation sg:pub.10.1007/bf00122147
    5 sg:pub.10.1007/bf01277643
    6 sg:pub.10.1007/bf01277644
    7 sg:pub.10.1023/a:1008604709862
    8 https://doi.org/10.1088/0967-1846/3/4/003
    9 https://doi.org/10.1145/319996.319999
    10 schema:datePublished 1999-04
    11 schema:datePublishedReg 1999-04-01
    12 schema:description In this paper, main components of a workflow system that are relevant to the correctness in the presence of concurrency are formalized based on set theory and graph theory. The formalization which constitutes the theoretical basis of the correctness criterion provided can be summarized as follows: -Activities of a workflow are represented through a notation based on set theory to make it possible to formalize the conceptual grouping of activities. -Control-flow is represented as a special graph based on this set definition, and it includes serial composition, parallel composition, conditional branching, and nesting of individual activities and conceptual activities themselves. -Data-flow is represented as a directed acyclic graph in conformance with the control-flow graph. The formalization of correctness of concurrently executing workflow instances is based on this framework by defining two categories of constraints on the workflow environment with which the workflow instances and their activities interact. These categories are: -Basic constraints that specify the correct states of a workflow environment. -Inter-activity constraints that define the semantic dependencies among activities such as an activity requiring the validity of a constraint that is set or verified by a preceding activity. Basic constraints graph and inter-activity constraints graph which are in conformance with the control-flow and data-flow graphs are then defined to represent these constraints. These graphs are used in formalizing the intervals among activities where an inter-activity constraint should be maintained and the intervals where a basic constraint remains invalid. A correctness criterion is defined for an interleaved execution of workflow instances using the constraints graphs. A concurrency control mechanism, namely Constraint Based Concurrency Control technique is developed based on the correctness criterion. The performance analysis shows the superiority of the proposed technique. Other possible approaches to the problem are also presented.
    13 schema:genre research_article
    14 schema:inLanguage en
    15 schema:isAccessibleForFree false
    16 schema:isPartOf N01ecbeb08ffa49ffbd52a3618790ce1a
    17 N771aa012a64e4bf29f51e9715b4f1b25
    18 sg:journal.1136670
    19 schema:name Formalization of Workflows and Correctness Issues in the Presence of Concurrency
    20 schema:pagination 199-248
    21 schema:productId N67288eb139c4456c8b2815b83ca9c66e
    22 N708e4189f08c4c57a729bc32cc409b10
    23 Nfeba9b93a86b4aaaa98dd91181262782
    24 schema:sameAs https://app.dimensions.ai/details/publication/pub.1024207832
    25 https://doi.org/10.1023/a:1008758612291
    26 schema:sdDatePublished 2019-04-10T16:47
    27 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    28 schema:sdPublisher Nc2c04756833e40d987a47be6cf019503
    29 schema:url http://link.springer.com/10.1023%2FA%3A1008758612291
    30 sgo:license sg:explorer/license/
    31 sgo:sdDataset articles
    32 rdf:type schema:ScholarlyArticle
    33 N01ecbeb08ffa49ffbd52a3618790ce1a schema:issueNumber 2
    34 rdf:type schema:PublicationIssue
    35 N05a6753a1f03497d8b94c35a780e116c rdf:first sg:person.01074167140.73
    36 rdf:rest rdf:nil
    37 N0ede29b15f0047ff9c8223dd664b4781 rdf:first sg:person.015106543057.92
    38 rdf:rest Nca0c5bd516cf4333b040be2cb491eaec
    39 N560b60cdab6440529ba1ac1f841a1e27 rdf:first sg:person.07721402144.55
    40 rdf:rest N05a6753a1f03497d8b94c35a780e116c
    41 N67288eb139c4456c8b2815b83ca9c66e schema:name readcube_id
    42 schema:value 735469dd16b5a8f06b7108c8384dfd5f38669adea1f704d712ac7e061d117ac9
    43 rdf:type schema:PropertyValue
    44 N708e4189f08c4c57a729bc32cc409b10 schema:name doi
    45 schema:value 10.1023/a:1008758612291
    46 rdf:type schema:PropertyValue
    47 N771aa012a64e4bf29f51e9715b4f1b25 schema:volumeNumber 7
    48 rdf:type schema:PublicationVolume
    49 Nc2c04756833e40d987a47be6cf019503 schema:name Springer Nature - SN SciGraph project
    50 rdf:type schema:Organization
    51 Nca0c5bd516cf4333b040be2cb491eaec rdf:first sg:person.012470124473.98
    52 rdf:rest N560b60cdab6440529ba1ac1f841a1e27
    53 Nfeba9b93a86b4aaaa98dd91181262782 schema:name dimensions_id
    54 schema:value pub.1024207832
    55 rdf:type schema:PropertyValue
    56 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    57 schema:name Information and Computing Sciences
    58 rdf:type schema:DefinedTerm
    59 anzsrc-for:0806 schema:inDefinedTermSet anzsrc-for:
    60 schema:name Information Systems
    61 rdf:type schema:DefinedTerm
    62 sg:journal.1136670 schema:issn 0926-8782
    63 1573-7578
    64 schema:name Distributed and Parallel Databases
    65 rdf:type schema:Periodical
    66 sg:person.01074167140.73 schema:affiliation https://www.grid.ac/institutes/grid.6935.9
    67 schema:familyName DoĞaÇ
    68 schema:givenName Asuman
    69 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01074167140.73
    70 rdf:type schema:Person
    71 sg:person.012470124473.98 schema:affiliation https://www.grid.ac/institutes/grid.6935.9
    72 schema:familyName Halici
    73 schema:givenName UĞur
    74 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012470124473.98
    75 rdf:type schema:Person
    76 sg:person.015106543057.92 schema:affiliation https://www.grid.ac/institutes/grid.6935.9
    77 schema:familyName Arpinar
    78 schema:givenName ÏsmaÏlcem Budak
    79 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015106543057.92
    80 rdf:type schema:Person
    81 sg:person.07721402144.55 schema:affiliation https://www.grid.ac/institutes/grid.6935.9
    82 schema:familyName Arpinar
    83 schema:givenName Sena
    84 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07721402144.55
    85 rdf:type schema:Person
    86 sg:pub.10.1007/bf00122147 schema:sameAs https://app.dimensions.ai/details/publication/pub.1020871365
    87 https://doi.org/10.1007/bf00122147
    88 rdf:type schema:CreativeWork
    89 sg:pub.10.1007/bf01277643 schema:sameAs https://app.dimensions.ai/details/publication/pub.1019738307
    90 https://doi.org/10.1007/bf01277643
    91 rdf:type schema:CreativeWork
    92 sg:pub.10.1007/bf01277644 schema:sameAs https://app.dimensions.ai/details/publication/pub.1004226782
    93 https://doi.org/10.1007/bf01277644
    94 rdf:type schema:CreativeWork
    95 sg:pub.10.1023/a:1008604709862 schema:sameAs https://app.dimensions.ai/details/publication/pub.1023335759
    96 https://doi.org/10.1023/a:1008604709862
    97 rdf:type schema:CreativeWork
    98 https://doi.org/10.1088/0967-1846/3/4/003 schema:sameAs https://app.dimensions.ai/details/publication/pub.1059121860
    99 rdf:type schema:CreativeWork
    100 https://doi.org/10.1145/319996.319999 schema:sameAs https://app.dimensions.ai/details/publication/pub.1038103660
    101 rdf:type schema:CreativeWork
    102 https://www.grid.ac/institutes/grid.6935.9 schema:alternateName Middle East Technical University
    103 schema:name Software Research and Development Center, Department of Computer Engineering, Middle East Technical University (METU), 06531, Ankara, Turkey
    104 rdf:type schema:Organization
     




    Preview window. Press ESC to close (or click here)


    ...