Query Processing in Embedded Control Programs View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

1999

AUTHORS

David Toman , Grant Weddell

ABSTRACT

An embedded control program can be viewed as a small main-memory database system tailored to suit the needs of a particular application. For performance reasons, the program will usually de- fine concrete low level data structures to encode the database, which in turn must be understood by anyone who needs to develop or modify the program. This is in contrast with the data independence that can be achieved by using a database system. However, because of space and performance requirements, the use of current database technology is not likely to be feasible in this setting. To explore one obstacle to this, we have developed a query optimizer that compiles queries on a conceptual schema to native Java or C code that navigates low level data structures. Of crucial significance is that an arbitrary collection of such structures, perhaps already devised for an earlier version of the control program, can be given as a part of the input to the optimizer. We present an overview of the underlying algorithms that are used to accomplish this. The algorithms are based on a novel resource bounded plan generation mechanism in which integrity constraints abstracting the definition of stored views are applied to source queries to extend the search space of possible query plans. We also report on some preliminary experimental results that suggest generated code navigates concrete data structures with an efficiency comparable to code written directly by expert programmers. More... »

PAGES

68-87

Book

TITLE

Databases in Telecommunications II

ISBN

978-3-540-42623-3
978-3-540-45432-8

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/3-540-45432-2_6

DOI

http://dx.doi.org/10.1007/3-540-45432-2_6

DIMENSIONS

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


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, University of Waterloo, Canada", 
          "id": "http://www.grid.ac/institutes/grid.46078.3d", 
          "name": [
            "Department of Computer Science, University of Waterloo, Canada"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Toman", 
        "givenName": "David", 
        "id": "sg:person.011644611743.11", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011644611743.11"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Computer Science, University of Waterloo, Canada", 
          "id": "http://www.grid.ac/institutes/grid.46078.3d", 
          "name": [
            "Department of Computer Science, University of Waterloo, Canada"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Weddell", 
        "givenName": "Grant", 
        "id": "sg:person.01111756132.29", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01111756132.29"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "1999", 
    "datePublishedReg": "1999-01-01", 
    "description": "An embedded control program can be viewed as a small main-memory database system tailored to suit the needs of a particular application. For performance reasons, the program will usually de- fine concrete low level data structures to encode the database, which in turn must be understood by anyone who needs to develop or modify the program. This is in contrast with the data independence that can be achieved by using a database system. However, because of space and performance requirements, the use of current database technology is not likely to be feasible in this setting. To explore one obstacle to this, we have developed a query optimizer that compiles queries on a conceptual schema to native Java or C code that navigates low level data structures. Of crucial significance is that an arbitrary collection of such structures, perhaps already devised for an earlier version of the control program, can be given as a part of the input to the optimizer. We present an overview of the underlying algorithms that are used to accomplish this. The algorithms are based on a novel resource bounded plan generation mechanism in which integrity constraints abstracting the definition of stored views are applied to source queries to extend the search space of possible query plans. We also report on some preliminary experimental results that suggest generated code navigates concrete data structures with an efficiency comparable to code written directly by expert programmers.", 
    "editor": [
      {
        "familyName": "Jonker", 
        "givenName": "Willem", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/3-540-45432-2_6", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-540-42623-3", 
        "978-3-540-45432-8"
      ], 
      "name": "Databases in Telecommunications II", 
      "type": "Book"
    }, 
    "keywords": [
      "embedded control program", 
      "low level data structures", 
      "level data structures", 
      "data structure", 
      "database systems", 
      "main-memory database systems", 
      "plan generation mechanism", 
      "current database technology", 
      "possible query plans", 
      "concrete data structures", 
      "query processing", 
      "database technology", 
      "query plans", 
      "query optimizer", 
      "data independence", 
      "expert programmers", 
      "native Java", 
      "integrity constraints", 
      "source query", 
      "conceptual schema", 
      "search space", 
      "preliminary experimental results", 
      "performance reasons", 
      "underlying algorithm", 
      "performance requirements", 
      "queries", 
      "arbitrary collection", 
      "algorithm", 
      "experimental results", 
      "particular application", 
      "optimizer", 
      "programmers", 
      "Java", 
      "schema", 
      "earlier version", 
      "novel resource", 
      "system", 
      "code", 
      "space", 
      "constraints", 
      "database", 
      "technology", 
      "requirements", 
      "processing", 
      "resources", 
      "applications", 
      "obstacles", 
      "program", 
      "version", 
      "input", 
      "control programs", 
      "collection", 
      "efficiency", 
      "generation mechanism", 
      "definition", 
      "overview", 
      "need", 
      "crucial significance", 
      "view", 
      "plan", 
      "structure", 
      "such structures", 
      "use", 
      "results", 
      "part", 
      "setting", 
      "independence", 
      "reasons", 
      "turn", 
      "mechanism", 
      "contrast", 
      "significance", 
      "small main-memory database system", 
      "de- fine concrete low level data structures", 
      "concrete low level data structures", 
      "code navigates concrete data structures", 
      "navigates concrete data structures"
    ], 
    "name": "Query Processing in Embedded Control Programs", 
    "pagination": "68-87", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1046138227"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/3-540-45432-2_6"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/3-540-45432-2_6", 
      "https://app.dimensions.ai/details/publication/pub.1046138227"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2021-12-01T20:09", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20211201/entities/gbq_results/chapter/chapter_432.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/3-540-45432-2_6"
  }
]
 

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/3-540-45432-2_6'

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/3-540-45432-2_6'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/3-540-45432-2_6'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/3-540-45432-2_6'


 

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

144 TRIPLES      23 PREDICATES      103 URIs      96 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/3-540-45432-2_6 schema:about anzsrc-for:08
2 anzsrc-for:0806
3 schema:author Nb4af281791ca46459c7df1b2ea30ede9
4 schema:datePublished 1999
5 schema:datePublishedReg 1999-01-01
6 schema:description An embedded control program can be viewed as a small main-memory database system tailored to suit the needs of a particular application. For performance reasons, the program will usually de- fine concrete low level data structures to encode the database, which in turn must be understood by anyone who needs to develop or modify the program. This is in contrast with the data independence that can be achieved by using a database system. However, because of space and performance requirements, the use of current database technology is not likely to be feasible in this setting. To explore one obstacle to this, we have developed a query optimizer that compiles queries on a conceptual schema to native Java or C code that navigates low level data structures. Of crucial significance is that an arbitrary collection of such structures, perhaps already devised for an earlier version of the control program, can be given as a part of the input to the optimizer. We present an overview of the underlying algorithms that are used to accomplish this. The algorithms are based on a novel resource bounded plan generation mechanism in which integrity constraints abstracting the definition of stored views are applied to source queries to extend the search space of possible query plans. We also report on some preliminary experimental results that suggest generated code navigates concrete data structures with an efficiency comparable to code written directly by expert programmers.
7 schema:editor Ncece348307914260869c434507cfd368
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf Ne13a76e73bce484099bc8b16b902e7e6
12 schema:keywords Java
13 algorithm
14 applications
15 arbitrary collection
16 code
17 code navigates concrete data structures
18 collection
19 conceptual schema
20 concrete data structures
21 concrete low level data structures
22 constraints
23 contrast
24 control programs
25 crucial significance
26 current database technology
27 data independence
28 data structure
29 database
30 database systems
31 database technology
32 de- fine concrete low level data structures
33 definition
34 earlier version
35 efficiency
36 embedded control program
37 experimental results
38 expert programmers
39 generation mechanism
40 independence
41 input
42 integrity constraints
43 level data structures
44 low level data structures
45 main-memory database systems
46 mechanism
47 native Java
48 navigates concrete data structures
49 need
50 novel resource
51 obstacles
52 optimizer
53 overview
54 part
55 particular application
56 performance reasons
57 performance requirements
58 plan
59 plan generation mechanism
60 possible query plans
61 preliminary experimental results
62 processing
63 program
64 programmers
65 queries
66 query optimizer
67 query plans
68 query processing
69 reasons
70 requirements
71 resources
72 results
73 schema
74 search space
75 setting
76 significance
77 small main-memory database system
78 source query
79 space
80 structure
81 such structures
82 system
83 technology
84 turn
85 underlying algorithm
86 use
87 version
88 view
89 schema:name Query Processing in Embedded Control Programs
90 schema:pagination 68-87
91 schema:productId N276f1a567683426496ead0ca9dabb5cb
92 N43c5cd7243f14841a72befa4b167a0f0
93 schema:publisher N0b40afb349b948278bf1703b3f63d3ce
94 schema:sameAs https://app.dimensions.ai/details/publication/pub.1046138227
95 https://doi.org/10.1007/3-540-45432-2_6
96 schema:sdDatePublished 2021-12-01T20:09
97 schema:sdLicense https://scigraph.springernature.com/explorer/license/
98 schema:sdPublisher Nd8992b6e397640c2ae81745cecb314c5
99 schema:url https://doi.org/10.1007/3-540-45432-2_6
100 sgo:license sg:explorer/license/
101 sgo:sdDataset chapters
102 rdf:type schema:Chapter
103 N0b40afb349b948278bf1703b3f63d3ce schema:name Springer Nature
104 rdf:type schema:Organisation
105 N276f1a567683426496ead0ca9dabb5cb schema:name dimensions_id
106 schema:value pub.1046138227
107 rdf:type schema:PropertyValue
108 N3838e0e81ed642d4a35806d38b8c7494 schema:familyName Jonker
109 schema:givenName Willem
110 rdf:type schema:Person
111 N43c5cd7243f14841a72befa4b167a0f0 schema:name doi
112 schema:value 10.1007/3-540-45432-2_6
113 rdf:type schema:PropertyValue
114 N8ba3f2c69dba4692a3220759c71c12f0 rdf:first sg:person.01111756132.29
115 rdf:rest rdf:nil
116 Nb4af281791ca46459c7df1b2ea30ede9 rdf:first sg:person.011644611743.11
117 rdf:rest N8ba3f2c69dba4692a3220759c71c12f0
118 Ncece348307914260869c434507cfd368 rdf:first N3838e0e81ed642d4a35806d38b8c7494
119 rdf:rest rdf:nil
120 Nd8992b6e397640c2ae81745cecb314c5 schema:name Springer Nature - SN SciGraph project
121 rdf:type schema:Organization
122 Ne13a76e73bce484099bc8b16b902e7e6 schema:isbn 978-3-540-42623-3
123 978-3-540-45432-8
124 schema:name Databases in Telecommunications II
125 rdf:type schema:Book
126 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
127 schema:name Information and Computing Sciences
128 rdf:type schema:DefinedTerm
129 anzsrc-for:0806 schema:inDefinedTermSet anzsrc-for:
130 schema:name Information Systems
131 rdf:type schema:DefinedTerm
132 sg:person.01111756132.29 schema:affiliation grid-institutes:grid.46078.3d
133 schema:familyName Weddell
134 schema:givenName Grant
135 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01111756132.29
136 rdf:type schema:Person
137 sg:person.011644611743.11 schema:affiliation grid-institutes:grid.46078.3d
138 schema:familyName Toman
139 schema:givenName David
140 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011644611743.11
141 rdf:type schema:Person
142 grid-institutes:grid.46078.3d schema:alternateName Department of Computer Science, University of Waterloo, Canada
143 schema:name Department of Computer Science, University of Waterloo, Canada
144 rdf:type schema:Organization
 




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


...