Searching a minimal semantically-equivalent subset of a set of partial values View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

1993-10

AUTHORS

Frank S. C. Tseng, Arbee L. P. Chen, Wei-Pang Yang

ABSTRACT

Imprecise data exist in databases due to their unavailability or to data/ schema incompatibilities in a multidatabase system. Partial values have been used to represent imprecise data. Manipulation of partial values is therefore necessary to process queries involving imprecise data. In this article, we study the problem of eliminating redundant partial values that result from a projection on an attribute with partial values. The redundancy of partial values is defined through the interpretation of a set of partial values. This problem is equivalent to searching a minimal semantically-equivalent subset of a set of partial values. A semantically-equivalent subset contains exactly the same information as the original set. We derive a set of useful properties and apply a graph matching technique to develop an efficient algorithm for searching such a minimal subset and therefore eliminating redundant partial values. By this process, we not only provide a concise answer to the user, but also reduce the communication cost when partial values are requested to be transmitted from one site to another site in a distributed environment. Moreover, further manipulation of the partial values can be simplified. This work is also extended to the case of multi-attribute projections. More... »

PAGES

489-512

References to SciGraph publications

  • 1991-06. Incomplete deductive databases in ANNALS OF MATHEMATICS AND ARTIFICIAL INTELLIGENCE
  • 1993-07. Answering heterogeneous database queries with degrees of uncertainty in DISTRIBUTED AND PARALLEL DATABASES
  • 1976. Graph Theory with Applications in NONE
  • Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/bf01263049

    DOI

    http://dx.doi.org/10.1007/bf01263049

    DIMENSIONS

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


    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/08", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Information and Computing Sciences", 
            "type": "DefinedTerm"
          }, 
          {
            "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"
          }
        ], 
        "author": [
          {
            "affiliation": {
              "alternateName": "Department of Computer Science and Information Engineering, National Chiao Tung University, 30050, Hsinchu, Taiwan, ROC", 
              "id": "http://www.grid.ac/institutes/grid.260539.b", 
              "name": [
                "Department of Computer Science and Information Engineering, National Chiao Tung University, 30050, Hsinchu, Taiwan, ROC"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Tseng", 
            "givenName": "Frank S. C.", 
            "id": "sg:person.013670725341.44", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013670725341.44"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Department of Computer Science, National Tsing Hua University, 30043, Hsinchu, Taiwan, ROC", 
              "id": "http://www.grid.ac/institutes/grid.38348.34", 
              "name": [
                "Department of Computer Science, National Tsing Hua University, 30043, Hsinchu, Taiwan, ROC"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Chen", 
            "givenName": "Arbee L. P.", 
            "id": "sg:person.011521402733.54", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011521402733.54"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Department of Computer Science and Information Engineering, National Chiao Tung University, 30050, Hsinchu, Taiwan, ROC", 
              "id": "http://www.grid.ac/institutes/grid.260539.b", 
              "name": [
                "Department of Computer Science and Information Engineering, National Chiao Tung University, 30050, Hsinchu, Taiwan, ROC"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Yang", 
            "givenName": "Wei-Pang", 
            "id": "sg:person.014374171260.51", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014374171260.51"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "sg:pub.10.1007/bf01530927", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1016134735", 
              "https://doi.org/10.1007/bf01530927"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-1-349-03521-2", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1109703686", 
              "https://doi.org/10.1007/978-1-349-03521-2"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf01263334", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1041333619", 
              "https://doi.org/10.1007/bf01263334"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "1993-10", 
        "datePublishedReg": "1993-10-01", 
        "description": "Imprecise data exist in databases due to their unavailability or to data/ schema incompatibilities in a multidatabase system. Partial values have been used to represent imprecise data. Manipulation of partial values is therefore necessary to process queries involving imprecise data. In this article, we study the problem of eliminating redundant partial values that result from a projection on an attribute with partial values. The redundancy of partial values is defined through the interpretation of a set of partial values. This problem is equivalent to searching a minimal semantically-equivalent subset of a set of partial values. A semantically-equivalent subset contains exactly the same information as the original set. We derive a set of useful properties and apply a graph matching technique to develop an efficient algorithm for searching such a minimal subset and therefore eliminating redundant partial values. By this process, we not only provide a concise answer to the user, but also reduce the communication cost when partial values are requested to be transmitted from one site to another site in a distributed environment. Moreover, further manipulation of the partial values can be simplified. This work is also extended to the case of multi-attribute projections.", 
        "genre": "article", 
        "id": "sg:pub.10.1007/bf01263049", 
        "inLanguage": "en", 
        "isAccessibleForFree": false, 
        "isPartOf": [
          {
            "id": "sg:journal.1044889", 
            "issn": [
              "1066-8888", 
              "0949-877X"
            ], 
            "name": "The VLDB Journal", 
            "publisher": "Springer Nature", 
            "type": "Periodical"
          }, 
          {
            "issueNumber": "4", 
            "type": "PublicationIssue"
          }, 
          {
            "type": "PublicationVolume", 
            "volumeNumber": "2"
          }
        ], 
        "keywords": [
          "imprecise data", 
          "graph matching techniques", 
          "partial values", 
          "equivalent subsets", 
          "communication cost", 
          "multidatabase systems", 
          "efficient algorithm", 
          "matching technique", 
          "minimal subset", 
          "concise answer", 
          "same information", 
          "original set", 
          "set", 
          "queries", 
          "users", 
          "algorithm", 
          "redundancy", 
          "useful properties", 
          "database", 
          "information", 
          "attributes", 
          "subset", 
          "data", 
          "environment", 
          "unavailability", 
          "cost", 
          "system", 
          "projections", 
          "manipulation", 
          "technique", 
          "answers", 
          "work", 
          "process", 
          "further manipulation", 
          "article", 
          "values", 
          "incompatibility", 
          "interpretation", 
          "cases", 
          "properties", 
          "sites", 
          "problem"
        ], 
        "name": "Searching a minimal semantically-equivalent subset of a set of partial values", 
        "pagination": "489-512", 
        "productId": [
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1004849095"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/bf01263049"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1007/bf01263049", 
          "https://app.dimensions.ai/details/publication/pub.1004849095"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2022-05-10T09:43", 
        "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
        "sdPublisher": {
          "name": "Springer Nature - SN SciGraph project", 
          "type": "Organization"
        }, 
        "sdSource": "s3://com-springernature-scigraph/baseset/20220509/entities/gbq_results/article/article_218.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "https://doi.org/10.1007/bf01263049"
      }
    ]
     

    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.1007/bf01263049'

    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.1007/bf01263049'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/bf01263049'

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

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/bf01263049'


     

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

    129 TRIPLES      22 PREDICATES      70 URIs      59 LITERALS      6 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/bf01263049 schema:about anzsrc-for:08
    2 anzsrc-for:0806
    3 schema:author N2f306d3a7bcb4fc68f53f2d2a2daf441
    4 schema:citation sg:pub.10.1007/978-1-349-03521-2
    5 sg:pub.10.1007/bf01263334
    6 sg:pub.10.1007/bf01530927
    7 schema:datePublished 1993-10
    8 schema:datePublishedReg 1993-10-01
    9 schema:description Imprecise data exist in databases due to their unavailability or to data/ schema incompatibilities in a multidatabase system. Partial values have been used to represent imprecise data. Manipulation of partial values is therefore necessary to process queries involving imprecise data. In this article, we study the problem of eliminating redundant partial values that result from a projection on an attribute with partial values. The redundancy of partial values is defined through the interpretation of a set of partial values. This problem is equivalent to searching a minimal semantically-equivalent subset of a set of partial values. A semantically-equivalent subset contains exactly the same information as the original set. We derive a set of useful properties and apply a graph matching technique to develop an efficient algorithm for searching such a minimal subset and therefore eliminating redundant partial values. By this process, we not only provide a concise answer to the user, but also reduce the communication cost when partial values are requested to be transmitted from one site to another site in a distributed environment. Moreover, further manipulation of the partial values can be simplified. This work is also extended to the case of multi-attribute projections.
    10 schema:genre article
    11 schema:inLanguage en
    12 schema:isAccessibleForFree false
    13 schema:isPartOf Nbc5c090888214fe49457f90ee4fdca25
    14 Nd0a123c28b794f3ca1156497d11b371e
    15 sg:journal.1044889
    16 schema:keywords algorithm
    17 answers
    18 article
    19 attributes
    20 cases
    21 communication cost
    22 concise answer
    23 cost
    24 data
    25 database
    26 efficient algorithm
    27 environment
    28 equivalent subsets
    29 further manipulation
    30 graph matching techniques
    31 imprecise data
    32 incompatibility
    33 information
    34 interpretation
    35 manipulation
    36 matching technique
    37 minimal subset
    38 multidatabase systems
    39 original set
    40 partial values
    41 problem
    42 process
    43 projections
    44 properties
    45 queries
    46 redundancy
    47 same information
    48 set
    49 sites
    50 subset
    51 system
    52 technique
    53 unavailability
    54 useful properties
    55 users
    56 values
    57 work
    58 schema:name Searching a minimal semantically-equivalent subset of a set of partial values
    59 schema:pagination 489-512
    60 schema:productId N706cbb41173a4dbab5ad4f67156e40bb
    61 Nc026bb46026c45d8a0512e95fec0160d
    62 schema:sameAs https://app.dimensions.ai/details/publication/pub.1004849095
    63 https://doi.org/10.1007/bf01263049
    64 schema:sdDatePublished 2022-05-10T09:43
    65 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    66 schema:sdPublisher N49fba9459347484cbc2633b5cc0eec7d
    67 schema:url https://doi.org/10.1007/bf01263049
    68 sgo:license sg:explorer/license/
    69 sgo:sdDataset articles
    70 rdf:type schema:ScholarlyArticle
    71 N2f306d3a7bcb4fc68f53f2d2a2daf441 rdf:first sg:person.013670725341.44
    72 rdf:rest Ncb1f2c32481e4711808a40e91e131fc0
    73 N49fba9459347484cbc2633b5cc0eec7d schema:name Springer Nature - SN SciGraph project
    74 rdf:type schema:Organization
    75 N706cbb41173a4dbab5ad4f67156e40bb schema:name dimensions_id
    76 schema:value pub.1004849095
    77 rdf:type schema:PropertyValue
    78 Nbc5c090888214fe49457f90ee4fdca25 schema:issueNumber 4
    79 rdf:type schema:PublicationIssue
    80 Nc026bb46026c45d8a0512e95fec0160d schema:name doi
    81 schema:value 10.1007/bf01263049
    82 rdf:type schema:PropertyValue
    83 Ncb1f2c32481e4711808a40e91e131fc0 rdf:first sg:person.011521402733.54
    84 rdf:rest Ncc3d8ddd4e99470a93297a65aff72fe6
    85 Ncc3d8ddd4e99470a93297a65aff72fe6 rdf:first sg:person.014374171260.51
    86 rdf:rest rdf:nil
    87 Nd0a123c28b794f3ca1156497d11b371e schema:volumeNumber 2
    88 rdf:type schema:PublicationVolume
    89 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    90 schema:name Information and Computing Sciences
    91 rdf:type schema:DefinedTerm
    92 anzsrc-for:0806 schema:inDefinedTermSet anzsrc-for:
    93 schema:name Information Systems
    94 rdf:type schema:DefinedTerm
    95 sg:journal.1044889 schema:issn 0949-877X
    96 1066-8888
    97 schema:name The VLDB Journal
    98 schema:publisher Springer Nature
    99 rdf:type schema:Periodical
    100 sg:person.011521402733.54 schema:affiliation grid-institutes:grid.38348.34
    101 schema:familyName Chen
    102 schema:givenName Arbee L. P.
    103 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011521402733.54
    104 rdf:type schema:Person
    105 sg:person.013670725341.44 schema:affiliation grid-institutes:grid.260539.b
    106 schema:familyName Tseng
    107 schema:givenName Frank S. C.
    108 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013670725341.44
    109 rdf:type schema:Person
    110 sg:person.014374171260.51 schema:affiliation grid-institutes:grid.260539.b
    111 schema:familyName Yang
    112 schema:givenName Wei-Pang
    113 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014374171260.51
    114 rdf:type schema:Person
    115 sg:pub.10.1007/978-1-349-03521-2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1109703686
    116 https://doi.org/10.1007/978-1-349-03521-2
    117 rdf:type schema:CreativeWork
    118 sg:pub.10.1007/bf01263334 schema:sameAs https://app.dimensions.ai/details/publication/pub.1041333619
    119 https://doi.org/10.1007/bf01263334
    120 rdf:type schema:CreativeWork
    121 sg:pub.10.1007/bf01530927 schema:sameAs https://app.dimensions.ai/details/publication/pub.1016134735
    122 https://doi.org/10.1007/bf01530927
    123 rdf:type schema:CreativeWork
    124 grid-institutes:grid.260539.b schema:alternateName Department of Computer Science and Information Engineering, National Chiao Tung University, 30050, Hsinchu, Taiwan, ROC
    125 schema:name Department of Computer Science and Information Engineering, National Chiao Tung University, 30050, Hsinchu, Taiwan, ROC
    126 rdf:type schema:Organization
    127 grid-institutes:grid.38348.34 schema:alternateName Department of Computer Science, National Tsing Hua University, 30043, Hsinchu, Taiwan, ROC
    128 schema:name Department of Computer Science, National Tsing Hua University, 30043, Hsinchu, Taiwan, ROC
    129 rdf:type schema:Organization
     




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


    ...