A family of NP-complete data aggregation problems View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

1989-03

AUTHORS

Paul Helman

ABSTRACT

We consider a family of general aggregation problems and prove each of its members to be NP-complete in the strong sense. These problems require that we partition a set of objects into “aggregates”. The goal is to minimize the expected cost of satisfying an anticipated collection of requests for subsets of the objects, where the cost of satisfying a request includes both the number and the sizes of the aggregates which must be retrieved. The aggregation problems are viewed as very basic versions of important database optimization problems, including: the partitioning of data items into record types, the clustering of records into physical blocks of storage, and the partitioning of a database into granules to support locking. The NP-completeness results demonstrate that such optimization problems are intractable, even when simplified to the extreme. The fact that the problems are NP-complete in the strong sense also rules out pseudopolynomial time solutions, unless P = NP. More... »

PAGES

485-499

References to SciGraph publications

  • 1988-03. Designing deductive databases in JOURNAL OF AUTOMATED REASONING
  • Identifiers

    URI

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

    DOI

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

    DIMENSIONS

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


    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/0802", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Computation Theory and Mathematics", 
            "type": "DefinedTerm"
          }, 
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0803", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Computer Software", 
            "type": "DefinedTerm"
          }, 
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0804", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Data Format", 
            "type": "DefinedTerm"
          }
        ], 
        "author": [
          {
            "affiliation": {
              "alternateName": "Department of Computer Science, University of New Mexico, 87131, Albuquerque, NM, USA", 
              "id": "http://www.grid.ac/institutes/grid.266832.b", 
              "name": [
                "Department of Computer Science, University of New Mexico, 87131, Albuquerque, NM, USA"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Helman", 
            "givenName": "Paul", 
            "id": "sg:person.01034346234.77", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01034346234.77"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "sg:pub.10.1007/bf00244512", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1010947330", 
              "https://doi.org/10.1007/bf00244512"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "1989-03", 
        "datePublishedReg": "1989-03-01", 
        "description": "We consider a family of general aggregation problems and prove each of its members to be NP-complete in the strong sense. These problems require that we partition a set of objects into \u201caggregates\u201d. The goal is to minimize the expected cost of satisfying an anticipated collection of requests for subsets of the objects, where the cost of satisfying a request includes both the number and the sizes of the aggregates which must be retrieved. The aggregation problems are viewed as very basic versions of important database optimization problems, including: the partitioning of data items into record types, the clustering of records into physical blocks of storage, and the partitioning of a database into granules to support locking. The NP-completeness results demonstrate that such optimization problems are intractable, even when simplified to the extreme. The fact that the problems are NP-complete in the strong sense also rules out pseudopolynomial time solutions, unless P = NP.", 
        "genre": "article", 
        "id": "sg:pub.10.1007/bf00289148", 
        "inLanguage": "en", 
        "isAccessibleForFree": false, 
        "isPartOf": [
          {
            "id": "sg:journal.1133515", 
            "issn": [
              "0001-5903", 
              "1432-0525"
            ], 
            "name": "Acta Informatica", 
            "publisher": "Springer Nature", 
            "type": "Periodical"
          }, 
          {
            "issueNumber": "5", 
            "type": "PublicationIssue"
          }, 
          {
            "type": "PublicationVolume", 
            "volumeNumber": "26"
          }
        ], 
        "keywords": [
          "data aggregation problem", 
          "collection of requests", 
          "aggregation problem", 
          "optimization problem", 
          "set of objects", 
          "such optimization problems", 
          "NP-completeness results", 
          "data items", 
          "record types", 
          "clustering of records", 
          "physical blocks", 
          "basic version", 
          "time solution", 
          "requests", 
          "NPs", 
          "objects", 
          "strong sense", 
          "partitioning", 
          "clustering", 
          "cost", 
          "database", 
          "set", 
          "collection", 
          "version", 
          "goal", 
          "storage", 
          "solution", 
          "block", 
          "sense", 
          "items", 
          "subset", 
          "number", 
          "locking", 
          "records", 
          "results", 
          "fact", 
          "family", 
          "types", 
          "size", 
          "aggregates", 
          "members", 
          "granules", 
          "extremes", 
          "problem"
        ], 
        "name": "A family of NP-complete data aggregation problems", 
        "pagination": "485-499", 
        "productId": [
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1025237166"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/bf00289148"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1007/bf00289148", 
          "https://app.dimensions.ai/details/publication/pub.1025237166"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2022-05-20T07:18", 
        "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
        "sdPublisher": {
          "name": "Springer Nature - SN SciGraph project", 
          "type": "Organization"
        }, 
        "sdSource": "s3://com-springernature-scigraph/baseset/20220519/entities/gbq_results/article/article_185.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "https://doi.org/10.1007/bf00289148"
      }
    ]
     

    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/bf00289148'

    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/bf00289148'

    Turtle is a human-readable linked data format.

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

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

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


     

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

    114 TRIPLES      22 PREDICATES      73 URIs      62 LITERALS      6 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/bf00289148 schema:about anzsrc-for:08
    2 anzsrc-for:0802
    3 anzsrc-for:0803
    4 anzsrc-for:0804
    5 schema:author Nf24d3807024143d39360dac1f82f2040
    6 schema:citation sg:pub.10.1007/bf00244512
    7 schema:datePublished 1989-03
    8 schema:datePublishedReg 1989-03-01
    9 schema:description We consider a family of general aggregation problems and prove each of its members to be NP-complete in the strong sense. These problems require that we partition a set of objects into “aggregates”. The goal is to minimize the expected cost of satisfying an anticipated collection of requests for subsets of the objects, where the cost of satisfying a request includes both the number and the sizes of the aggregates which must be retrieved. The aggregation problems are viewed as very basic versions of important database optimization problems, including: the partitioning of data items into record types, the clustering of records into physical blocks of storage, and the partitioning of a database into granules to support locking. The NP-completeness results demonstrate that such optimization problems are intractable, even when simplified to the extreme. The fact that the problems are NP-complete in the strong sense also rules out pseudopolynomial time solutions, unless P = NP.
    10 schema:genre article
    11 schema:inLanguage en
    12 schema:isAccessibleForFree false
    13 schema:isPartOf N528db0761c1b41a499e5c3c0b3ba4738
    14 Na91cab723a6646e4a208a665e74ef0ca
    15 sg:journal.1133515
    16 schema:keywords NP-completeness results
    17 NPs
    18 aggregates
    19 aggregation problem
    20 basic version
    21 block
    22 clustering
    23 clustering of records
    24 collection
    25 collection of requests
    26 cost
    27 data aggregation problem
    28 data items
    29 database
    30 extremes
    31 fact
    32 family
    33 goal
    34 granules
    35 items
    36 locking
    37 members
    38 number
    39 objects
    40 optimization problem
    41 partitioning
    42 physical blocks
    43 problem
    44 record types
    45 records
    46 requests
    47 results
    48 sense
    49 set
    50 set of objects
    51 size
    52 solution
    53 storage
    54 strong sense
    55 subset
    56 such optimization problems
    57 time solution
    58 types
    59 version
    60 schema:name A family of NP-complete data aggregation problems
    61 schema:pagination 485-499
    62 schema:productId N8139cb7f444643c3988b35bdd41f8ee7
    63 Na9d3e9c0cbd54e1582cd5785f4075551
    64 schema:sameAs https://app.dimensions.ai/details/publication/pub.1025237166
    65 https://doi.org/10.1007/bf00289148
    66 schema:sdDatePublished 2022-05-20T07:18
    67 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    68 schema:sdPublisher N55a4c9b0c98247deb2a44831070e6a30
    69 schema:url https://doi.org/10.1007/bf00289148
    70 sgo:license sg:explorer/license/
    71 sgo:sdDataset articles
    72 rdf:type schema:ScholarlyArticle
    73 N528db0761c1b41a499e5c3c0b3ba4738 schema:volumeNumber 26
    74 rdf:type schema:PublicationVolume
    75 N55a4c9b0c98247deb2a44831070e6a30 schema:name Springer Nature - SN SciGraph project
    76 rdf:type schema:Organization
    77 N8139cb7f444643c3988b35bdd41f8ee7 schema:name dimensions_id
    78 schema:value pub.1025237166
    79 rdf:type schema:PropertyValue
    80 Na91cab723a6646e4a208a665e74ef0ca schema:issueNumber 5
    81 rdf:type schema:PublicationIssue
    82 Na9d3e9c0cbd54e1582cd5785f4075551 schema:name doi
    83 schema:value 10.1007/bf00289148
    84 rdf:type schema:PropertyValue
    85 Nf24d3807024143d39360dac1f82f2040 rdf:first sg:person.01034346234.77
    86 rdf:rest rdf:nil
    87 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    88 schema:name Information and Computing Sciences
    89 rdf:type schema:DefinedTerm
    90 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
    91 schema:name Computation Theory and Mathematics
    92 rdf:type schema:DefinedTerm
    93 anzsrc-for:0803 schema:inDefinedTermSet anzsrc-for:
    94 schema:name Computer Software
    95 rdf:type schema:DefinedTerm
    96 anzsrc-for:0804 schema:inDefinedTermSet anzsrc-for:
    97 schema:name Data Format
    98 rdf:type schema:DefinedTerm
    99 sg:journal.1133515 schema:issn 0001-5903
    100 1432-0525
    101 schema:name Acta Informatica
    102 schema:publisher Springer Nature
    103 rdf:type schema:Periodical
    104 sg:person.01034346234.77 schema:affiliation grid-institutes:grid.266832.b
    105 schema:familyName Helman
    106 schema:givenName Paul
    107 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01034346234.77
    108 rdf:type schema:Person
    109 sg:pub.10.1007/bf00244512 schema:sameAs https://app.dimensions.ai/details/publication/pub.1010947330
    110 https://doi.org/10.1007/bf00244512
    111 rdf:type schema:CreativeWork
    112 grid-institutes:grid.266832.b schema:alternateName Department of Computer Science, University of New Mexico, 87131, Albuquerque, NM, USA
    113 schema:name Department of Computer Science, University of New Mexico, 87131, Albuquerque, NM, USA
    114 rdf:type schema:Organization
     




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


    ...