A logic for rule-based query optimization in graph-based data models View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

1993

AUTHORS

Neil Coburn , Grant E. Weddell

ABSTRACT

We present a wide-spectrum algebra and refinement calculus designed to allow one to reason about query optimization in graph-based data models.A query language is wide-spectrum if it can be used to express both user level queries as well as low-level evaluation strategies or access plans. This property enables rule-based query optimization to be viewed as the process of refining expressions in such a language: “non-procedural” sub-expressions are gradually replaced by more “procedural” sub-expressions until an unambiguous access plan results. We begin by presenting an algebra that is wide-spectrum in this sense. One subset of operations within the algebra can be used to define the formal semantics of a non-procedural query language for graph-based data models. Another subset can express common data access paradigms such as an index scan, the “cut” operator in Prolog or the nested-iteration join processing strategy.We then present a refinement calculus over the algebra which defines when one algebraic expression subsumes another. The calculus makes it possible to formally prove the correctness of rewrite rules used in rule-based query optimizers, and is sufficiently expressive to admit rules encoding many forms of semantic query optimization. More... »

PAGES

120-145

Book

TITLE

Deductive and Object-Oriented Databases

ISBN

978-3-540-57530-6
978-3-540-48212-3

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/3-540-57530-8_8

DOI

http://dx.doi.org/10.1007/3-540-57530-8_8

DIMENSIONS

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


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, UK", 
          "id": "http://www.grid.ac/institutes/None", 
          "name": [
            "Department of Computer Science, University of Waterloo, UK"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Coburn", 
        "givenName": "Neil", 
        "id": "sg:person.015614722063.65", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015614722063.65"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Computer Science, University of Waterloo, UK", 
          "id": "http://www.grid.ac/institutes/None", 
          "name": [
            "Department of Computer Science, University of Waterloo, UK"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Weddell", 
        "givenName": "Grant E.", 
        "id": "sg:person.01111756132.29", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01111756132.29"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "1993", 
    "datePublishedReg": "1993-01-01", 
    "description": "We present a wide-spectrum algebra and refinement calculus designed to allow one to reason about query optimization in graph-based data models.A query language is wide-spectrum if it can be used to express both user level queries as well as low-level evaluation strategies or access plans. This property enables rule-based query optimization to be viewed as the process of refining expressions in such a language: \u201cnon-procedural\u201d sub-expressions are gradually replaced by more \u201cprocedural\u201d sub-expressions until an unambiguous access plan results. We begin by presenting an algebra that is wide-spectrum in this sense. One subset of operations within the algebra can be used to define the formal semantics of a non-procedural query language for graph-based data models. Another subset can express common data access paradigms such as an index scan, the \u201ccut\u201d operator in Prolog or the nested-iteration join processing strategy.We then present a refinement calculus over the algebra which defines when one algebraic expression subsumes another. The calculus makes it possible to formally prove the correctness of rewrite rules used in rule-based query optimizers, and is sufficiently expressive to admit rules encoding many forms of semantic query optimization.", 
    "editor": [
      {
        "familyName": "Ceri", 
        "givenName": "Stefano", 
        "type": "Person"
      }, 
      {
        "familyName": "Tanaka", 
        "givenName": "Katsumi", 
        "type": "Person"
      }, 
      {
        "familyName": "Tsur", 
        "givenName": "Shalom", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/3-540-57530-8_8", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-540-57530-6", 
        "978-3-540-48212-3"
      ], 
      "name": "Deductive and Object-Oriented Databases", 
      "type": "Book"
    }, 
    "keywords": [
      "graph-based data model", 
      "rule-based query optimization", 
      "query optimization", 
      "data model", 
      "query language", 
      "rule-based query optimizer", 
      "refinement calculus", 
      "non-procedural query languages", 
      "data access paradigm", 
      "semantic query optimization", 
      "level queries", 
      "query optimizer", 
      "subset of operations", 
      "formal semantics", 
      "index scan", 
      "rewrite rules", 
      "access paradigm", 
      "access plan", 
      "plan results", 
      "language", 
      "evaluation strategies", 
      "optimization", 
      "processing strategies", 
      "queries", 
      "semantics", 
      "Prolog", 
      "rules", 
      "correctness", 
      "algebraic expressions", 
      "optimizer", 
      "calculus", 
      "logic", 
      "paradigm", 
      "model", 
      "operators", 
      "algebra", 
      "operation", 
      "subset", 
      "strategies", 
      "plan", 
      "process", 
      "sense", 
      "results", 
      "reasons", 
      "cut", 
      "scans", 
      "form", 
      "properties", 
      "expression", 
      "wide-spectrum algebra", 
      "user level queries", 
      "low-level evaluation strategies", 
      "refining expressions", 
      "unambiguous access plan results", 
      "access plan results", 
      "common data access paradigms", 
      "nested-iteration join processing strategy", 
      "join processing strategy"
    ], 
    "name": "A logic for rule-based query optimization in graph-based data models", 
    "pagination": "120-145", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1052689766"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/3-540-57530-8_8"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/3-540-57530-8_8", 
      "https://app.dimensions.ai/details/publication/pub.1052689766"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-01-01T19:17", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220101/entities/gbq_results/chapter/chapter_299.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/3-540-57530-8_8"
  }
]
 

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-57530-8_8'

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-57530-8_8'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/3-540-57530-8_8'

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-57530-8_8'


 

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

135 TRIPLES      23 PREDICATES      84 URIs      77 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/3-540-57530-8_8 schema:about anzsrc-for:08
2 anzsrc-for:0806
3 schema:author Na9caa222b077450b93c5a01fc96ee053
4 schema:datePublished 1993
5 schema:datePublishedReg 1993-01-01
6 schema:description We present a wide-spectrum algebra and refinement calculus designed to allow one to reason about query optimization in graph-based data models.A query language is wide-spectrum if it can be used to express both user level queries as well as low-level evaluation strategies or access plans. This property enables rule-based query optimization to be viewed as the process of refining expressions in such a language: “non-procedural” sub-expressions are gradually replaced by more “procedural” sub-expressions until an unambiguous access plan results. We begin by presenting an algebra that is wide-spectrum in this sense. One subset of operations within the algebra can be used to define the formal semantics of a non-procedural query language for graph-based data models. Another subset can express common data access paradigms such as an index scan, the “cut” operator in Prolog or the nested-iteration join processing strategy.We then present a refinement calculus over the algebra which defines when one algebraic expression subsumes another. The calculus makes it possible to formally prove the correctness of rewrite rules used in rule-based query optimizers, and is sufficiently expressive to admit rules encoding many forms of semantic query optimization.
7 schema:editor N809b99b8a6e04489af314e574c078280
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf N182524d1764f4f4c9153ac3b3e7fb315
12 schema:keywords Prolog
13 access paradigm
14 access plan
15 access plan results
16 algebra
17 algebraic expressions
18 calculus
19 common data access paradigms
20 correctness
21 cut
22 data access paradigm
23 data model
24 evaluation strategies
25 expression
26 form
27 formal semantics
28 graph-based data model
29 index scan
30 join processing strategy
31 language
32 level queries
33 logic
34 low-level evaluation strategies
35 model
36 nested-iteration join processing strategy
37 non-procedural query languages
38 operation
39 operators
40 optimization
41 optimizer
42 paradigm
43 plan
44 plan results
45 process
46 processing strategies
47 properties
48 queries
49 query language
50 query optimization
51 query optimizer
52 reasons
53 refinement calculus
54 refining expressions
55 results
56 rewrite rules
57 rule-based query optimization
58 rule-based query optimizer
59 rules
60 scans
61 semantic query optimization
62 semantics
63 sense
64 strategies
65 subset
66 subset of operations
67 unambiguous access plan results
68 user level queries
69 wide-spectrum algebra
70 schema:name A logic for rule-based query optimization in graph-based data models
71 schema:pagination 120-145
72 schema:productId N372714a9e66e444e94930c0f09a80e39
73 Nf4ba55605bfe4280a92a2bf486a7fd1f
74 schema:publisher N417302520ec042f686befa2b92762423
75 schema:sameAs https://app.dimensions.ai/details/publication/pub.1052689766
76 https://doi.org/10.1007/3-540-57530-8_8
77 schema:sdDatePublished 2022-01-01T19:17
78 schema:sdLicense https://scigraph.springernature.com/explorer/license/
79 schema:sdPublisher N6895d2d1e58548d6a8b1d541d1591804
80 schema:url https://doi.org/10.1007/3-540-57530-8_8
81 sgo:license sg:explorer/license/
82 sgo:sdDataset chapters
83 rdf:type schema:Chapter
84 N182524d1764f4f4c9153ac3b3e7fb315 schema:isbn 978-3-540-48212-3
85 978-3-540-57530-6
86 schema:name Deductive and Object-Oriented Databases
87 rdf:type schema:Book
88 N1fa499d9ef75453b95dcefb9f35aaf95 rdf:first N739e51226762415ab8ce36e4073223a9
89 rdf:rest N9096feaf488e4928a5571fb95bee5ef4
90 N35adc9a2a33642e3800f04d912797b58 schema:familyName Tsur
91 schema:givenName Shalom
92 rdf:type schema:Person
93 N372714a9e66e444e94930c0f09a80e39 schema:name doi
94 schema:value 10.1007/3-540-57530-8_8
95 rdf:type schema:PropertyValue
96 N417302520ec042f686befa2b92762423 schema:name Springer Nature
97 rdf:type schema:Organisation
98 N6895d2d1e58548d6a8b1d541d1591804 schema:name Springer Nature - SN SciGraph project
99 rdf:type schema:Organization
100 N739e51226762415ab8ce36e4073223a9 schema:familyName Tanaka
101 schema:givenName Katsumi
102 rdf:type schema:Person
103 N809b99b8a6e04489af314e574c078280 rdf:first Nd7f8b398d7884655aa6abe1d8497b0e5
104 rdf:rest N1fa499d9ef75453b95dcefb9f35aaf95
105 N9096feaf488e4928a5571fb95bee5ef4 rdf:first N35adc9a2a33642e3800f04d912797b58
106 rdf:rest rdf:nil
107 Na9caa222b077450b93c5a01fc96ee053 rdf:first sg:person.015614722063.65
108 rdf:rest Ne0fd5427e30c4fcdb872ec3521256a38
109 Nd7f8b398d7884655aa6abe1d8497b0e5 schema:familyName Ceri
110 schema:givenName Stefano
111 rdf:type schema:Person
112 Ne0fd5427e30c4fcdb872ec3521256a38 rdf:first sg:person.01111756132.29
113 rdf:rest rdf:nil
114 Nf4ba55605bfe4280a92a2bf486a7fd1f schema:name dimensions_id
115 schema:value pub.1052689766
116 rdf:type schema:PropertyValue
117 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
118 schema:name Information and Computing Sciences
119 rdf:type schema:DefinedTerm
120 anzsrc-for:0806 schema:inDefinedTermSet anzsrc-for:
121 schema:name Information Systems
122 rdf:type schema:DefinedTerm
123 sg:person.01111756132.29 schema:affiliation grid-institutes:None
124 schema:familyName Weddell
125 schema:givenName Grant E.
126 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01111756132.29
127 rdf:type schema:Person
128 sg:person.015614722063.65 schema:affiliation grid-institutes:None
129 schema:familyName Coburn
130 schema:givenName Neil
131 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015614722063.65
132 rdf:type schema:Person
133 grid-institutes:None schema:alternateName Department of Computer Science, University of Waterloo, UK
134 schema:name Department of Computer Science, University of Waterloo, UK
135 rdf:type schema:Organization
 




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


...