DBA*: Solving Combinatorial Problems with Deductive Databases View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

1989

AUTHORS

Helmut Schmidt , Werner Kiessling , Ulrich Güntzer , Rudolf Bayer

ABSTRACT

The evolution of database (DB) technology, with its origins in hierarchical databases, has currently reached the stage of matured relational DB systems and is about to grow into deductive DB systems, where logic programming — originated by the artificial intelligence (AI) community — plays a central theoretical role. Until now, however, no smooth integration of another important part of AI, namely that of heuristic search and intelligent planning, into DB technology was known. This paper contributes a first step beyond deductive DB systems towards intelligent DB systems. We describe the well-known A*-algorithm in terms of a general theoretical framework for deductive DB systems, the sloppy deltaiteration scheme, and give a generalized algorithm, called DBA*-algorithm. As an immediate consequence, heuristic search strategies for combinatorial problems become now feasible in the DB environment in a natural and efficient way. We also present a prototype implementation of the DBA*-algorithm, with the 15-Puzzle and the Traveling Salesman Problem as sample combinatorial problems. The benchmark results gained from this testbed demonstrate the applicability and efficiency of our approach for heuristic search in deductive DB systems. More... »

PAGES

196-215

References to SciGraph publications

  • 1985. Database Technology for Expert Systems in WISSENSBASIERTE SYSTEME
  • 1986. Naive Evaluation of Recursively Defined Relations in ON KNOWLEDGE BASE MANAGEMENT SYSTEMS
  • 1987. Foundations of Logic Programming in NONE
  • Book

    TITLE

    Datenbanksysteme in Büro, Technik und Wissenschaft

    ISBN

    978-3-540-50894-6
    978-3-642-74571-3

    Author Affiliations

    Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/978-3-642-74571-3_16

    DOI

    http://dx.doi.org/10.1007/978-3-642-74571-3_16

    DIMENSIONS

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


    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/0801", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Artificial Intelligence and Image Processing", 
            "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": {
              "name": [
                "MAD Intelligent Systems GmbH, Prinzregentenplatz 10, D-8000\u00a0M\u00fcnchen 80, Deutschland"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Schmidt", 
            "givenName": "Helmut", 
            "id": "sg:person.015162601146.82", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015162601146.82"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "name": [
                "MAD Intelligent Systems GmbH, Prinzregentenplatz 10, D-8000\u00a0M\u00fcnchen 80, Deutschland"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Kiessling", 
            "givenName": "Werner", 
            "id": "sg:person.07355710125.73", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07355710125.73"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Technical University Munich", 
              "id": "https://www.grid.ac/institutes/grid.6936.a", 
              "name": [
                "Institut f\u00fcr Informatik, Technische Universit\u00e4t M\u00fcnchen, Arcisstrasse 21, D-8000\u00a0M\u00fcnchen 2, Deutschland"
              ], 
              "type": "Organization"
            }, 
            "familyName": "G\u00fcntzer", 
            "givenName": "Ulrich", 
            "id": "sg:person.013324511711.75", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013324511711.75"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Technical University Munich", 
              "id": "https://www.grid.ac/institutes/grid.6936.a", 
              "name": [
                "Institut f\u00fcr Informatik, Technische Universit\u00e4t M\u00fcnchen, Arcisstrasse 21, D-8000\u00a0M\u00fcnchen 2, Deutschland"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Bayer", 
            "givenName": "Rudolf", 
            "id": "sg:person.010052470746.96", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010052470746.96"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "sg:pub.10.1007/978-3-642-70840-4_1", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1000114058", 
              "https://doi.org/10.1007/978-3-642-70840-4_1"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/3979.3980", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1000409090"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-83189-8", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1016029570", 
              "https://doi.org/10.1007/978-3-642-83189-8"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-83189-8", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1016029570", 
              "https://doi.org/10.1007/978-3-642-83189-8"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0004-3702(85)90084-0", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1030400469"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0004-3702(85)90084-0", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1030400469"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0743-1066(87)90004-5", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1032090701"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-1-4612-4980-1_17", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1034223670", 
              "https://doi.org/10.1007/978-1-4612-4980-1_17"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-1-4612-4980-1_17", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1034223670", 
              "https://doi.org/10.1007/978-1-4612-4980-1_17"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/321978.321991", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1042730246"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "1989", 
        "datePublishedReg": "1989-01-01", 
        "description": "The evolution of database (DB) technology, with its origins in hierarchical databases, has currently reached the stage of matured relational DB systems and is about to grow into deductive DB systems, where logic programming \u2014 originated by the artificial intelligence (AI) community \u2014 plays a central theoretical role. Until now, however, no smooth integration of another important part of AI, namely that of heuristic search and intelligent planning, into DB technology was known. This paper contributes a first step beyond deductive DB systems towards intelligent DB systems. We describe the well-known A*-algorithm in terms of a general theoretical framework for deductive DB systems, the sloppy deltaiteration scheme, and give a generalized algorithm, called DBA*-algorithm. As an immediate consequence, heuristic search strategies for combinatorial problems become now feasible in the DB environment in a natural and efficient way. We also present a prototype implementation of the DBA*-algorithm, with the 15-Puzzle and the Traveling Salesman Problem as sample combinatorial problems. The benchmark results gained from this testbed demonstrate the applicability and efficiency of our approach for heuristic search in deductive DB systems.", 
        "editor": [
          {
            "familyName": "H\u00e4rder", 
            "givenName": "Theo", 
            "type": "Person"
          }
        ], 
        "genre": "chapter", 
        "id": "sg:pub.10.1007/978-3-642-74571-3_16", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": false, 
        "isPartOf": {
          "isbn": [
            "978-3-540-50894-6", 
            "978-3-642-74571-3"
          ], 
          "name": "Datenbanksysteme in B\u00fcro, Technik und Wissenschaft", 
          "type": "Book"
        }, 
        "name": "DBA*: Solving Combinatorial Problems with Deductive Databases", 
        "pagination": "196-215", 
        "productId": [
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/978-3-642-74571-3_16"
            ]
          }, 
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "e6eb59e8d3ad0d38b187d615546c74d8eee920372c02227be82b89532885bb2a"
            ]
          }, 
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1048473545"
            ]
          }
        ], 
        "publisher": {
          "location": "Berlin, Heidelberg", 
          "name": "Springer Berlin Heidelberg", 
          "type": "Organisation"
        }, 
        "sameAs": [
          "https://doi.org/10.1007/978-3-642-74571-3_16", 
          "https://app.dimensions.ai/details/publication/pub.1048473545"
        ], 
        "sdDataset": "chapters", 
        "sdDatePublished": "2019-04-15T22:01", 
        "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_8693_00000273.jsonl", 
        "type": "Chapter", 
        "url": "http://link.springer.com/10.1007/978-3-642-74571-3_16"
      }
    ]
     

    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/978-3-642-74571-3_16'

    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/978-3-642-74571-3_16'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-74571-3_16'

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

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-74571-3_16'


     

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

    114 TRIPLES      23 PREDICATES      34 URIs      20 LITERALS      8 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/978-3-642-74571-3_16 schema:about anzsrc-for:08
    2 anzsrc-for:0801
    3 schema:author N27c360dccc60427f9d4f8da15d6d4c1f
    4 schema:citation sg:pub.10.1007/978-1-4612-4980-1_17
    5 sg:pub.10.1007/978-3-642-70840-4_1
    6 sg:pub.10.1007/978-3-642-83189-8
    7 https://doi.org/10.1016/0004-3702(85)90084-0
    8 https://doi.org/10.1016/0743-1066(87)90004-5
    9 https://doi.org/10.1145/321978.321991
    10 https://doi.org/10.1145/3979.3980
    11 schema:datePublished 1989
    12 schema:datePublishedReg 1989-01-01
    13 schema:description The evolution of database (DB) technology, with its origins in hierarchical databases, has currently reached the stage of matured relational DB systems and is about to grow into deductive DB systems, where logic programming — originated by the artificial intelligence (AI) community — plays a central theoretical role. Until now, however, no smooth integration of another important part of AI, namely that of heuristic search and intelligent planning, into DB technology was known. This paper contributes a first step beyond deductive DB systems towards intelligent DB systems. We describe the well-known A*-algorithm in terms of a general theoretical framework for deductive DB systems, the sloppy deltaiteration scheme, and give a generalized algorithm, called DBA*-algorithm. As an immediate consequence, heuristic search strategies for combinatorial problems become now feasible in the DB environment in a natural and efficient way. We also present a prototype implementation of the DBA*-algorithm, with the 15-Puzzle and the Traveling Salesman Problem as sample combinatorial problems. The benchmark results gained from this testbed demonstrate the applicability and efficiency of our approach for heuristic search in deductive DB systems.
    14 schema:editor N95f7ca25b2d14e4a8f961c6c6cbf42d2
    15 schema:genre chapter
    16 schema:inLanguage en
    17 schema:isAccessibleForFree false
    18 schema:isPartOf Nf5461ebbb9af416d83b52491cbfa33c6
    19 schema:name DBA*: Solving Combinatorial Problems with Deductive Databases
    20 schema:pagination 196-215
    21 schema:productId N744010214e004c1f9efea773ac542fe9
    22 N9b66b63121984a3ca3897e1063600a76
    23 Nb6a249f886d4484a95c6bbb6494109aa
    24 schema:publisher N19370d015fa94caba18370e460e6adf0
    25 schema:sameAs https://app.dimensions.ai/details/publication/pub.1048473545
    26 https://doi.org/10.1007/978-3-642-74571-3_16
    27 schema:sdDatePublished 2019-04-15T22:01
    28 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    29 schema:sdPublisher Ne38955e3e4894c6c80f18d403b582770
    30 schema:url http://link.springer.com/10.1007/978-3-642-74571-3_16
    31 sgo:license sg:explorer/license/
    32 sgo:sdDataset chapters
    33 rdf:type schema:Chapter
    34 N19370d015fa94caba18370e460e6adf0 schema:location Berlin, Heidelberg
    35 schema:name Springer Berlin Heidelberg
    36 rdf:type schema:Organisation
    37 N1fed5cc7980e438cbc603bcfa694596b schema:name MAD Intelligent Systems GmbH, Prinzregentenplatz 10, D-8000 München 80, Deutschland
    38 rdf:type schema:Organization
    39 N27c360dccc60427f9d4f8da15d6d4c1f rdf:first sg:person.015162601146.82
    40 rdf:rest N76fd25615c0049438929cd56089e35b0
    41 N525bfc3dcfbe435ea2a28a88b7d41914 rdf:first sg:person.013324511711.75
    42 rdf:rest N8f501136cbea4013bcfb43ca4ecf3615
    43 N744010214e004c1f9efea773ac542fe9 schema:name readcube_id
    44 schema:value e6eb59e8d3ad0d38b187d615546c74d8eee920372c02227be82b89532885bb2a
    45 rdf:type schema:PropertyValue
    46 N76fd25615c0049438929cd56089e35b0 rdf:first sg:person.07355710125.73
    47 rdf:rest N525bfc3dcfbe435ea2a28a88b7d41914
    48 N7c5222ee9833477cb67329d19a472f2e schema:familyName Härder
    49 schema:givenName Theo
    50 rdf:type schema:Person
    51 N8f501136cbea4013bcfb43ca4ecf3615 rdf:first sg:person.010052470746.96
    52 rdf:rest rdf:nil
    53 N95f7ca25b2d14e4a8f961c6c6cbf42d2 rdf:first N7c5222ee9833477cb67329d19a472f2e
    54 rdf:rest rdf:nil
    55 N9b66b63121984a3ca3897e1063600a76 schema:name doi
    56 schema:value 10.1007/978-3-642-74571-3_16
    57 rdf:type schema:PropertyValue
    58 Nb6a249f886d4484a95c6bbb6494109aa schema:name dimensions_id
    59 schema:value pub.1048473545
    60 rdf:type schema:PropertyValue
    61 Nc9e15b1a104548aa941310a83f075fe6 schema:name MAD Intelligent Systems GmbH, Prinzregentenplatz 10, D-8000 München 80, Deutschland
    62 rdf:type schema:Organization
    63 Ne38955e3e4894c6c80f18d403b582770 schema:name Springer Nature - SN SciGraph project
    64 rdf:type schema:Organization
    65 Nf5461ebbb9af416d83b52491cbfa33c6 schema:isbn 978-3-540-50894-6
    66 978-3-642-74571-3
    67 schema:name Datenbanksysteme in Büro, Technik und Wissenschaft
    68 rdf:type schema:Book
    69 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    70 schema:name Information and Computing Sciences
    71 rdf:type schema:DefinedTerm
    72 anzsrc-for:0801 schema:inDefinedTermSet anzsrc-for:
    73 schema:name Artificial Intelligence and Image Processing
    74 rdf:type schema:DefinedTerm
    75 sg:person.010052470746.96 schema:affiliation https://www.grid.ac/institutes/grid.6936.a
    76 schema:familyName Bayer
    77 schema:givenName Rudolf
    78 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010052470746.96
    79 rdf:type schema:Person
    80 sg:person.013324511711.75 schema:affiliation https://www.grid.ac/institutes/grid.6936.a
    81 schema:familyName Güntzer
    82 schema:givenName Ulrich
    83 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013324511711.75
    84 rdf:type schema:Person
    85 sg:person.015162601146.82 schema:affiliation Nc9e15b1a104548aa941310a83f075fe6
    86 schema:familyName Schmidt
    87 schema:givenName Helmut
    88 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015162601146.82
    89 rdf:type schema:Person
    90 sg:person.07355710125.73 schema:affiliation N1fed5cc7980e438cbc603bcfa694596b
    91 schema:familyName Kiessling
    92 schema:givenName Werner
    93 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07355710125.73
    94 rdf:type schema:Person
    95 sg:pub.10.1007/978-1-4612-4980-1_17 schema:sameAs https://app.dimensions.ai/details/publication/pub.1034223670
    96 https://doi.org/10.1007/978-1-4612-4980-1_17
    97 rdf:type schema:CreativeWork
    98 sg:pub.10.1007/978-3-642-70840-4_1 schema:sameAs https://app.dimensions.ai/details/publication/pub.1000114058
    99 https://doi.org/10.1007/978-3-642-70840-4_1
    100 rdf:type schema:CreativeWork
    101 sg:pub.10.1007/978-3-642-83189-8 schema:sameAs https://app.dimensions.ai/details/publication/pub.1016029570
    102 https://doi.org/10.1007/978-3-642-83189-8
    103 rdf:type schema:CreativeWork
    104 https://doi.org/10.1016/0004-3702(85)90084-0 schema:sameAs https://app.dimensions.ai/details/publication/pub.1030400469
    105 rdf:type schema:CreativeWork
    106 https://doi.org/10.1016/0743-1066(87)90004-5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1032090701
    107 rdf:type schema:CreativeWork
    108 https://doi.org/10.1145/321978.321991 schema:sameAs https://app.dimensions.ai/details/publication/pub.1042730246
    109 rdf:type schema:CreativeWork
    110 https://doi.org/10.1145/3979.3980 schema:sameAs https://app.dimensions.ai/details/publication/pub.1000409090
    111 rdf:type schema:CreativeWork
    112 https://www.grid.ac/institutes/grid.6936.a schema:alternateName Technical University Munich
    113 schema:name Institut für Informatik, Technische Universität München, Arcisstrasse 21, D-8000 München 2, Deutschland
    114 rdf:type schema:Organization
     




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


    ...